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