Embed Size (px)
Citation preview
Conetividad en Grafos
Tomado de: Rosen, K. (2004). Matemáticas Discretas y sus Aplicaciones
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.
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.
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.
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.
a b c
f
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).
Ejemplo 1
Ejemplo 1
e1
e2
e3
e2
e3
e1
Ejemplo 2
a b c
f
Definición 1
El camino es un circuito si comienza y termina
en el mismo vértice, esto es, si u=v.
El camino o circuito se dice que pasa o atraviesa
el vértice x1, x2, ...., xn-1.
a b c
fe
Definición 1
Un camino o circuito es simple si no contiene la
misma arista más de una vez.
Ejemplo 3
Un camino o circuito es simple si no contiene la
misma arista más de una vez.
b c f
Ejemplo 3
Un camino o circuito es simple si no contiene la
misma arista más de una vez.
b c f e b
Circuito
Simple
Ejemplo 3
Un camino o circuito es simple si no contiene la
misma arista más de una vez.
b c f e b c
Ejemplo 3
Un camino o circuito es simple si no contiene la
misma arista más de una vez.
b c f e b c b
Circuito
No Simple
SolucionANDO
Halle un camino de longitud 4.
Halle un circuito de longitud 8.
Halle un camino no simple de longitud 6.
Definición 2
Un camino de longitud n de u a v, donde n es unentero positivo, en un multigrafo dirigido es unasecuencia de aristas e1, e2, e3, . . . , en el grafo tal quef(e1)={x0, x1}, f(e2)={x1, x2},..., f(en)={xn-1, xn}, donde x0=uy xn=v.
Cuando no existen aristas múltiples en el grafo, estecamino se denota por la secuencia de vértices x0, x1,x2, ...., xn.
Un camino que comienza y termina en el mismovértice es llamado un circuito.
Un camino o circuito es simple si no contiene lamisma arista mas de una vez.
SolucionANDO
Halle un camino de longitud 6.
Halle un circuito de longitud 5.
Halle un camino no simple de longitud 4.
Conectividad en grafos No dirigidos
¿Cuándo una red de computadores tiene la
propiedad de que cada par de computadores
puede compartir información?. Si un mensaje
puede ser enviado utilizando uno o más
computadores intermedios.
Ejemplo
Grafo G1
Grafo G2
Definición 3
Un grafo no dirigido se denomina conectado si
existe un camino entre cada par de distintos
vértices del grafo.
Número de Caminos entre dos vértices
El número de caminos entre dos vértices en un grafo
puede ser determinado usando la matriz de
adyacencia.
Teorema 2
Sea G un grafo con matriz de adyacencia A con
respecto al conjunto ordenado v1, v2,...,vn (con aristas
dirigidas y no dirigidas, con múltiples aristas y con
ciclos). El número de diferentes caminos de longitud r
de vi a vj, donde r es un entero positivo, es igual a la
entrada (i, j)-esima de Ar.
Ejemplo
A1A1 A2
Ejemplo
A1A2 A3
Caminos de
longitud 3 de A a B
ABABABDBACDBACAB
Ejemplo
Existen 13 Caminos
de longitud 2 de A a
A.
A1 A1 A2
Ejemplo
Halle el número de caminos de longitud 2 entre
a y f.
Existen 2 Caminos
de longitud 2 entre
a y f.
abf
aef
Finalizamos
Conectividad en Grafos
Hasta pronto
