Caminos y Ciclos - menerey.weebly.com · representar por medio de caminos, ellos se develan...
Transcript of Caminos y Ciclos - menerey.weebly.com · representar por medio de caminos, ellos se develan...
Repaso
Son estructuras discretas que constan de vértices y aristas
Son conectores de los vértices
V = { Juan, Pedro, María, Lucia }, los elementos de V son…
Única arista que parte de Juan y llega a Juan
Grafo donde no hay aristas múltiples entre dos vértices ni lazos
Dada una arista {a,b}, a es el vértice inicial y b el final
Grafo que contiene todas las posibles aristas
A cada arista se le asocia un peso, es un grafo…
Aristas
Grafos
Lazo o Bucle
Vértices
Simple
Grafo dirigido
Completo
Ponderado
Caminos y Ciclos
Introducción
Hay muchos problemas que se pueden resolver y
representar por medio de caminos, ellos se develan
recorriendo las aristas de un grafo.- También
podemos asociar esta teoría a las topologías de redes
informáticas. - Por ejemplo, determinar si se puede
enviar o no un mensaje entre dos ordenadores
usando nodos o enlaces intermedios y qué camino es
más eficiente en tiempo de transmisión.-
Esto puede estudiarse utilizando un modelo de
grafos.
Topologías básicas de red
Definición De Caminos
Dado un grafo G = (V,A), un camino “P” es una secuencia de vértices V:
v1, v2,……… vn de G, tal que {vi, vi+1} A, 1≤i<n
Extremos del Camino
Vértices intermedios
Definición De Caminos - Ejemplo
v1, v2,……… vn de G, tal que {vi, vi+1} A, 1≤i<n
Extremos del Camino
Vértices intermedios
Un camino que pasa por los vértices: {1, 5, 6, 5, 4}
Tiene las aristas: {1,5},{5,6},{6,5},{5,4}
Largo del camino
El largo del camino son la cantidad de aristas del mismo y
se denota Ck, si el camino repite aristas transitadas
anteriormente se las debe contabilizar igual
Aristas del camino {1,5},{5,6},{6,5},{5,4}
C4
Distancia de un grafo
La distancia de vos vértices de G, es el largo del camino
más corto entre ambos vértices.
Se denota: (distanciag (x,y))
Distanciag (1,6) = 2
Ciclo de un Grafo
Un ciclo de G =(V,A) es un camino C de aristas que inician y
terminan en el mismo vértice y no repiten vértices interiores.
C1 = {1,3},{3,4},{4,5},{5,1}
C2 = {3}
Girth y Circunferencia
El Girth es el largo menor de un ciclo contenido en un grafo.
La Circunferencia del grafo es el largo mayor de un ciclo.
Girth (G) = 1
{3}
Circunferencia (G) = 4
Con aristas {1,3}, {3,4}, {4,5}, {5,1}
Ejercicio guiado
G = (V,A)/
V = { 0,1,2,3,4 }
A = {0}, {0,1}, {0,2}, {1,2}, {1,3}, {3,4}, {4}
a) Camino de largo 5 en G que no repita aristas y cuyos extremos sean
los vértices 1 y 4.
C5 = {1,2}, {2,0}, {0,1}, {1,3}, {3,4}
Otro camino de aristas: C5 = {1,0}, {0,2}, {2,1}, {1,3}, {3,4}
Ejercicio guiado
G = (V,A)/
V = { 0,1,2,3,4 }
A = {0}, {0,1}, {0,2}, {1,2}, {1,3}, {3,4}, {4}
b) ¿Qué ciclos existen en G?. Justifique .
C1 = {0,1},{1,2},{2,0}
C2 = {0} y C3 = {4}
Ejercicio guiado
G = (V,A)/
V = { 0,1,2,3,4 }
A = {0}, {0,1}, {0,2}, {1,2}, {1,3}, {3,4}, {4}
c) Determinar el Girth y la circunferencia de G. Justifique .
Ghirth (G) = 1 los caminos posibles son {0} o {4}
Circunferencia (G)= 3 aristas del camino {0,2}, {2,1}, {1,0}
ACTIVIDAD
Resumen de la clase
Camino
Largo del camino
Distancia
Ciclos
Girth
Circunferencia
Tarea Domiciliaria
Realizar los ejercicios restantes:
Están a disposición en la web del docente practicante.
https://menerey.weebly.com/introduccioacuten.html
Bibliografía:
Presentación de la clase. https://menerey.weebly.com/introduccioacuten.html
Introducción a la teoría de grafos. 2.1 parte 1 https://menerey.weebly.com/introduccioacuten.html
Rosen, K. H. (2003). Matemáticas Discretas y sus aplicaciones. Mc Graw Hill. Pag 503 en adelante