Grafos (2017)

Apunte Español
Universidad Universidad Complutense de Madrid (UCM)
Grado Matemáticas y Estadística - 1º curso
Asignatura elementos
Año del apunte 2017
Páginas 7
Fecha de subida 15/07/2017
Descargas 0
Subido por

Descripción

ejercicios resueltos de grafos

Vista previa del texto

Ejercicios de Grafos (Lección 6) 1) Supongamos que el grafo bipartito K m,n tiene 196 aristas.
1.- Halla m y n de modo que K m,n sea euleriano pero no hamiltoniano.
2.- Halla m y n de modo que K m,n sea euleriano y hamiltoniano.
Solución: 1.- m  2  49 y n  2 2.- m  14  n 2) Consideremos el grafo G  V , A  de la figura: Completa: 1.- G es  EULERIANO  NO EULERIANO 2.- El grado de todos sus vértices es  PAR  IMPAR y  v  , v  V 3.- Un circuito euleriano para G es el dado por la secuencia de vértices siguiente: Solución: G es euleriano. El grado de todos sus vértices es 4.
Circuito euleriano: v1 , v2 , v4 , v3 , v4 , v6 , v5 , v2 , v7 , v6 , v8 , v7 , v5 , v3 , v8 , v1 3) Consideremos el grafo bipartito siguiente. Razona por qué G no es hamiltoniano G Solución: Si G fuese un grafo hamiltoniano, habría un circuito de longitud 9, lo que contradice la condición de bipartito.
1 Apuntes descargados de wuolah.com 4) Indíquese cuáles de los siguientes grafos son eulerianos o hamiltonianos.
Solución: Son eulerianos  b  y d  Los circuitos eulerianos son: a b c d e a c e b d a y a b c a d c f b e f d e a respectivamente Son hamiltonianos  a  ,  b  ,  c  , d  y f Los ciclos hamiltonianos son: a b c d a , a b c d e a , a b f e h g d a y a d b e c f a respectivamente 5) ¿Cuáles de los siguientes grafos son eulerianos? a) El grafo completo K 8 b) El grafo bipartito completo K 8, 8 c) El grafo ciclo C8 d) El grafo cúbico Q8 Solución: a) K 8 no es euleriano ya que es regular de grado 7.
b) K 8, 8 es euleriano ya que es regular de grado 8.
c) C8 es euleriano ya que es regular de grado 2.
d) Q8 es euleriano ya que es regular de grado 8.
2 6) Cuáles de los siguientes grafos son hamiltonianos a) K 4, 4 b) El grafo G dado por el siguiente dibujo Solución: a) El grafo K 4, 4 es hamiltoniano b) El grafo G no es hamiltoniano 7) Para qué valores de n los grafos Cn , K n , K n,n y Qn son eulerianos Solución: Los grafos dados son todos conexos, así que sólo debemos observar si todos los vértices tienen grado par. Como, además, esos grafos son regulares basta observar el grado de uno de sus vértices.
Cn es regular de grado 2, luego es euleriano n  3 K n es regular de grado n  1 , luego es euleriano si n es impar.
K n , n es regular de grado n , luego es euleriano si n es par, n  2 .
Qn es regular de grado n , luego es euleriano si n es par, n  2 .
8) Elena y Dora invitan a 10 amigos a cenar. En el grupo de 12 personas, cada una de ellas conoce al menos a otras 6. Demostrar que se pueden sentar los 12 , alrededor de una mesa circular, de modo que todos conozcan a las dos personas que están sentadas a su lado.
Solución: Las 12 personas en la mesa son los vértices de un grafo, en la que dos vértices son adyacentes si las personas correspondientes se conocen.
3 Por el dato de que de todos conocen al menos a 6 personas se sabe que el grado de cada vértice x es   x  6 .
La colocación en la mesa será posible si el grafo posee un ciclo hamiltoniano, pues se desea que cada vértice está entre dos adyacentes.
En este grafo si x e y son dos vértices cualesquiera se cumple que   x     y   6  6  12 Es decir, se verifican las condiciones del teorema de Ore. Por tanto, el grafo es hamiltoniano y los invitados se pueden sentar a la mesa.
9) Dos amigos, Raúl y Laura, tienen pensado ir de vacaciones a la isla de Moral. La figura adjunta representa los lugares interesantes de la isla y las carreteras que los unen. Laura es una turista nata y desea visitar cada lugar una sola vez y volver al punto de partida. Mientras que Raúl es un explorador nato y prefiere atravesar cada carretera una sola vez en cualquier dirección y no le importa empezar y acabar en lugares distintos. ¿Es posible ayudar a los dos amigos a encontrar rutas convenientes a sus intereses? Solución: Laura desea realizar un circuito hamiltoniano, mientras que Raúl desea recorrer una camino euleriano.
Laura no tendrá ningún problema en conseguirlo ya que si se hallan los grados de cada vértice se obtienen los resultados de la tabla siguiente Vértice Grado A 4 B 4 C 5 D 3 E 5 F 5 Por tanto, el grafo es hamiltoniano ya que cumple la condición suficiente del Teorema de Dirac y un posible recorrido para Laura es el siguiente: A-B-C-D-F-E-A Sin embargo, Raúl no podrá conseguirlo porque hay 4 vértices de grado impar y, en consecuencia, no existen caminos eulerianos.
10) Siete personas que asisten a un congreso deberán comer juntas, en una mesa circular, los tres días que dura el congreso. Para conocerse mejor deciden sentarse de modo que cada persona tenga a cada lado a una persona distinta cada día.
¿Pueden llevar a cabo su propósito? ¿Y si el congreso durara 5 días? 4 Solución: Designamos a las personas con las etiquetas 1, 2, 3, 4, 5, 6, y 7. Una colocación en la mesa es un ciclo hamiltoniano en el grafo completo K 7 . Así, para el segundo día la colocación será, de nuevo, un ciclo hamiltoniano pero en el que no se utilice ninguna de las aristas del primer ciclo, para no repetir compañero de mesa. Y para el tercer día se requiere un tercer ciclo hamiltoniano que no tenga ninguna arista común con los ciclos anteriores. Es posible construir estos tres ciclos hamiltonianos: Los ciclos son: 12345671, 1352461 y 14736251 11) a) Demostrar que el conjunto de aristas de K 9 se puede descomponer en 4 ciclos hamiltonianos con todas sus aristas distintas.
b) Demostrar que el conjunto de aristas de K n , n  3, n impar, se puede descomponer en n 1 ciclos hamiltonianos con todas sus aristas distintas.
2 Solución: a) Llamemos a los vértices de K 9 : 0, 1, 2, 3, 4, 5, 6, 7, z y dispongamos los 8 primeros en una circunferencia. Formemos un camino con esos primeros vértices en forma de zigzag como indica la figura: Unimos finalmente los vértices 0 y 4 con el adicional z. Así hemos construido un primer ciclo hamiltoniano en K 9 . Para construir el segundo, giramos el zigzag en el sentido de las agujas del reloj y unimos los vértices 1 y 5 con z, según muestra la figura.
5 Si el ciclo inicial era 01726354z, el segundo se obtiene de éste sumando una unidad módulo 8, es decir, 12037465z.
El proceso se repite para obtener otros dos ciclos hamiltonianos que no tienen ninguna arista en común con los anteriores. Los ciclos son: 23140576z, 34251607z.
Con los 4-ciclos llenamos todas las aristas de K 9 n  n  1 aristas. Cada ciclo hamiltoniano posee n 2 n 1 aristas, luego el número de ciclos de la descomposición debe ser . Para 2 b) El grafo completo K n tiene describir los ciclos usamos la misma técnica que en el apartado anterior.
Nombramos ahora a los vértices con las etiquetas 0, 1, 2, , n  2 , z. Los ciclos serán ahora: n 1 n 1 , , z 2 2 n  3 n 1 1, 2, 0, 3, n  2 ,  , , , z 2 2  0, 1, n  2, 2, n  3,  , n  3 n 1 , ,  , 0, n  2 , z 2 2 Es inmediato comprobar que las aristas no se repiten y como hay queda demostrado.
n 1 ciclos, 2 6 12) Cuestiones 1.- Si G es un grafo bipartito y hamiltoniano, entonces tiene un número par de vértices.
 Verdadero  Falso 2.- Todo grafo simple, regular y bipartito es euleriano  Verdadero  Falso 3.- Si G es un grafo conexo 6-regular con 11 vértices, entonces G es hamiltoniano.
 Verdadero  Falso 4.- Los grafos K n :     Son todos hamiltonianos Son hamiltonianos sólo si n es par Son hamiltonianos sólo si n es impar Ninguno es un grafo hamiltoniano 5.- Los grafos K n , m son eulerianos:    Para cualquier valor de n y m Sólo si n y m son pares Sólo si n y m son impares 6.- Los grafos K n , m son hamiltonianos:    Para cualquier valor de n y m Sólo si n  m Sólo si n y m son de distinta paridad Solución: 1.2.3.4.5.6.- Verdadero Falso Verdadero Son todos hamiltonianos Sólo si n y m son pares Sólo si n  m 7 ...

Tags:
Comprar Previsualizar