• Author / Uploaded
• Lenin Sleyter Saavedra Jimenez

Citation preview

INFORMÁTICA

GRAFOS Y COMBINATORIA EJERCICIOS PROPUESTOS

1.- De una solución al problema 1 de grafos eulerianos, justificando su respuesta. 2.- De una solución al problema 2 de grafos eulerianos, justificando su respuesta 3.- Estudiar si los grafos siguientes son eulerianos: K ,k a) El grafo completo 4 5 b) El grafo del cubo c) El grafo de Petersen

4.- Las autoridades actuales de la antigua ciudad de Könisberg han decidido finalmente construir los puentes que sea preciso para satisfacer el antiguo capricho de sus habitantes, ¿Cuántos han de construir como mínimo y dónde es preciso ponerlos?

GRAFO DE PETERSEN

5.- Estudiar si existe un recorrido o circuito euleriano en cada uno de los siguientes grafos. y digrafos

6.- Se denomina grafo molinillo de orden n , Mn v = { 0,1, 2,..., 2n} a un grafo con vértices y aristas A = { { 0, i} :1 �i �2n} �{ { 2i - 1, 2i} :1 �i �n} : Así por ejemplo M 4 sería el grafo adjunto. M a.- Para que valores de n es n euleriano M b.- Para que valores de n admite n un recorrido euleriano. Mn c.- Encontrar los vértices de corte de para todo n M d.- Para que valores de n es n hamiltoniano

1

4

3

2

5

0

1

6

7

8

INFORMÁTICA

GRAFOS Y COMBINATORIA

M e.- Para que valores de n admite n un camino hamiltoniano

7.- a.- Probar que si un grafo G es hamiltoniano entonces es orientable b.- Encontrar un grafo G orientable y no hamiltoniano. c.- Probar que si un grafo G es euleriano entonces es orientable d.- Encontrar un grafo G orientable pero no euleriano 9. Indicar cual de los grafos siguientes tiene un camino o ciclo hamiltoniano

8.- a. Dar un ejemplo de un grafo que contenga, tanto circuitos eulerianos como hamiltonianos. b. Dar un ejemplo de un grafo que contenga un circuito euleriano pero no uno hamiltoniano. 9.- Cuáles de los siguientes grafos son hamiltonianos? a) el grafo completo c) Grafo de Petersen

kn .

k

b) El grafo completo bipartido r , s d) Grafos del tetraedro, cubo y octaedro.

10.- Se considera un grafo que tiene por matriz de adyacencia A Se pide : a. Estudiar si el grafo admite recorridos o circuitos eulerianos y hamiltonianos, en caso afirmativo hallarlos b.- Responder a la pregunta anterior si se añade una arista entre el vértice 3 y el vértice 5

0 � � 0 � � 0 � 1 A=� � 1 � 1 � � 1 � � 0 �

0

0

1

1

1

1

0

0

0

1

1

1

0

0

0

0

1

1

0

0

0

0

1

1

1

0

0

0

0

0

1

1

1

0

0

0

1

1

1

0

0

0

1

1

1

1

0

0

0� � 1� 1� � 1� 1� � 0� 0� � 0� �

11.- Responder a las siguientes preguntas:

K n y para que a. Para que valores de n tiene un recorrido euleriano el grafo completo K valores de n es euleriano el grafo completo n K

b. ¿ Es euleriano 4,6 ? En caso afirmativo, descomponerlo en ciclos simple. c. ¿ Puede un grafo euleriano tener un número impar de aristas? 12.- Las calzadas de un jardín tienen forma de una recua, que representamos como un grafo de

V = { 0,1, 2, .., n}

{ { 0,1} ,{ 0, 2} , ...,{ 0, n} ,{ 1, 2} , ..,{ n - 1, n} ,{ n,1} }

vértices y aristas: . Describir una ruta que comience y termine en el vértice 0 y visite cada vértice una y solo una vez.

2

INFORMÁTICA

GRAFOS Y COMBINATORIA

13.- En el siguiente grafo las aristas representan los vuelos que oferta una compañía aérea entre diversas ciudades: a. Estudiar razonadamente si una misma tripulación puede servir todos los vuelos, sin repetir ninguno volviendo a la ciudad de origen. ¿En caso negativo cuantos vuelos habría que añadir y entre que ciudades para poder subsanar tal eventualidad? Determine por un algoritmo apropiado un itinerario de modo que la tripulación asista todos los vuelos programados en el grafo del dibujo. b. Estudiar si una misma tripulación puede visitar todas las ciudades sin pasar dos veces por la misma volviendo a la ciudad de partida. En caso afirmativo determinar razonadamente un itinerario. En caso negativo, decir cuántos vuelos habría que fletar y entre que ciudades para propiciar tal circunstancia. 14.- Se considera el grafo G(V , A ) siendo son adyacentes si no son primos entre sí.

V = { 2 , 3 , 4 , 6 , 8 , 9 ,10}

, y en el que dos vértices

Graficar G(V , A ) , ¿Es euleriano?,¿ es hamiltoniano? Razónese sus respuestas. 15.- Las calzadas de un jardin tienen la forma de una rueda que representamos como un grafo de

A = { { 0 ,1} ,{ 0 , 2} , ...,{ 1 , 2} , ...,{ n - 1 ,n} ,{ n,1} }

V = { 0 ,1, 2.....,n}

vértices y aristas ,describir un circuito que empiece y termine en vértice 0

16. Demostrar que un grafo con vértices de corte no es hamiltoniano. ¿ Puede admitir un camino hamiltoniano?¿ Existe una limitación en el número de vértices de corte y de aristas puente que puede tener un grafo que admite un camino hamiltoniano? Razonar las respuestas. 17. Responder las siguientes preguntas a. Un grafo bipartito

b.

a.1 Si

K n,m

a.2. Si

K n,m

K n,m

contiene 16 lados, m < n determina n,n tal que:

posee un circuito euleriano pero no hamiltoniano posee un circuito euleriano y un ciclo hamiltoniano

¿Existe un ciclo hamiltoniano en

k 4 ,4

?, ¿ Y en

18.

3

K 4 ,5

? ¿ Y en

K 4 ,6

?

INFORMÁTICA

GRAFOS Y COMBINATORIA

4