Matemáticas - Teoría de grafos

grado o valencia de un vértice es el número de aristas incidentes al vértice. El grado de un vértice x es denotado por grado(x), g(x) o gr(x) (aunque también se usa δ(x), y del inglés d(x) y deg(x)). El grado máximo de un grafo G es denotado por Δ(G) y el grado mínimo de un grafo G es denotado por δ(G).

Vecindad de un vértice

Otra forma de definir el grado de un vértice es a través de su vecindad. La vecindad de un vértice x , denotado como ${\displaystyle N(x)\,}$ está dado por todos los vértices adyacentesa x.

${\displaystyle N(x)=\{y\in V_{G}|\{x,y\}\in E_{G}\}}$

de modo que el grado del vértice x es el número de vecinos que tiene: ${\displaystyle g(x)=|N(x)|\,}$.

Lema del apretón de manos

La fórmula de la sumatoria de grados, que relaciona la valencia de los vértices con el número de aristas es conocida como Lema del apretón de manos:

Lema del apretón de manos. La suma de los grados de un grafo ${\displaystyle G(V,E)\,}$ es igual al doble del número de aristas: ${\displaystyle \sum _{v\in V}g(v)=2|E|\,}$ Euler (1736)1

Su demostración es una prueba del doble conteo, esto porque, como cada arista tiene dos vértices extremos, es contada dos veces en las valencias de estos.

Algunas implicaciones del Lema del apretón de manos son:

• En un grafo siempre hay un número par de vértices de grado impar.
• No puede existir un grafo r-regular de s vértices si r y s son impares.
• El número de aristas de un grafo k-regular es ${\displaystyle {\frac {nk}{2}}}$, y por ende, el número de aristas de un grafo completo de n vértices es ${\displaystyle {\frac {n(n-1)}{2}}}$

Grafos dirigidos

Un grafo dirigido con vértices ${\displaystyle i}$etiquetados como ${\displaystyle (g^{-}(i),g^{+}(i))}$.

En el caso de los grafos dirigidos o digrafos, se suele distinguir entre grado de entrada ${\displaystyle g^{-}(x)\,}$, como el número de aristas que tiene al vértice x como vértice final, y grado de salida ${\displaystyle g^{+}(x)\,}$, como el número de aristas que tiene al vértice x como vértice inicial, de forma que ${\displaystyle g(x)=g^{-}(x)+g^{+}(x)\,}$.

El Lema del apretón de manos también es cierto en los grafos dirigidos. Para ello hay que distinguir para cada nodo entre grados de entrada y de salida. Por lo tanto, el Lema se expresa del siguiente modo:

${\displaystyle \sum _{v\in V}g^{-}(v)=\sum _{v\in V}g^{+}(v)=|E|\,}$

Secuencia de grados

Una secuencia de grados o lista de grados de un grafo no dirigido es una secuencia de números, los cuales son grados de los vértices de algún grafo. Para el grafo de la primera imagen su secuencia de enteros es (3, 3, 3, 2, 2, 1, 0). La lista de grados es un invariante (topológica) de un grafo, aunque dos grafos con igual lista de grados no son necesariamente isomorfos.

Un problema interesante es determinar si una secuencia de enteros no negativos cualquiera es o no gráfica, es decir, es una secuencia de grados de un grafo (simple).Erdős y Gallai² (1960) resuelven el problema con su teorema de existencia, mientras que Havel³ (1955) y Hakimi⁴ (1962) nos entregan un teorema de construcción que justifica el Algoritmo Havel-Hakimi para construir un grafo a partir de una secuencia de grados.

Teorema de Erdős-Callai. La secuencia de enteros ${\displaystyle d_{i}\,}$ con ${\displaystyle i=1,...,n\,}$ es una secuencia de grados de un grafo simple, si y sólo si: La suma de los enteros de la secuencia es par, y ${\displaystyle \sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)}$ para ${\displaystyle k\leq n-1}$

