grafos

Cap´
ıtulo 4: Grafos
Clase 2: Caminos, Circuitos Eulerianos y
Hamiltonianos
Matem´tica Discreta - CC3101
a
Profesor: Pablo Barcel´
o

P. Barcel´
o

–

Matem´tica Discreta - Cap. 4: Grafos
a

1 / 29

Navegaci´n de grafos
o

En muchos problemas de modelaci´n con grafos quisi´ramos
o
e
utilizar la capacidad para navegar el grafo por medio de los arcos.
Por ejemplo,
◮¿Cu´l es la mejor ruta para hacer la distribuci´n del correo en
a
o
una ciudad?

◮

¿Cu´l es la manera m´s econ´mica de volar de una ciudad a
a
a
o
otra?

Informalmente, un camino es una secuencia de arcos que permiten
navegar el grafo de nodo en nodo.

P. Barcel´
o

–

Matem´tica Discreta - Cap. 4: Grafos
a

2 / 29

Caminos
Definition
Sea G = (V , E ) un grafo nodirigido. Un camino entre los nodos u
y v es una secuencia e1 e2 · · · en tal que existen nodos
x0 , x1 , x2 , . . . , xn que satisfacen lo siguiente:
◮

x0 = u y xn = v , y

◮

para cada 1 ≤ i ≤ n, ei = (xi −1 , xi ).

En tal caso, decimos que el camino es de largo n.
Si el grafo es simple podemos denotarlo tan solo por
u, x1 , x2 , . . . , xn−1 , v .
Decimos que el camino es un circuitosi u = v . Es simple si todos
los ei ’s son distintos
P. Barcel´
o

–

Matem´tica Discreta - Cap. 4: Grafos
a

3 / 29

Ejercicio

Ejercicio: Ejemplifique los anteriores conceptos en el siguiente
grafo.

P. Barcel´
o

–

Matem´tica Discreta - Cap. 4: Grafos
a

4 / 29

Conecciones en grafos no dirigidos

¿Cu´ndo podemos concluir que es posible alcanzar un nodo del
agrafo desde cualquier otro nodo? ¿Cu´ndo siempre existe un
a
camino entre un par de nodos arbitrario de un grafo?

P. Barcel´
o

–

Matem´tica Discreta - Cap. 4: Grafos
a

5 / 29

Conecciones en grafos no dirigidos

¿Cu´ndo podemos concluir que es posible alcanzar un nodo del
a
grafo desde cualquier otro nodo? ¿Cu´ndo siempre existe un
a
camino entre un par de nodos arbitrariode un grafo?
Un grafo no dirigido es conexo si existe un camino entre cada par
de nodos distintos del grafo.

P. Barcel´
o

–

Matem´tica Discreta - Cap. 4: Grafos
a

5 / 29

Conecciones en grafos no dirigidos

¿Cu´ndo podemos concluir que es posible alcanzar un nodo del
a
grafo desde cualquier otro nodo? ¿Cu´ndo siempre existe un
a
camino entre un par de nodos arbitrario de ungrafo?
Un grafo no dirigido es conexo si existe un camino entre cada par
de nodos distintos del grafo.
Demuestre la siguiente propiedad:

Proposici´n
o
Existe un camino simple entre cada par de nodos distintos de un
grafo no dirigido.

P. Barcel´
o

–

Matem´tica Discreta - Cap. 4: Grafos
a

5 / 29

Componentes conexas
Si un grafo no es conexo, entonces est´ formado por launi´n
a
o
disjunta de sus componentes conexas.
Sea G un grafo no dirigido, entonces una componente conexa de G
es un subgrafo G ′ de G tal que (1) G ′ es conexo, y (2) G ′ no es un
subgrafo propio de otro subgrafo conexo de G . Decimos que G ′ es
maximal.
Ejemplo: Un grafo y sus componentes conexas.

P. Barcel´
o

–

Matem´tica Discreta - Cap. 4: Grafos
a

6 / 29

Componentesconexas en redes sociales

◮
◮

Dos n´meros telef´nicos estaban conectados si uno hab´
u
o
ıa
llamado al otro.

◮

Se descubri´ una gran cantidad de componentes conexas
o
peque˜as.
n

◮

Adem´s exist´ una componente conexa muy grande, que
a
ıa
cubr´ casi al 80 % de los n´meros telef´nicos.
ıa
u
o

◮

P. Barcel´
o

Se analiz´ el grafo de llamadas telef´nicas de AT&T.o
o

La distancia m´xima en esta componente era tan solo 20.
a

–

Matem´tica Discreta - Cap. 4: Grafos
a

7 / 29

Conectividad en grafos dirigidos
La definici´n es an´loga a la de grafos no dirigidos, pero tomando
o
a
en cuenta la direcci´n.
o
Dado grafo dirigido G = (V , E ), el grafo no dirigido subyacente G ′
de G se obtiene desde G computando la clausura sim´trica de...