GRAFOS 02 - Jair García

Vista previa del material en texto

Unidad V. Teoría de Grafos Caminos y circuitos 
Una introducción a las matemáticas de la computación 171 
 
5.2 CAMINOS Y CIRCUITOS 
 
5.2.1. Definiciones básicas. 
 
Otro concepto básico en teoría de grafos es el de camino, el cual se define a continuación. 
 
Definición 5.2.1 (Camino) 
Sean v y w dos vértices no necesariamente distintos de un grafo no dirigido G=(V,E). Un 
camino v–w en G es una sucesión alternada1 finita (sin lazos) 
 
v=v1, e1, v2, e2, v3, e3, . . . , en-1, vn-1, en, vn=w 
 
de vértices y aristas de G que comienza en el vértice v y que termina en el vértice w, que contiene 
además n aristas ei={vi,vi+1} donde 1≤ i≤n. 
 
Con frecuencia en un grafo la sucesión de lados, v=v1, e1, v2, e2, v3, e3, . . . , en-1, vn-1, en, 
vn=w, se puede escribir como: 
 
{(v1,v2), (v2,v3), (v3,v4) ,…, (vn-1,vn)}, y se puede abreviar como (v1, v2, v3, … , vn-1, vn), o bien 
),...,,( 210 neeee . 
 
Definición 5.2.2 
a) La longitud de un camino es igual al número de aristas que integran el camino. 
b) Si n=0, no existe arista, v=w, el camino se llama trivial. 
c) Cualquier camino v–w donde v=w(y n>1) se llama camino cerrado; en caso contrario 
decimos que el camino es abierto. 
 
Obsérvese que en el camino se pueden repetir vértices y aristas. 
 
Ejemplo 5.2.1 
Considere los caminos del siguiente grafo 
 
Fig. 5.2.1 
 
a) (a,b,d,c,e,d,b), es un camino abierto desde a hasta b de longitud n=6, en este camino se 
repiten los vértices b y d y la arista e4=(b,d)=(d,b). 
 
 
 
1 Consideramos una sucesión alternada a una lista que con elementos que se presentan de un modo alternado 
 
Unidad V. Teoría de Grafos Caminos y circuitos 
Una introducción a las matemáticas de la computación 172 
 
b) (b,c,d,e,c,f), es un camino abierto desde b hasta f de longitud n=5, en este camino se repite 
el vértice c y no se repite ninguna arista. 
 
c) (f,c,e,d,a), es un camino abierto desde f hasta a de longitud n=4, en este camino no se 
repiten vértices ni aristas. 
 
d) (b,c,d,b), es un camino cerrado desde b hasta b de longitud n=3, en este camino no se 
repiten vértices ni aristas. 
 
Ejemplo 5.2.2 
Sea G el grafo determinado por el conjunto V de vértices y el conjunto E de aristas. 
V={1,2,3,4,5,6,7} y E={(1,2), (2,3), (2,4), (2,5), (3,4), (5,6), (2,6), (6,7)} 
encontrar un camino de 1 a 7. 
 
 
Fig. 5.2.2 
 
Los siguientes son caminos desde el vértice 1 hasta el vértice 7. 
a) (1,2,6,7). 
b) (1,2,5,6,7). 
c) (1,2,3,4,2,5,6,7). 
 
Todos ellos nos dan una solución al problema planteado pero observamos que tienen 
diferente longitud, el primero de ellos tiene longitud 3, el segundo 4 y el tercero 7. Con lo cual 
notamos que la determinación de un camino v–w no es única. 
 
Hay algunos otros conceptos para grafos referidos a un camino, estos se presentan en la 
siguiente definición: 
 
Definición 5.2.3: Consideremos un camino de x a y (x–y) en un grafo no dirigido G=(V, E). 
a) Un recorrido es un camino abierto de x a y en el cual no se repite ninguna arista. 
b) Un circuito es un camino cerrado de x a x en el cual no se repite ninguna arista. 
c) Un camino simple es un camino abierto de x a y en el cual no se repite ningún vértice. 
d) Un ciclo es un camino cerrado de x a x en el cual sólo se repite el vértice x. 
 
Ejemplo 5.2.3 
Determine como se llaman los caminos del ejemplo 5.2.1. 
a) ninguno 
b) recorrido 
c) recorrido, camino simple 
 
Unidad V. Teoría de Grafos Caminos y circuitos 
Una introducción a las matemáticas de la computación 173 
 
d) circuito, ciclo. 
 
5.2.2 Grafos conexos 
 
Definición 5.2.4 (Grafo conexo) 
Un grafo G es conexo si dados cualesquiera dos vértices v y w en G, existe un camino de v 
a w. Un grafo es conexo si no tiene vértices aislados. 
 
Ejemplo 5.2.4 
a) Sea G=(V,E) como el grafo de la figura 5.2.2. El grafo es conexo, ya que es posible 
determinar uno (o varios) camino entre 1 y 7 y de la misma manera sucede con cualquier 
par de vértices. 
 
