Teoría de grafos — vértices, aristas y conceptos básicos

La teoría de grafos es el estudio de los grafos, que son estructuras formadas por vértices y aristas. Un vértice es un objeto, y una arista muestra una relación entre dos objetos.

Si estás buscando los conceptos básicos de teoría de grafos, empieza con esta idea: un grafo es una forma clara de modelar conexiones. Personas en una red social, ciudades unidas por carreteras y páginas web enlazadas entre sí pueden representarse con grafos.

Qué significa un grafo en matemáticas

En un grafo no dirigido, una arista dice que dos vértices están conectados, y la conexión no tiene dirección. Si $A$ está unido a $B$, entonces $B$ también está unido a $A$.

En un grafo dirigido, las aristas sí tienen dirección, así que $A \to B$ y $B \to A$ son afirmaciones distintas. Muchos ejemplos para principiantes usan grafos simples no dirigidos, lo que significa que no hay lazos ni aristas repetidas entre los mismos dos vértices.

Esa condición importa porque las definiciones suelen introducirse primero en el caso simple y no dirigido. Si cambia el tipo de grafo, el significado de los términos también puede cambiar.

Términos básicos de teoría de grafos que necesitas primero

Vértices y aristas

Un vértice es la cosa que quieres seguir. Una arista es la conexión que quieres seguir.

Si un grafo modela ciudades y carreteras, las ciudades son los vértices y las carreteras son las aristas.

Grado

En un grafo no dirigido, el grado de un vértice es el número de aristas que lo tocan.

Si una ciudad tiene carreteras hacia otras tres ciudades, su grado es $3$.

Camino

Un camino es una secuencia de vértices donde cada par consecutivo está conectado por una arista.

Si hay un camino de un vértice a otro, puedes moverte de uno al otro siguiendo aristas.

Ciclo

Un ciclo es un camino que empieza y termina en el mismo vértice. En la definición básica habitual, no se repite ningún otro vértice.

Un ciclo muestra que hay un bucle cerrado en el grafo.

Grafo conexo y componentes conexas

Un grafo no dirigido es conexo si se puede llegar desde cualquier vértice a cualquier otro mediante algún camino.

Si eso no ocurre, el grafo se divide en componentes conexas. Cada componente es una parte conexa del grafo.

Ejemplo resuelto: un grafo pequeño

Supón que un grafo tiene vértices $A$, $B$, $C$, $D$ y $E$, con aristas

$$AB,\ AC,\ BC,\ CD$$

Esto da un triángulo sobre $A$, $B$ y $C$, una arista extra de $C$ a $D$ y un vértice aislado $E$.

Ahora las ideas principales son fáciles de ver.

Los grados son

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

Hay un camino de $A$ a $D$:

$$A-C-D$$

Hay un ciclo:

$$A-B-C-A$$

El grafo no es conexo porque no se puede llegar a $E$ desde los otros vértices. Así que el grafo tiene dos componentes conexas: una que contiene a $A,B,C,D$ y otra que contiene solo a $E$.

Este único ejemplo muestra cómo encajan el grado, el camino, el ciclo, los vértices aislados y las componentes conexas.

Una comprobación rápida: suma de grados

Para cualquier grafo no dirigido finito,

$$\sum \deg(v) = 2|E|$$

Esto funciona porque cada arista toca exactamente dos extremos, así que cada arista suma $1$ a dos conteos de grado.

En el ejemplo anterior, la suma de grados es

$$2+2+3+1+0=8$$

y el número de aristas es $4$, así que

$$2|E| = 2 \cdot 4 = 8$$

Esta es una comprobación útil cuando cuentas grados a mano. Si los números no coinciden, algo está mal.

Errores comunes en teoría de grafos

Confundir vértices y aristas

Los vértices son los objetos. Las aristas son las relaciones entre ellos.

Olvidar qué tipo de grafo tienes

Una afirmación que es cierta para un grafo simple no dirigido puede necesitar cambios para un grafo dirigido o para un grafo que permite lazos.

Tratar un camino como si fuera un ciclo

Un camino no tiene que volver al punto de partida. Un ciclo sí.

Ignorar los vértices aislados

Un vértice con grado $0$ sigue siendo parte del grafo. Puede cambiar si el grafo es conexo o no.

Dónde se usan los conceptos básicos de teoría de grafos

Estas ideas aparecen en redes informáticas, planificación de rutas, programación de tareas, sistemas de recomendación y redes sociales. El contexto cambia, pero las mismas preguntas siguen apareciendo: qué está conectado, a qué se puede llegar y dónde están los bucles.

Por eso la teoría de grafos aparece pronto tanto en matemáticas discretas como en informática.

Prueba con un grafo similar

Dibuja cuatro vértices $P$, $Q$, $R$ y $S$. Añade las aristas $PQ$, $QR$, $RS$ y $SP$.

Luego responde tres preguntas: ¿cuál es el grado de cada vértice?, ¿es conexo el grafo? y ¿contiene un ciclo?