UNIVERSIDAD NACIONAL DE LOJA

REA DE LA ENERGA LAS INDUSTRIAS Y LOS RECURSOS NATURALES NO RENOVABLES

CARRERA DE INGENIERA EN SISTEMAS

Tarea en clase

Nombre: Gabriela Cuenca

Fecha: 10-07-2015

Paralelo: 3ro B

Tema: Teora de grafos

Ejercicios.

El ciclo euleriano

1. La ciudad de Knigsberg est atravesada por un rio que tiene 2 islas y 7 puentes como muestra

la figura 1. Se pregunta si es posible partir del sector A y, haciendo una caminata, pasar por

cada puente una sola vez volviendo al punto de partida. En el grafo de la figura 2 el problema

se traduce en partir de A y recorrer las 7 ramas sin repetir ninguna y volver a A (ciclo euleriano).

Este problema fue encarado por Euler en 1736 y es el origen de la teora de grafos.

SOLUCIN:

Euler determin, en el contexto del problema, que los puntos intermedios de un recorrido posible

necesariamente han de estar conectados a un nmero par de lneas. En efecto, si llegamos a un punto

desde alguna lnea, entonces el nico modo de salir de ese punto es por una lnea diferente. Esto

significa que tanto el punto inicial como el final seran los nicos que podran estar conectados con un

nmero impar de lneas. Sin embargo, el requisito adicional del problema dice que el punto inicial debe

ser igual al final, por lo que no podra existir ningn punto conectado con un nmero impar de lneas.

El ciclo hamiltoniano.

2. A un dodecaedro, cuerpo solido regular con doce caras pentagonales, se la ha quitado una cara

y se lo ha aplastado en el plano como muestra la figura 3

Imaginemos a los vrtices de esta figura como ciudades y a las aristas como tramos de caminos

entre dos ciudades. Se pregunta si hay un camino formado de tramos que partiendo de una ciudad

visite todas las ciudades una sola vez volviendo a la ciudad de partida (ciclo hamiltoniano)

2

Coloreado de mapas

3. La figura 4 muestra un mapa con 4 distritos A, B, C y D. Se trata de pintar cada distrito con un

color de forma que dos regiones con un borde comn (que no sea un punto) tengan distintos

colores y queremos hacer esto usando un mnimo nmero de colores. La figura 5 muestra un

grafo homeomorfo al mapa, en el sentido que los vrtices del grafo se corresponden con las

regiones del mapa y dos vrtices estn conectados por una rama cuando las regiones

correspondientes tienen un borde comn. El problema se traduce en el grafo a minimizar el

nmero de colores al asignar un color a cada vrtice de forma que cualquier rama tenga

extremos de distinto color.

Respuesta

El recorrido del cartero

4. Imaginemos un grafo que representa el mapa de las calles de un barrio. Una calle va de una

esquina a la otra. En una esquina est ubicada una oficina de correos. Un cartero sale de la

oficina de correos y tiene que recorrer todas las calles y volver a la oficina. Se plantea el

problema de un recorrido que minimice el nmero de calles que est obligado a recorrer ms

de una vez.

SOLUCIN: Sea V0(G)={u1, u2, ., u2n} el conjunto de vrtices de grado impar de G.Recordamos que son un nmero par. Definimos una particin emparejada de Vo(G) como una particin de Vo(G) En n conjuntos de dos elementos:

={ {u11, u12}, {u21, u22}, , {un1,un2} }

Se define la distancia de la particin emparejada como

d()= d (ui1,ui2)

Y m(G)= min ( d() )

3 El camino euleriano se obtendra duplicando nicamente las aristas de los caminos que van de u i1 a ui2.

El problema del caballo en el juego de ajedrez

5. Consideremos un tablero de ajedrez y un caballo. Se pregunta si es posible que el caballo parta

de un casillero y visite todos los otros 63 casilleros una solo vez volviendo al punto inicial. (ciclo

hamiltoniano)

El problema de cruzar el rio

6. Tenemos 3 misioneros y 3 canbales y un bote para cruzar el rio. El bote tiene capacidad para 2

personas a lo sumo. Se trata que los 6 individuos crucen el rio de forma que en ningn momento

haya ms canbales que misioneros en cualquiera de los dos mrgenes del rio. Indiquemos con

(i,j) el hecho que haya i misioneros y j canbales en un dado margen. Entonces (i,j)(i-1, j-1)

significa una posible transicin, es decir, cruzan el rio un misionero y un canbal. A continuacin

(i-1, j-1) (i, j-1) significa que volvi el misionero solo. Imaginemos que dibujamos todos los

pares (i,j) como puntos en el plano (ij) y unimos por flechas los pares que representan

transiciones posibles. Se trata de hallar una sucesin de flechas consecutivas que parta de (3,3)

y termine en (0,0)

