Teoría De Grafos
Páginas: 3 (665 palabras)
Publicado: 8 de julio de 2012
TEORIA DE GRAFOS
1. DEFINICION
La empresa de energía de una ciudad paga a una compañía de mensajería por entregar, en cada una de las casas de los usuarios del servicio, el recibocorrespondiente a cada mes.
El siguiente Plano muestra de uno de los sectores que debe visitar un empleado de la empresa
El empleado debe entregar recibos en cada una de las casas del sector este tipo deproblema se relaciona con varios aspectos:
· ¿Cuál será la manera más productiva de hacerlo?
· ¿Cuál será el recorrido optimo en tiempo, dinero y esfuerzo?
· ¿Cuántas veces, como mínimo, tendrá quepasar el empleado por la misma esquina?
· ¿Tendrá que pasar varias veces por la misma cuadra?
El problema de repartir los recibos se puede plantear a partir de una estructura denominada grafo.Grafo: Un grafo es un conjunto finito de puntos y enlaces entre esos puntos los puntos reciben el nombre de vértices y los enlaces reciben el nombre de aristas.
En el caso del empleado de la empresade energía, cada una de las esquinas marcadas con A, B, C, D, E, F, G, H, son los vértices y cada recorrido señalado con un segmento entre dos vértices y cada recorrido señalado con un segmento entredos vértices hace las veces de arista.
Camino: Un camino es una secuencia de aristas que produce una ruta en el grafo que comienza en un vértice y termina en otro.
1. Escribir una camino que puedeseguir el empleado de la empresa de energía, si debe visitar las casas comprendidas entre las esquinas A , B, J, D, C, y H.
Solución
El empleado puede ir de la esquina A hasta la esquina B, luego,ir hasta la esquina J; posteriormente, pasar por la esquina I, seguir hasta la esquina D, luego, a las esquina C y, finalmente, pasar por la esquina G para llegar a la esquina H.CIRCUITOS
Circuito: Un circuito es un camino que recorre todo el grafo; comienza y acaba en un vértice.
Ejercicio
a. Trazar dos circuitos diferentes si debe partir del punto A.
b....
1. DEFINICION
La empresa de energía de una ciudad paga a una compañía de mensajería por entregar, en cada una de las casas de los usuarios del servicio, el recibocorrespondiente a cada mes.
El siguiente Plano muestra de uno de los sectores que debe visitar un empleado de la empresa
El empleado debe entregar recibos en cada una de las casas del sector este tipo deproblema se relaciona con varios aspectos:
· ¿Cuál será la manera más productiva de hacerlo?
· ¿Cuál será el recorrido optimo en tiempo, dinero y esfuerzo?
· ¿Cuántas veces, como mínimo, tendrá quepasar el empleado por la misma esquina?
· ¿Tendrá que pasar varias veces por la misma cuadra?
El problema de repartir los recibos se puede plantear a partir de una estructura denominada grafo.Grafo: Un grafo es un conjunto finito de puntos y enlaces entre esos puntos los puntos reciben el nombre de vértices y los enlaces reciben el nombre de aristas.
En el caso del empleado de la empresade energía, cada una de las esquinas marcadas con A, B, C, D, E, F, G, H, son los vértices y cada recorrido señalado con un segmento entre dos vértices y cada recorrido señalado con un segmento entredos vértices hace las veces de arista.
Camino: Un camino es una secuencia de aristas que produce una ruta en el grafo que comienza en un vértice y termina en otro.
1. Escribir una camino que puedeseguir el empleado de la empresa de energía, si debe visitar las casas comprendidas entre las esquinas A , B, J, D, C, y H.
Solución
El empleado puede ir de la esquina A hasta la esquina B, luego,ir hasta la esquina J; posteriormente, pasar por la esquina I, seguir hasta la esquina D, luego, a las esquina C y, finalmente, pasar por la esquina G para llegar a la esquina H.CIRCUITOS
Circuito: Un circuito es un camino que recorre todo el grafo; comienza y acaba en un vértice.
Ejercicio
a. Trazar dos circuitos diferentes si debe partir del punto A.
b....
Leer documento completo
Regístrate para leer el documento completo.