Grafos, caminos, árboles y conectividad

Trabajamos con un grafo finito simple no dirigido G=(V, E). V es el conjunto de vértices. Cada arista es un par no ordenado de vértices distintos: AB y BA nombran la misma arista. No hay lazos de un vértice consigo mismo ni dos aristas duplicadas con los mismos extremos.

Mover puntos, curvar líneas o cambiar nombres mediante una biyección que conserve adyacencias no cambia la estructura. Esa última equivalencia se llama isomorfismo. Un cruce de líneas no crea un vértice si no se declara uno. Primero se fija qué representan vértices y aristas; un dibujo puede representar objetos distintos según ese modelo.

El grado deg(v) cuenta las aristas incidentes en v; en un grafo simple coincide con su número de vecinos. Al sumar grados, cada arista aparece una vez en cada extremo.

Es un doble conteo, no una hipótesis sobre cómo se dibujó la red.

La suma es par y, por tanto, hay un número par de vértices de grado impar. Son condiciones necesarias para una lista de grados. No bastan para que una lista sea realizable por un grafo simple: cada grado también debe respetar los vecinos disponibles y restricciones conjuntas.

Un recorrido es una secuencia de vértices consecutivos unidos por aristas y puede repetir vértices y aristas. Su longitud es el número de pasos, no el número de vértices escritos. Llamamos camino al recorrido sin vértices repetidos. Un vértice solo da un camino de longitud cero.

Si un recorrido repite un vértice, se puede borrar el tramo cerrado entre dos apariciones y conservar los mismos extremos. Repetir esa operación termina porque disminuye la longitud y produce un camino. Un ciclo simple vuelve al inicio sin repetir los demás vértices ni las aristas; en grafos simples tiene longitud al menos tres.

Dos vértices están conectados si existe un camino entre ellos. La relación es reflexiva por el camino de longitud cero, simétrica al invertir un camino y transitiva al concatenar recorridos y borrar repeticiones. Sus clases son las componentes conexas.

Un grafo con al menos un vértice es conexo si tiene una sola componente. Un vértice aislado forma una componente de tamaño uno. No hay aristas entre componentes diferentes: esa arista las conectaría. Una componente es maximal por inclusión entre los subconjuntos conectados, no necesariamente la de mayor tamaño.

La distancia entre dos vértices de una componente es la menor longitud de sus caminos. La búsqueda en anchura, BFS, usa una cola: saca primero lo descubierto antes y añade los vecinos nuevos con distancia una unidad mayor. Por eso termina cada capa antes de explorar la siguiente.

Si hubiera un camino más corto hacia un vértice recién descubierto, su penúltimo vértice habría estado en una capa anterior y lo habría descubierto antes: contradicción. Una búsqueda en profundidad, DFS, sigue una rama y retrocede; encuentra alcanzables, pero el primer camino hallado no tiene por qué ser mínimo.

Los pesos de aristas cambian la pregunta y esta garantía de BFS no se aplica a suma de pesos arbitrarios.

Un árbol es un grafo conexo y sin ciclos. La conexión asegura al menos un camino entre cada pareja. Si hubiera dos caminos distintos, después de una separación podríamos seguir hasta un primer reencuentro y obtener un ciclo. Por tanto solo hay uno.

Recíprocamente, si hay un único camino entre cada pareja, hay conexión y no puede existir un ciclo: sus dos lados darían dos caminos entre vértices del ciclo. Un árbol conserva conexión sin rutas alternativas; un grafo conexo con ciclos puede ser útil por su redundancia, aunque no sea árbol.

En un árbol finito de al menos dos vértices, los extremos de un camino de longitud máxima son hojas, de grado uno. Otro vecino fuera del camino lo alargaría; uno dentro, distinto del vecino inmediato, crearía un ciclo. Los dos extremos dan al menos dos hojas.

Quitamos una hoja y su arista. Los demás vértices siguen conectados, pues una ruta entre ellos no necesita pasar por una hoja como punto intermedio, y no aparecen ciclos.

Un bosque es un grafo sin ciclos; si tiene c componentes, cada una es árbol y al sumar se obtiene m=n−c.

Todo grafo conexo de n vértices tiene al menos n−1 aristas: una exploración selecciona una arista por cada vértice nuevo después del origen y produce un árbol generador. Si el grafo conexo tiene justo n−1, no puede contener un ciclo: borrar una arista de ese ciclo conservaría conexión con menos del mínimo.

También ausencia de ciclos y m=n−1 bastan: en el bosque m=n−c fuerza c=1. En cambio m=n−1 por sí sola no garantiza nada sobre conexión. Se necesitan ambas condiciones de la caracterización. Aquí n≥1 para hablar del árbol conexo.

Una arista es puente si borrarla aumenta el número de componentes. Si pertenece a un ciclo, los otros lados conservan una ruta entre sus extremos y el borrado no separa la componente. Si no es puente, existe una ruta alternativa tras borrarla; junto a la arista forma un ciclo.

Así es puente exactamente cuando no pertenece a ningún ciclo.

Borrar aristas de ciclos conserva conexión y termina, por finitud, en un árbol generador con todos los vértices. Todas las aristas de un árbol son puentes. Todos los árboles generadores tienen n−1 aristas; si hay pesos, no necesariamente tienen el mismo coste: elegir uno de coste mínimo es un problema adicional.