7. Determine V, E, todas las aristas paralelas, lazos, vrtices aislados e indique si G es una grfica

simple.

4

Respuesta:

No tiene aristas paralelas, no tiene lasos, no tiene vrtices aislados y no es un grafo simple porque

tiene un lazo ya que una grfica simple es a que no tienes lazos ni aislados y mltiples.

8. Determine un camino de longitud mnima de V a W en la siguiente grfica, que pase por cada

vrtice exactamente una vez.

A. b a e

B. c a d

Respuesta: El camino corto es el de longitud 21

9. En la siguiente grfica, los vrtices representan ciudades y los nmeros sobre las aristas

representan los costos de construccin de los caminos indicados. Determine el sistema de

carreteras ms barato que una todas las ciudades.

Respuesta:

El sistema de carreteras ms barato que una todas las ciudades es el recorrido de (e,g,f,b,d,c,a) lo cual nos arroja un resultado de 62 por ende para otros recorridos el valor es ms alto .

10. En al grafica del problema 9 determine un circuito de Euler y un circuito de Hamilton.

Circuito de Euler .El que contiene todas las aristas del grafo:

5 Sea G un grafo sin vrtices aislados. Un circuito que contiene todas las aristas de G recibe el nombre

de circuito euleriano. Un circuito euleriano es una trayectoria que empieza y termina en el mismo vrtice

y recorre cada arista exactamente una vez.

Desde el vrtice f a f no admite ningn circuito euclidiano ya que debera de ser los grados de los

vrtices de 2

Circuito de Hamilton. Sea G un grafo conexo con n vrtices, donde n3. Si la suma de los Grados de

cada par de vrtices no adyacentes es mayor o igual a n, entonces G tiene Un circuito hamiltoniano

11. Suponga que un ciclo contiene un lazo. Cul es su longitud?

Respuesta: La longitud de un ciclo con lazo es la suma de su arista que tiene.

12. Puede un ciclo contener dos lazos?

Respuesta:

Si porque no hay estricciones para no poder tener una arista con el mismo vrtice en sus extremo

13. Enumera tres situaciones, en que un grafo pueda ser til.

*su utilidad puede ser muy amplia se lo aplica en divisiones de comunidades o carreteras.

*es una herramienta de gran potencial a la hora de resolver problema como por ejemplo encontrar

rutas ms cortas en carreteras

*organizar la distribucin de mercancas para distribuirlas desde una serie de puntos de almacenaje a

otros puntos de venta.

14. Para el grafo de la figura, determina

a) un camino de b a d que no sea un recorrido;

b) un recorrido b-d que no sea un camino simple;

c) Cuntos caminos simples existen de b a f?

a. b-e-d

6

b. b-c-d

c. 3 caminos de (b-a-c-d-e-f) ,(b-e-f) y (b-c-d-e-g-f) y (b-e-f)

15. Cuntos caminos simples diferentes existen entre los vrtices h y c en el grafo dado en la figura?

Respuesta: Existen 3*2*2*2*2=48;

16. Sea G = (V, E) el grafo no dirigido de la figura, cuntos caminos simples existen en g de e a

h? Cuntos de ellos son de longitud 5?

a. existen 4 caminos simples de (e) a (h);

b. 3 son de longuitud cinco.

17. Para el grafo de la figura

a. Determina un camino para ir de Barcelona a Sevilla

b. Cuntos ciclos tiene?

c. Existe una recorrido en la que puedas visitar todas las ciudades?, si

d. existe, cul?

Respuesta:

a. Barcelona-Zaragoza-Madrid-Jaen-Seviila.

b. 16 ciclos.

c. No porque para que se de este recorrido los vrtices tienen que ser pares y en este caso no lo es.

18. Para el grafo de la figura, determina

7

a. Cuntos ciclos tiene?, cules? 1. a-b-c 2. b-c-d-e 3. a-b-e-d-c 4. e-f-g

b) Traza un camino simple de g a c

1. g-f-e-b-c

19. Cuntos caminos simples diferentes existen entre los vrtices a y c en el grafo dado en la

figura?

Respuesta:

Existen 24 caminos simples ya que 3*2*1*2*2*1*1=24.

20. Dibuja, si existen, grafos con

a. 5 vrtices, 6 aristas y sin ciclos de longitud 3

No imposible:

b. 5 vrtices con grados 0, 5, 1, 3 y 2

A B

NO imposible:

C

D D

8

21. Dibuja, si existen, grafos de cuatro vrtices con los siguientes grados:

a). 2, 2, 2, 3

b). 2, 2, 2, 4

c). 2, 1, 2, 1

22. En el siguiente grafo, los nmeros en las aristas representan los kilmetros

a. v-15-b-4-g-6-h-3-w=28

9

b. v-4-a-10-f-14-w=28 c. v-6-c-13-g-6-h-3-w=28