Grafo

En matemáticas, y más específicamente en teoría de grafos, un Grafo es una estructura que equivale a un conjunto de objetos en los que algunos pares de objetos están en algún sentido "relacionados". Los objetos corresponden a abstracciones matemáticas llamadas vértices (también llamados nodos o puntos) y cada uno de los pares de vértices relacionados se llama arista (también llamado enlace o línea). Por lo general, un gráfico se representa en forma de diagrama como un conjunto de puntos o círculos para los vértices, unidos por líneas o curvas para los bordes. Los gráficos son uno de los objetos de estudio de las matemáticas discretas.

Los bordes pueden ser dirigidos o no dirigidos. Por ejemplo, si los vértices representan personas en una fiesta y hay un borde entre dos personas si se dan la mano, entonces este gráfico no está dirigido porque cualquier persona A puede darle la mano a una persona B solo si B también le da la mano a A. Por el contrario, si cualquier arista de una persona A a una persona B corresponde a que A le debe dinero a B, entonces este gráfico es dirigido, porque la deuda no es necesariamente recíproca.

Los grafos son el tema básico estudiado por la teoría de grafos. La palabra "gráfico" fue utilizada por primera vez en este sentido por JJ Sylvester en 1878 en una relación directa entre las matemáticas y la estructura química (lo que él llamó imagen químico-gráfica).

Definiciones

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.

Grafico

Un grafo (a veces llamado grafo no dirigido para distinguirlo de un grafo dirigido, o grafo simple para distinguirlo de un multigrafo) es un par G = (V, E), donde V es un conjunto cuyos elementos se llaman vértices (singular: vértice), y E es un conjunto de vértices apareados, cuyos elementos se denominan aristas (a veces enlaces o líneas).

Los vértices x e y de una arista { x, y } se denominan extremos de la arista. Se dice que la arista une x e y y que incide sobre x e y. Un vértice puede no pertenecer a ninguna arista, en cuyo caso no está unido a ningún otro vértice.

Un multigrafo es una generalización que permite que varias aristas tengan el mismo par de extremos. En algunos textos, los multigrafos se llaman simplemente grafos.

A veces, se permite que los gráficos contengan bucles, que son bordes que unen un vértice consigo mismo. Para permitir bucles, la definición anterior debe cambiarse definiendo los bordes como conjuntos múltiples de dos vértices en lugar de dos conjuntos. Estos gráficos generalizados se denominan gráficos con bucles o simplemente gráficos cuando está claro por el contexto que los bucles están permitidos.

Generalmente, se supone que el conjunto de vértices V es finito; esto implica que el conjunto de aristas también es finito. Los gráficos infinitos a veces se consideran, pero se ven más a menudo como un tipo especial de relación binaria, ya que la mayoría de los resultados en gráficos finitos no se extienden al caso infinito o necesitan una prueba bastante diferente.

Un gráfico vacío es un gráfico que tiene un conjunto vacío de vértices (y, por lo tanto, un conjunto vacío de aristas). El orden de un grafo es su número de vértices | V |. El tamaño de un gráfico es su número de aristas | mi |. Sin embargo, en algunos contextos, como para expresar la complejidad computacional de los algoritmos, el tamaño es | V | + | mi | (de lo contrario, un gráfico no vacío podría tener un tamaño 0). El grado o valencia de un vértice es el número de aristas que le son incidentes; para gráficos con bucles, un bucle se cuenta dos veces.

En un gráfico de orden n, el grado máximo de cada vértice es n − 1 (o n si se permiten bucles), y el número máximo de aristas es n (n − 1)/2 (o n (n + 1)/ 2 si se permiten bucles).

Los bordes de un gráfico definen una relación simétrica en los vértices, llamada relación de adyacencia. Específicamente, dos vértices x e y son adyacentes si { x, y } es una arista. Un grafo puede ser completamente especificado por su matriz de adyacencia A, que es una matriz cuadrada n × n, con Aij especificando el número de conexiones desde el vértice _i al vértice j. Para un gráfico simple, A _ij ∈ {0,1}, indicando desconexión o conexión respectivamente, mientras que A_ii = 0(es decir, una arista no puede empezar y terminar en el mismo vértice). Los gráficos con bucles automáticos se caracterizarán por que algunos o todos losA _ii sean iguales a un número entero positivo, y los multigrafos (con múltiples aristas entre vértices) se caracterizarán por que algunos o todos losA _ij sean iguales a un número entero positivo. Los gráficos no dirigidos tendrán una matriz de adyacencia simétrica ( A _ij = A _ji).

Gráfico dirigido

Un gráfico dirigido o dígrafo es un gráfico en el que los bordes tienen orientaciones.

