Teoría de grafos · Definición

Camino en un grafo

matemáticas discretasgrafos

Antes de empezar necesitas conocer

Formaliza la idea de ir de un vértice a otro siguiendo aristas, base de la conexidad y de las distancias.

Definición

Un camino de longitud \(k\) es una sucesión de vértices \(v_0,\dots,v_k\) tal que cada par consecutivo está unido por una arista de \(E\).

\[\{v_{i-1},v_i\}\in E,\qquad i=1,\dots,k\]

La longitud de un camino es el número de aristas que recorre, uno menos que la cantidad de vértices listados. Un solo vértice es un camino de longitud \(0\). Si en la sucesión pueden repetirse vértices y aristas se habla de recorrido; si no se repite ningún vértice, de camino simple. Varios textos usan «camino» para el recorrido general y «camino simple» para el que no repite vértices.

Como las aristas no tienen dirección, recorrer un camino al revés da otro camino: si se puede ir de \(u\) a \(v\), también se puede ir de \(v\) a \(u\). Esta simetría es lo que permitirá agrupar los vértices en piezas separadas al estudiar la conexidad.

Los caminos se cuentan con la matriz de adyacencia \(A\): la entrada \((i,j)\) de \(A^k\) es el número de recorridos de longitud \(k\) de \(i\) a \(j\). Por eso la diagonal de \(A^2\) contiene los grados. La distancia entre dos vértices es la longitud del camino más corto que los une, y se encuentra recorriendo el grafo por niveles.

Un error típico es confundir longitud con número de vértices, o suponer que el camino más corto es único. Los caminos son la herramienta con la que se define la conexidad y, cuando regresan a su punto de partida, los ciclos.

Para pensar

¿Cuántos vértices tiene un camino simple de longitud 7?

Tiene 8 vértices: hay uno más que aristas, y todos son distintos.

Ejercicios 10

  1. ¿Cuál es la longitud del camino \(1,2,3,4\) en un grafo donde \(12\), \(23\) y \(34\) son aristas?
  2. Un grafo tiene aristas \(12, 23, 34, 14, 25\). ¿Cuál de estas sucesiones es un camino?
  3. En el ciclo de 5 vértices \(1,2,3,4,5\) (aristas \(12,23,34,45,51\)), ¿cuál es la longitud del camino más corto de \(1\) a \(3\)?
  4. Un grafo tiene aristas \(12, 13, 23, 34\). ¿Cuántos recorridos de longitud 2 (con vértices que pueden repetirse) empiezan y terminan en \(3\)?
  5. Un camino pasa por 5 vértices distintos. ¿Cuál es su longitud?
  6. Se tiene el grafo de aristas \(12, 23, 34\). ¿Cuántos recorridos de longitud 3 van de \(1\) a \(2\) (se pueden repetir vértices)?
  7. ¿Cuál es la longitud máxima de un camino sin vértices repetidos en el grafo completo \(K_6\)?
  8. Si hay un camino de u a v en un grafo no dirigido, ¿qué se puede asegurar?
  9. Un grafo tiene aristas \(12, 23, 34, 45, 16, 65, 25\). ¿Cuál es la distancia (longitud del camino más corto) entre \(1\) y \(4\)?
  10. ¿Cuántos caminos sin vértices repetidos hay de \(1\) a \(4\) en el grafo completo \(K_4\)?

Referencias

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.4
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.2
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.2