b) El grafo representado en la figura 
 
Fig. 5.2.3 
 
No es conexo, ya que no es posible determinar un camino entre el vértice V4 y el vértice V6 
y entre algunos otros vértices. 
 
Con este ejemplo notamos que para que un grafo sea conexo no puede tener vértices 
aislados además que, podríamos decir que debe ser de una sola pieza. Si tenemos un grafo que no 
es conexo con varias “piezas” podemos decir que cada una de ellas es conexa como sucede aquí 
con el triángulo formado por los vértices V1, V2 y V3 y el segmento formado por V5 y V6. 
 
Con todos estos conceptos considerados de teoría de gráficas nos es posible volver al 
problema inicial. Recordemos que en él se pregunta si es posible que el electricista inicie en una 
conexión, por ejemplo a, recorra todos los cables una sola vez y regrese al punto a. Para 
responder a esta pregunta empecemos por considerar el grafo asociado a la situación planteada, 
para ello se considera a las conexiones como vértices y los cables como aristas. 
 
 
Fig. 5.1.4 
 
Unidad V. Teoría de Grafos Caminos y circuitos 
Una introducción a las matemáticas de la computación 174 
 
Al trazar una gráfica la única información importante es saber cuales vértices están unidos 
por cuales aristas. 
 
El problema planteado se puede parafrasear de la siguiente forma: 
¿Existe un camino cerrado en a que recorra cada arista sólo una vez? 
 
Si intentamos formar caminos cerrados con esta característica veremos que no es posible, lo 
más cercano es el repetir una sola arista pero esto no es lo que se pide. Es importante que se 
intente encontrar una solución para apreciar que efectivamente no es posible. 
 
5.2.3 Circuitos Eulerianos 
 
Este problema nos introduce en el concepto de camino Euleriano el cual da una razón del 
porqué no se puede determinar el camino pedido. 
 
Definición5.2.5 (Circuito Euleriano) 
Sea G=(V, E) un grafo conexo. G tiene un circuito Euleriano si existe un circuito en G 
que recorra cada arista del grafo exactamente una vez. 
 
Observe que en la definición no se hace referencia a los vértices, esto indica que no importa 
si estos se repiten o no. 
 
Ejemplo 5.2.5 
Los siguientes grafos tienen un circuito Euleriano. 
a) 
 
 
Circuito Euleriano: 
a, e1, b, e3, c, e5,d, e4, b, e6, e, e7, c, e2, a. 
 
 
Fig. 5.2.5 
 
b) 
 
Circuito Euleriano: 
a, e1, b, e4, d, e9, e, e5, b, e2, c, e6, f, e10, e, e14, 
j, e15, f, e11, g, e7, c, e8, h, e12, g, e18, l, e20, h, 
e19, k, e23, l, e17, f, e16, k, e22, j, e21, i, e13, d, 
e3, a. 
 
 
 
Fig. 5.2.6 
 
 
 
Unidad V. Teoría de Grafos Caminos y circuitos 
Una introducción a las matemáticas de la computación 175 
 
Nota: Observe que cada vértice tiene grado par y se puede construir el circuito desde cualquier 
vértice. 
 
¿Si uno o más vértices tienen grado impar se puede construir un circuito Euleriano? 
No, porque cada vértice debe tener una entrada y una salida. 
 
Teorema 5.2.1 
Un grafo tiene un Circuito Euleriano si y sólo si todos sus vértices tienen grado par. 
 
Este teorema nos da una razón del porque el problema del electricista no tiene solución. En 
el grafo que representa el sistema eléctrico dado al inicio de la unidad (ver fig 5.2.4) se tienen dos 
aristas de grado impar, por lo tanto el electricista no puede analizar el sistema eléctrico 
comenzando en un vértice y terminar en el mismo vértice. 
 
Definición5.2.6 (Recorrido Euleriano) 
Sea G=(V,E) un grafo no dirigido conexo. G tiene un recorrido Euleriano, si existe un 
recorrido en G que pase por cada arista de V exactamente una vez. 
 
Ejemplo 5.2.6 
Los siguientes grafos tienen un recorrido Euleriano. 
 
a) 
 
Recorrido Euleruiano: 
e, e4, b, e1, a, e3, d, e11, e, e9, g, e10, f, e7, d, e8, g, e6, c, e2, 
b, e5 g. 
 
 
 
Fig. 5.2.7 
 
b) 
 
 
 
 
 
Recorrido Euleriano: 
 g, e9, d, e5, b, e1, a, e4, g, e11, f, e8, d, e6, c, e7, e, e2, a, e3, f, e10, e. 
 
 
Fig. 5.2.8 
 
Nota: Observe que sólo dos vérticestienen grado impar. 
 
 
Unidad V. Teoría de Grafos Caminos y circuitos 
Una introducción a las matemáticas de la computación 176 
 