En un sentido restringido pero muy común del término, un gráfico dirigido es un par G = (V, E) que comprende:

• V, un conjunto de vértices (también llamados nodos o puntos);
• mi ⊆ {(X, y) | (x, y) ∈ V, x ≠ y }, un conjunto de aristas (también llamadas aristas dirigidas, enlaces dirigidos, líneas dirigidas, flechas o arcos) que son pares ordenados de vértices (es decir, una arista está asociada con dos vértices distintos vértices).

Para evitar ambigüedades, este tipo de objeto puede denominarse precisamente grafo simple dirigido.

En la arista (x, y) dirigida de x a y, los vértices x e y se denominan extremos de la arista, x la cola de la arista ey la cabeza de la arista. Se dice que la arista une xey y que incide sobre xey sobre y. Un vértice puede existir en un gráfico y no pertenecer a un borde. La arista (y, x) se llamaarista invertida de (x, y). Las aristas múltiples, no permitidas según la definición anterior, son dos o más aristas con la misma cola y la misma cabeza.

En un sentido más general del término que permite múltiples aristas, un gráfico dirigido es un triple ordenado G = (V, E, ϕ) que comprende:

• V, un conjunto de vértices (también llamados nodos o puntos);
• E, un conjunto de aristas (también llamadas aristas dirigidas, enlaces dirigidos, líneas dirigidas, flechas o arcos);
• ϕ: mi → {(x, y) | (x, y) ∈ V, x ≠ y }, una función de incidencia que asigna cada arista a un par ordenado de vértices (es decir, una arista está asociada con dos vértices distintos).

Para evitar ambigüedades, este tipo de objeto puede denominarse precisamente multigrafo dirigido.

Un bucle es una arista que une un vértice consigo mismo. Los gráficos dirigidos, tal como se definen en las dos definiciones anteriores, no pueden tener bucles, porque un bucle que une un vértice x consigo mismo es el borde (para un gráfico simple dirigido) o incide en (para un multigrafo dirigido) (x, x) que no es en {(x, y) | (X, y) ∈ V, X ≠ y }. Entonces, para permitir bucles, las definiciones deben expandirse. Para grafos simples dirigidos, la definición de E debe modificarse a E ⊆ {(x, y) | (x, y) ∈ V }. Para multigrafos dirigidos, la definición de ϕ debe modificarse a ϕ: E → {(x, y) | (x, y) ∈ V }. Para evitar ambigüedades, este tipo de objetos pueden llamarse precisamente gráfico simple dirigido que permite bucles y multigráfico dirigido que permite bucles (o carcaj) respectivamente.

Los bordes de un gráfico simple dirigido que permite bucles G es una relación homogénea ~ en los vértices de G que se llama relación de adyacencia de G. Específicamente, para cada borde (x, y), se dice que sus extremos x e y son adyacentes entre sí, lo que se denota x ~ y.

Gráfico mixto

Un grafo mixto es un grafo en el que algunos bordes pueden estar dirigidos y otros pueden no estarlo. Es un triple ordenado G = (V, E, A) para un gráfico simple mixto y G = (V, E, A, ϕ _E, ϕ _A) para un multigrafo mixto con V, E (las aristas no dirigidas), A (los bordes dirigidos), ϕ _E y ϕ _Adefinido como arriba. Los grafos dirigidos y no dirigidos son casos especiales.

Gráfico ponderado

Un gráfico ponderado o una red es un gráfico en el que se asigna un número (el peso) a cada borde. Dichos pesos pueden representar, por ejemplo, costos, longitudes o capacidades, según el problema en cuestión. Dichos gráficos surgen en muchos contextos, por ejemplo, en problemas de ruta más corta, como el problema del viajante de comercio.

Tipos de gráficos

Gráfico orientado

Una definición de un gráfico orientado es que es un gráfico dirigido en el que como máximo uno de (x, y) y (y, x) pueden ser bordes del gráfico. Es decir, es un grafo dirigido que se puede formar como una orientación de un grafo no dirigido (simple).

Algunos autores usan "gráfico orientado" para significar lo mismo que "gráfico dirigido". Algunos autores usan "gráfico orientado" para referirse a cualquier orientación de un gráfico o multigráfico no dirigido dado.

Gráfico regular

Un grafo regular es un grafo en el que cada vértice tiene el mismo número de vecinos, es decir, cada vértice tiene el mismo grado. Un grafo regular con vértices de grado k se llama grafo regular k o grafo regular de grado k.

Gráfico simétrico

Un gráfico simétrico es un gráfico tal que, para cualquier par de aristas, tiene una operación de simetría que relaciona la primera con la segunda en cualquiera de las orientaciones especificadas.

