Sección 8.4

Conexión en Grafos

Tomado de Matemáticas Discretas y sus Aplicaciones. Rosen

Esteban Andrés Díaz Mina

Introducción

Existen muchos problemas que se pueden

representar por medio de caminos que se forman al ir

recorriendo las aristas de un grafo. Por ejemplo, el

problema de determinar si se puede enviar o no un

mensaje entre dos ordenadores usando enlaces

intermedios puede estudiarse utilizando un

modelo de grafos.

Los modelos para planificar de forma eficiente la

rutas de distribución de correo, y de recolección

de basuras pueden resolverse utilizando modelos que

involucran caminos definidos sobre grafos.

Caminos

De manera informal, un camino es una

secuencia de aristas que comienza en un vértice

del grafo y recorre ciertas aristas del grafo

siempre conectando pares de vértices adyacentes.

Definición 1

Un camino de longitud n de u a v, donde n es un

entero positivo, en un grafo no dirigido es una

secuencia de aristas e1, e2, e3, ..., en el grafo tal

que f(e1)={x0, x1}, f(e2)={x1, x2},..,f(en)={xn-1, xn},

donde x0=u y xn=v. Cuando el grafo es simple, se

denota este camino por la secuencia x0, x1, x2,..,

xn (dado que listando estos vértices se determina

de manera única el camino).