Teorema de Havel-Hakimi. Una secuencia de enteros ${\displaystyle d_{1}\geq d_{2}\geq ...\geq d_{v}\geq 0}$ es gráfica sí, y sólo sí también lo es la lista: ${\displaystyle d_{2}-1,d_{3}-1,...,d_{d_{1}+1}-1,d_{d_{1}+2},...,d_{v}}$, que resulta de eliminar el primer elemento y restar una unidad a los siguientes ${\displaystyle d_{1}}$ valores de la lista.

Valores especiales

• Un vértice con grado 0 se llama vértice aislado. Un grafo formado por vértices aislados se llama grafo vacío
• En un árbol, el vértice de grado 1 se llama hoja y forma parte del grupo de los vértices terminales.

Propiedades globales

• Si cada vértice de un grafo cualquiera tiene grado k, entonces el grafo es llamado grafo regular de grado k.
• Un grafo simple conexo contiene un camino Euleriano si, y sólo si el grafo contiene 0 ó 2 vértices de grado impar. Si el grafo no tiene vértices de grado impar entonces contiene un ciclo Euleriano.
• Por el Teorema de Brooks el número cromático de un grafo G que no es un grafo completo ni un ciclo de longitud impar es a lo sumo: ${\displaystyle \chi (G)\leq \Delta }$, y por elTeorema de Vizing todo grafo tiene índice cromático a lo más ${\displaystyle \Delta +1}$

Un grafo con vértices etiquetados según su grado. El vértice aislado se etiqueta con 0, pues no es adyacente a ningún nodo.

 grafo (del griego grafos: dibujo, imagen) es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.¹ Son objeto de estudio de la teoría de grafos.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de lasciencias exactas y las ciencias sociales.

Grafo etiquetado con 6 vértices y 7 aristas.

Historia y problema de los puentes de Königsberg

Los siete puentes de Königsberg.

El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó en su artículo en el problema de los puentes de Königsberg. La ciudad de Kaliningrado, originalmenteKönigsberg, es famosa por sus siete puentes que unen ambas márgenes del río Pregel con dos de sus islas. Dos de los puentes unen la isla mayor con la margen oriental y otros dos con la margen occidental. La isla menor está conectada a cada margen por un puente y el séptimo puente une ambas islas. El problema planteaba lo siguiente: ¿es posible dar un paseo comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo solo una vez cada uno y regresando al mismo punto de partida?

Abstrayendo este problema y planteándolo con la (entonces aún básica) teoría de grafos, Euler consigue demostrar que el grafo asociado al esquema de puentes de Königsberg no tiene solución, es decir, no es posible regresar al vértice de partida sin pasar por alguna arista dos veces.

De hecho, Euler resuelve el problema más general: ¿qué condiciones debe satisfacer un grafo para garantizar que se puede regresar al vértice de partida sin pasar por la misma arista más de una vez? Si definimos como «grado» al número de líneas que se encuentran en un punto de un grafo, entonces la respuesta al problema es que los puentes de un pueblo se pueden atravesar exactamente una vez si, salvo a lo sumo dos, todos los puntos tienen un grado par.

Definiciones

Un grafo ${\displaystyle G}$ es un par ordenado ${\displaystyle G=(V,E)}$, donde:

• ${\displaystyle V}$ es un conjunto de vértices o nodos, y
• ${\displaystyle E}$ es un conjunto de aristas o arcos, que relacionan estos nodos.

Normalmente ${\displaystyle V}$ suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.

Se llama orden del grafo ${\displaystyle G}$ a su número de vértices, ${\displaystyle |V|}$.

El grado de un vértice o nodo ${\displaystyle v\in V}$ es igual al número de arcos que lo tienen como extremo.

Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Dos o más aristas son paralelas si relacionan el mismo par de vértices.

Grafo no dirigido

Grafo no dirigido

Un grafo no dirigido o grafo propiamente dicho es un grafo ${\displaystyle G=(V,E)}$ donde:

• ${\displaystyle V\neq \emptyset }$
• ${\displaystyle E\subseteq \{x\in {\mathcal {P}}(V):|x|=2\}}$ es un conjunto de pares no ordenados de elementos de ${\displaystyle V\,}$.