Gráfico completo

Un grafo completo es un grafo en el que cada par de vértices está unido por una arista. Un gráfico completo contiene todas las aristas posibles.

Gráfico finito

Un grafo finito es un grafo en el que el conjunto de vértices y el conjunto de aristas son conjuntos finitos. De lo contrario, se llama un gráfico infinito.

Más comúnmente en la teoría de grafos se da a entender que los gráficos discutidos son finitos. Si los gráficos son infinitos, eso generalmente se establece específicamente.

Gráfico conectado

En un gráfico no dirigido, un par desordenado de vértices { x, y } se llama conectado si un camino lleva de x a y. De lo contrario, el par desordenado se llama desconectado.

Un grafo conexo es un grafo no dirigido en el que todos los pares desordenados de vértices del grafo están conectados. De lo contrario, se llama un gráfico desconectado.

En un gráfico dirigido, un par ordenado de vértices (x, y) se llama fuertemente conectado si un camino dirigido lleva de x a y. De lo contrario, el par ordenado se llama débilmente conectado si un camino no dirigido conduce de x a y después de reemplazar todas sus aristas dirigidas con aristas no dirigidas. De lo contrario, el par ordenado se llama desconectado.

Un grafo fuertemente conexo es un grafo dirigido en el que cada par ordenado de vértices en el grafo está fuertemente conexo. De lo contrario, se llama un gráfico débilmente conectado si cada par ordenado de vértices en el gráfico está débilmente conectado. De lo contrario, se llama un gráfico desconectado.

Un gráfico conectado con k vértices o un gráfico conectado con k bordes es un gráfico en el que no existe un conjunto de k - 1 vértices (respectivamente, bordes) que, cuando se eliminan, desconectan el gráfico. Un grafo conexo en k vértices a menudo se denomina simplemente grafo conexo en k.

Gráfica bipartita

Un grafo bipartito es un grafo simple en el que el conjunto de vértices se puede dividir en dos conjuntos, W y X, de modo que no haya dos vértices en W que compartan una arista común y dos vértices en X no compartan una arista común. Alternativamente, es un gráfico con un número cromático de 2.

En un grafo bipartito completo, el conjunto de vértices es la unión de dos conjuntos disjuntos, W y X, de modo que cada vértice en W es adyacente a cada vértice en X pero no hay aristas dentro de W o X.

Gráfico de ruta

Un gráfico de ruta o gráfico lineal de orden n ≥ 2 es un gráfico en el que los vértices se pueden enumerar en un orden v ₁, v ₂, …, v _n tal que las aristas son { v _i, v _{i +1} } donde i = 1, 2, …, n − 1. Los gráficos de ruta se pueden caracterizar como gráficos conectados en los que el grado de todos los vértices menos dos es 2 y el grado de los dos vértices restantes es 1. Si un gráfico de ruta se presenta como un subgrafo de otro gráfico, es un camino en ese gráfico.

Gráfico plano

Un grafo plano es un grafo cuyos vértices y aristas se pueden dibujar en un plano tal que ninguna de las dos aristas se cruzan.

Gráfico de ciclo

Un gráfico de ciclo o gráfico circular de orden n ≥ 3 es un gráfico en el que los vértices se pueden enumerar en un orden v ₁, v ₂, …, v _n tal que las aristas son { v _i, v _{i +1} } donde yo = 1, 2, …, norte − 1, más la arista { v norte, v _{1 }}. Los gráficos de ciclo se pueden caracterizar como gráficos conectados en los que el grado de todos los vértices es 2. Si un gráfico de ciclo aparece como un subgráfico de otro gráfico, es un ciclo o circuito en ese gráfico.

Árbol

Un árbol es un gráfico no dirigido en el que dos vértices están conectados exactamente por un camino, o de manera equivalente, un gráfico no dirigido acíclico conectado.

Un bosque es un grafo no dirigido en el que dos vértices están conectados como máximo por un camino, o de manera equivalente, un grafo no dirigido acíclico, o de manera equivalente, una unión disjunta de árboles.

Poliárbol

Un poliárbol (o árbol dirigido, árbol orientado o red conectada individualmente) es un gráfico acíclico dirigido (DAG) cuyo gráfico no dirigido subyacente es un árbol.

Un polibosque (o bosque dirigido o bosque orientado) es un grafo acíclico dirigido cuyo grafo no dirigido subyacente es un bosque.

Clases avanzadas

Los tipos de gráficos más avanzados son:

• gráfico de Petersen y sus generalizaciones;
• gráficos perfectos;
• cografos;
• grafos cordales;
• otros gráficos con grandes grupos de automorfismos: gráficos transitivos de vértice, transitivos de arco y transitivos de distancia;
• grafos fuertemente regulares y sus generalizaciones grafos regulares de distancia.