Teorema 5.2.2 
Un grafo tiene un recorrido Euleriano si y sólo si G es un conexo y tiene exactamente dos 
vértices de grado impar. Para construir el recorrido Euleriano se debe empezar en un el vértice de 
grado impar y se termina en el otro vértice. 
 
Construyendo un recorrido en el sistema eléctrico del problema introductorio a esta unidad 
se resuelve el problema del electricista. 
 
5.2.4 Ciclos Hamiltonianos 
 
Definición 5.2.7 (Ciclo Hamiltoniano) 
Si G=(V,E) es un grafo con |V|≥3, decimos que G tiene un ciclo Hamiltoniano si existe un 
ciclo en G que contenga cada vértice de V. 
 
Observe que en la definición no se hace referencia a las aristas, esto indica que no importa 
si se pasa o no por todas ellas. 
 
Ejemplo 5.2.7 
El siguiente grafo tiene un ciclo hamiltoniano. 
 
Fig. 5.2.9 
Ciclos Hamiltonianos: 
 
 
Fig. 5.2.10 
 
Como puede observar, si un grafo tiene ciclo Hamiltoniano, se pueden construir muchos. 
 
Definición 5.2.8: (Camino Hamiltoniano) 
Un camino hamiltoniano es un camino simple de G que contiene todos los vértices. 
 
 
Unidad V. Teoría de Grafos Caminos y circuitos 
Una introducción a las matemáticas de la computación 177 
Ejemplo 5.2.8 
El siguiente grafo tiene un camino 
Hamiltoniano. 
 
 
Fig. 5.2.11 
 
 
Caminos Hamiltonianos: 
 
Fig.5.2.12 
 
Sugerencias para determinar si un grafo tiene un ciclo Hamiltoniano. 
a) Si G tiene un ciclo hamiltoniano, entonces para v∈V, grad(v)≥2. 
b) Si a∈V y grad(a)=2, entonces los dos aristas incidentes en el vértice a deben aparecer en 
cualquier ciclo hamiltoniano de G. 
c) Si a∈V y grad(a)>2, cuando tratamos de construir un ciclo hamiltoniano, una vez que 
hemos pasado por el vértice a, dejamos de tener en cuenta las aristas no utilizadas 
incidentes con a. 
d) Si se puede construir un ciclo hamiltoniano se debe cumplir que 
|E| - número de aristas no utilizadas=|V| 
 
Ejemplo 5.2.9 
Determinar si el siguiente grafo tiene un ciclo hamiltoniano o un camino hamiltoniano. 
 
 
Fig. 5.2.13 
 
Número de vértices=|V|=11. 
Número de aristas=|E|=19. 
 
Observe que los vértices, a, c y k sólo tienen dos aristas, por lo que las dos deben aparecer 
en el ciclo Hamiltoniano. 
 
Unidad V. Teoría de Grafos Caminos y circuitos 
Una introducción a las matemáticas de la computación 178 
 
Comenzamos a construir el ciclo partiendo del vértice a. 
 
Vértices a b c g k j f e i h d a 
Aristas eliminadas 0 4 0 1 0 1 1 1 0 0 0 0 
Total de aristas eliminadas=8 
 
|E|=Número de vértices – total de aristas eliminadas=19–8=11. 
Por lo tanto el grafo tiene ciclo hamiltoniano. 
 
Fig. 5.2.14 
	Definición 5.2.3: Consideremos un camino de x a y (x–y) en un grafo no dirigido G=(V, E).
	Un grafo G es conexo si dados cualesquiera dos vértices v y w en G, existe un camino de v a w. Un grafo es conexo si no tiene vértices aislados.
	Definición5.2.5 (Circuito Euleriano)
	Sea G=(V, E) un grafo conexo. G tiene un circuito Euleriano si existe un circuito en G que recorra cada arista del grafo exactamente una vez.
	Observe que en la definición no se hace referencia a los vértices, esto indica que no importa si estos se repiten o no.
	Nota: Observe que cada vértice tiene grado par y se puede construir el circuito desde cualquier vértice.
	¿Si uno o más vértices tienen grado impar se puede construir un circuito Euleriano?
	No, porque cada vértice debe tener una entrada y una salida.
	Teorema 5.2.1
	Un grafo tiene un Circuito Euleriano si y sólo si todos sus vértices tienen grado par.
	Este teorema nos da una razón del porque el problema del electricista no tiene solución. En el grafo que representa el sistema eléctrico dado al inicio de la unidad (ver fig 5.2.4) se tienen dos aristas de grado impar, por lo tanto el electricista no ...
	Definición5.2.6 (Recorrido Euleriano)
	Definición 5.2.7 (Ciclo Hamiltoniano)
	Definición 5.2.8: (Camino Hamiltoniano)
	Un camino hamiltoniano es un camino simple de G que contiene todos los vértices.