GRAFOS 3 MATE DISCRETA ING SISTEMAS

INGENIERÍA DE
SISTEMAS
M

D
ATEMÁTICA ISCRETA

GRAFOS

I

3

Mgtr. Julio César Moreno Descalzi
Mgtr. Julio César Moreno Descalzi

RECORRIDOS Y CONECTIVIDAD
• Un recorrido en un grafo G = (V,A) esuna sucesión
de vértices v0, v1, …, vk tal que {vi,vi+1} A para todo
0 ≤i < k
• La longitud de un recorrido v0, v1, …, vk es k
• Ejemplo:

G

f,b,c,f,e,d es un
recorrido de
longitud 5 sobre
G
Mgtr.Julio César Moreno Descalzi

RECORRIDOS Y CONECTIVIDAD
• Observación: Un recorrido puede repetir
vértices, y puede comenzar y acabar en vértices
diferentes
• Un camino es un recorrido v0, v1, …, vken el
que vi ≠ vj para 0 ≤i,j ≤ k, con i ≠0 o j ≠k
• Es decir en un camino todos los vértices son
distintos entre sí, excepto quizás el primero y el
último

Mgtr. Julio César Moreno DescalziRECORRIDOS Y CONECTIVIDAD
• Ejemplo:

G

a,b,e,c,d es un
camino

Mgtr. Julio César Moreno Descalzi

RECORRIDOS Y CONECTIVIDAD
• Si existe un camino entre dos vértices se dice que
están conectados
• SeaG=(V,A) un grafo. La relación
xRy  x e y están conectados
es de equivalencia.
• Si para todo par de vértices de un grafo están
conectados se dice que el grafo es conexo.
• Un grafo conexo es un grafotal que dados dos
vértices cualesquiera del mismo, hay un recorrido
que los une.
• Las componentes conexas de un grafo G son los
mayores subgrafos conexos de G.
Mgtr. Julio César Moreno DescalziRECORRIDOS Y CONECTIVIDAD
• Ejemplo. Consideramos el grafo:
• Se tiene que:
– G no es conexo: no hay camino entre a y b, por
ejemplo.
– [a] = {a,c,e} [c] = {a,c,e} [e]={a,c,e} [b]={b,d} [d]={b,d}
– G/R= {[a],[b]}
– G tiene dos componentes conexas:

Mgtr. Julio César Moreno Descalzi

RECORRIDOS Y CONECTIVIDAD
• Un recorrido v0, v1, …,vk tal que v0 = vk es un circuito.
• Un camino v0, v1, …, vk talque v0 = vk es un ciclo.

G

a,b,f,c,e,f,a
es
un circuito

f,c,b,e,f es
un ciclo

Mgtr. Julio César Moreno Descalzi

EL CAMINO MÁS CORTO

ALGORITMO
DE

DIJKSTRA

Mgtr. Julio César Moreno Descalzi...