Un par no ordenado es un conjunto de la forma ${\displaystyle \{a,b\}}$, de manera que ${\displaystyle \{a,b\}=\{b,a\}}$. Para los grafos, estos conjuntos pertenecen al conjunto potencia de ${\displaystyle V}$, denotado ${\displaystyle {\mathcal {P}}(V)}$, y son de cardinalidad 2.

Grafo dirigido

Grafo dirigido

Un grafo dirigido o digrafo es un grafo ${\displaystyle G=(V,E)}$ donde:

• ${\displaystyle V\neq \emptyset }$
• ${\displaystyle E\subseteq \{(a,b)\in V\times V:a\neq b\}\,}$ es un conjunto de pares ordenados de elementos de ${\displaystyle V\,}$.

Dada una arista ${\displaystyle (a,b)}$, ${\displaystyle a}$ es su nodo inicial y ${\displaystyle b}$ su nodo final.

Por definición, los grafos dirigidos no contienen bucles.

Un grafo mixto es aquel que se define con la capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.

Variantes sobre las definiciones principales

Algunas aplicaciones requieren extensiones más generales a las dos propuestas clásicas de grafos. Aunque la definición original los permite, según la aplicación concreta pueden ser válidos o no. A veces ${\displaystyle V}$ o ${\displaystyle E}$ pueden ser un multiconjunto, pudiendo haber más de una arista entre cada par de vértices. La palabra grafo (a secas) puede permitir o no múltiples aristas entre cada par de vértices, dependiendo del autor de la referencia consultada. Si se quiere remarcar la inexistencia de múltiples aristas entre cada par de vértices (y en el caso no dirigido, excluir bucles) el grafo puede llamarse simple. Por otra parte, si se quiere asegurar la posibilidad de permitir múltiples aristas, el grafo puede llamarse multigrafo (a veces se utiliza el término pseudografo para indicar que se permiten tanto bucles como múltiples aristas entre cada par de vértices).

Propiedades

• Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
• Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
• Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.
• Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

Ejemplos

La imagen es una representación del siguiente grafo:

• V:={1,2,3,4,5,6}
• E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

El hecho que el vértice 1 sea adyacente con el vértice 2 puede ser denotado como 1 ~ 2.

• En la teoría de las categorías una categoría puede ser considerada como un multigrafo dirigido, con los objetos como vértices y los morfismos como aristas dirigidas.
• En ciencias de la computación los grafos dirigidos son usados para representar máquinas de estado finito y algunas otras estructuras discretas.
• Una relación binaria R en un conjunto X es un grafo dirigido simple. Dos vértices a, b en X están conectados por una arista dirigida ab si aRb.

Grafos particulares

Existen grafos que poseen propiedades destacables. Algunos ejemplos básicos son:

• Grafo nulo: aquel que no tiene vértices ni aristas. Nótese que algunas personas exigen que el conjunto de vértices no sea vacío en la definición de grafo.
• Grafo vacío: aquel que no tiene aristas.
• Grafo trivial: aquel que tiene un vértice y ninguna arista.
• Grafo simple: aquel que no posee bucles ni aristas paralelas. Consultar variantes en esta definición.
• Multigrafo (o pseudografo): G es multigrafo si y solo si no es simple. Consultar variantes en esta definición.
• Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas.
• Grafo bipartito: sea ${\displaystyle (W,X)}$ una partición del conjunto de vértices ${\displaystyle V}$, es aquel donde cada arista tiene un vértice en ${\displaystyle W}$ y otro en ${\displaystyle X}$.
• Grafo bipartito completo: sea ${\displaystyle (W,X)}$ una partición del conjunto de vértices ${\displaystyle V}$, es aquel donde cada vértice en ${\displaystyle W}$ es adyacente sólo a cada vértice en ${\displaystyle X}$, y viceversa.
• Grafo plano: aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas.
• Árbol: grafo conexo sin ciclos.
• Grafo rueda: grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1).
• Grafo perfecto aquel que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo.

Una generalización de los grafos son los llamados hipergrafos.