Propiedades de los gráficos

Dos aristas de un gráfico se llaman adyacentes si comparten un vértice común. Dos aristas de un grafo dirigido se llaman consecutivas si la cabeza de la primera es la cola de la segunda. Del mismo modo, dos vértices se llaman adyacentes si comparten una arista común (consecutivos si el primero es la cola y el segundo es la cabeza de una arista), en cuyo caso se dice que la arista común une los dos vértices. Una arista y un vértice en esa arista se llaman incidente.

El grafo con un solo vértice y sin aristas se llama grafo trivial. Un gráfico con sólo vértices y sin bordes se conoce como un gráfico sin bordes. El gráfico sin vértices y sin bordes a veces se denomina gráfico nulo o gráfico vacío, pero la terminología no es consistente y no todos los matemáticos permiten este objeto.

Normalmente, los vértices de un grafo, por su naturaleza de elementos de un conjunto, son distinguibles. Este tipo de gráfico puede llamarse etiquetado con vértices. Sin embargo, para muchas preguntas es mejor tratar los vértices como indistinguibles. (Por supuesto, los vértices aún pueden distinguirse por las propiedades del gráfico en sí, por ejemplo, por el número de aristas incidentes). Las mismas observaciones se aplican a las aristas, por lo que las gráficas con aristas etiquetadas se denominan aristas etiquetadas. Los gráficos con etiquetas adjuntas a los bordes o vértices se designan más generalmente como etiquetados. En consecuencia, los gráficos en los que los vértices son indistinguibles y los bordes son indistinguibles se denominan sin etiqueta. (En la literatura, el término etiquetadopuede aplicarse a otros tipos de etiquetado, además del que sirve solo para distinguir diferentes vértices o bordes).

La categoría de todos los gráficos es la categoría de coma Conjunto ↓ D donde D: Conjunto → Conjunto es el funtor que toma un conjunto s a s × s.

Ejemplos

• El diagrama es una representación esquemática del gráfico con vértices y aristas.
• En informática, los gráficos dirigidos se utilizan para representar conocimiento (p. ej., gráfico conceptual), máquinas de estados finitos y muchas otras estructuras discretas.
• Una relación binaria R sobre un conjunto X define un grafo dirigido. Un elemento x de X es un predecesor directo de un elemento y de X si y solo si xRy.
• Un gráfico dirigido puede modelar redes de información como Twitter, con un usuario siguiendo a otro.
• Ejemplos particularmente regulares de gráficos dirigidos son los gráficos de Cayley de grupos generados finitamente, así como los gráficos de clases laterales de Schreier.
• En la teoría de categorías, cada categoría pequeña tiene un multigrafo dirigido subyacente cuyos vértices son los objetos de la categoría y cuyos bordes son las flechas de la categoría. En el lenguaje de la teoría de categorías, se dice que hay un funtor olvidadizo desde la categoría de las categorías pequeñas hasta la categoría de los carcajes.

Operaciones gráficas

Hay varias operaciones que producen nuevos gráficos a partir de los iniciales, que se pueden clasificar en las siguientes categorías:

• operaciones unarias, que crean un nuevo gráfico a partir de uno inicial, como:
  • contracción del borde,
  • gráfico de líneas,
  • gráfico doble,
  • gráfico de complemento,
  • reescritura de gráficos;
• operaciones binarias, que crean un nuevo gráfico a partir de dos iniciales, como por ejemplo:
  • unión disjunta de grafos,
  • producto cartesiano de grafos,
  • producto tensorial de gráficas,
  • fuerte producto de grafos,
  • producto lexicografico de grafos,
  • gráficas serie-paralelo.

Generalizaciones

En una hipergrafía, una arista puede unir más de dos vértices.

Un grafo no dirigido puede verse como un complejo simplicial que consta de 1-simples (los bordes) y 0-simples (los vértices). Como tales, los complejos son generalizaciones de gráficos, ya que permiten simples de dimensiones superiores.

Cada gráfico da lugar a una matroide.

En la teoría de modelos, un gráfico es solo una estructura. Pero en ese caso, no hay limitación en el número de aristas: puede ser cualquier número cardinal, ver gráfico continuo.

En biología computacional, el análisis de gráficos de potencia introduce gráficos de potencia como una representación alternativa de gráficos no dirigidos.

En los sistemas de información geográfica, las redes geométricas se modelan de cerca a partir de gráficos y toman prestados muchos conceptos de la teoría de gráficos para realizar análisis espaciales en redes de carreteras o redes de servicios públicos.