Teoría de grafos

En matemáticas , la teoría de grafos es el estudio de los gráficos , que son estructuras matemáticas utilizadas para modelar relaciones por pares entre objetos. Un grafo en este contexto se compone de vértices (también llamados nodos o puntos ) que están conectados por aristas (también llamados enlaces o líneas ). Se hace una distinción entre grafos no dirigidos , donde las aristas unen dos vértices simétricamente, y gráficos dirigidos , donde las aristas unen dos vértices asimétricamente. Los gráficos son uno de los principales objetos de estudio de las matemáticas discretas .

Las definiciones en la teoría de grafos varían. Las siguientes son algunas de las formas más básicas de definir gráficos y estructuras matemáticas relacionadas .

En un sentido restringido pero muy común del término, ^{[1] [2]} un gráfico es un par ordenado que comprende:${\ estilo de visualización G = (V, E)}$

En la arista , los vértices y se denominan extremos de la arista. Se dice que el borde se une y y es incidente una y otra vez . Un vértice puede existir en un gráfico y no pertenecer a un borde. Las aristas múltiples , no permitidas según la definición anterior, son dos o más aristas que unen los mismos dos vértices.${\ estilo de visualización \ {x, y \}}$${\ estilo de visualización x}$${\ estilo de visualización y}$ ${\ estilo de visualización x}$${\ estilo de visualización y}$${\ estilo de visualización x}$${\ estilo de visualización y}$

En un sentido más general del término que permite múltiples aristas, ^{[3] [4]} un gráfico es un triple ordenado que comprende:${\displaystyle G=(V,E,\phi )}$

Un bucle es una arista que une un vértice consigo mismo. Los gráficos definidos en las dos definiciones anteriores no pueden tener bucles, porque un bucle que une un vértice consigo mismo es el borde (para un gráfico simple no dirigido) o incide sobre (para un multigrafo no dirigido) que no está en . Entonces, para permitir bucles, las definiciones deben expandirse. Para gráficos simples no dirigidos, la definición de debe modificarse a . Para multigrafos no dirigidos, la definición de debe modificarse a . Para evitar la ambigüedad, estos tipos de objetos pueden denominarse bucles que permiten gráficos simples no dirigidos y bucles que permiten multigráficos no dirigidos (a veces también seudógrafos no dirigidos ).${\ estilo de visualización x}$${\ estilo de visualización \ {x, x \} = \ {x \}}$${\displaystyle \{\{x,y\}\mid x,y\in V\;{\textrm {y}}\;x\neq y\}}$${\ estilo de visualización E}$${\displaystyle E\subseteq \{\{x,y\}\mid x,y\in V\}}$${\ estilo de visualización \ phi}$${\displaystyle \phi :E\to \{\{x,y\}\mid x,y\in V\}}$), respectivamente.

Un dibujo de un gráfico.

Un gráfico con tres vértices y tres aristas.

Un gráfico dirigido con tres vértices y cuatro aristas dirigidas (la flecha doble representa una arista en cada dirección).

El grafo de red formado por los editores de Wikipedia (bordes) que contribuyeron a diferentes versiones del idioma de Wikipedia (vértices) durante un mes en el verano de 2013. ^[6]

Teoría de grafos en sociología: Sociograma de Moreno (1953). ^[17]

El problema del puente de Königsberg