caminos eurelianos y hamintonianos
Transcript of caminos eurelianos y hamintonianos
![Page 1: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/1.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 1/37
UNIVERSIDAD NACIONAL DE SAN CRISTÓBAL
DE HUAMANGA FACULTAD DE INGENIERÍA DE
MINAS, GEOLOGÍA Y CIVIL
ESCUELA DE FORMACIÓN PROFESIONAL DE INGENIERÍA
DE SISTEMAS
CAMINOS EULERIANOS Y HAMILTONANOS
DOCENTE : LIC.PULACHE JUAREZ
CURSO : MATEMATICA DISCRETA
SIGLA : MA-142
INTEGRANTE : ÑACARI VALVERDE, AXELL .A
YACHAPA BARRIENTOS, Milan
AYACUCHO – PERU
2015
![Page 2: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/2.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 2/37
INTRODUCCIÓN
En el presente trabajo se abarca dos conceptos básicos de las matemáticasdiscretas: los caminos y circuitos matemáticos, ambos dentro del ámbito de lateoría de grafos; más específicamente nos referiremos a los caminos y circuitoseuclidianos y hamiltonianos.Se define, de manera breve, cada uno de los conceptos nombradosanteriormente, todos con sus respectivos teoremas de existencia y suficiencia;además, para su mejor entendimiento, los acompañaremos con ejemplos clarosy concisos que nos ilustrarán correctamente lo que en realidad significan y
pueden ofrecer al ser aplicados correctamente.
![Page 3: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/3.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 3/37
IMPORTANCIA
La importancia tanto de los circuitos como de los caminos, radica en que nospermiten simular situaciones cotidianas que se presentan a diario en la vida real,por citar algunos ejemplos tendríamos: situaciones relacionadas con transporte,
realización de comunicaciones, asignación de recursos, etc. En ellos podemosasignar valores predeterminados que representen distancia, cantidad o cualquiervariable a estudiar, evitándonos así engorrosos procedimientos que consumiríanmuchos recursos y, sobre todo, tiempo.
MARCO TEÓRICO
CAMINO.- En un grafo, un camino es una sucesión finita en la que aparecenalternadamente vértices y aristas de dicho grafo.
CIRCUITO.- Es un camino cerrado (que comienza y termina en el mismo vértice)que no posee ningún vértice repetido.*EN OTRAS PALABRAS:Sea G = (V , E) un grafo no dirigido. Un camino entre los nodos u y v es unasecuencia e1,e2… en tal que existen nodosx0, x1, x2, . . . , xn que satisfacen lo siguiente: x0 = u y xn = v, y para cada 1 ≤ i ≤ n, ei = (xi−1, xi)
En tal caso, decimos que el camino es de largo n.*Si el grafo es simple podemos denotarlo tan solo poru, x1, x2, . . . , xn−1, v.
Decimos que el camino es un circuito si u = v. Es simple si todos los ei sondistintos.
CIRCUITO EULERIANO.- Un circuito Euleriano en un grafo o multigrafo G es uncircuito que recorre cada arista una y sólo una vez.TEOREMA:Son equivalentes, para G grafo o multigrafo conexo: G es Euleriano. Todo vértice de G tiene grado par. Las aristas de G pueden particionarse en circuitos.
CAMINO EULERIANO.- Un camino Euleriano en un grafo o multigrafo G es un
camino que recorre cada arista una y sólo una vez.TEOREMA:Un grafo o multigrafo conexo tiene un camino Euleriano si y sólo sí todos susvértices tienen grado par salvo dos.CIRCUITO HAMILTONIANO.- Un circuito Hamiltoniano en un grafo G es uncircuito que recorre cada vértice una y sólo una vez.CAMINO HAMILTONIANO.- Un camino Hamiltoniano en un grafo G es uncamino que recorre cada vértice una y sólo una vez.TEOREMA (CONDICIÓN NECESARIA):
![Page 4: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/4.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 4/37
Sea G un grafo conexo. Si existe W ⊂ V tal que G \ W tiene c componentesconexas con c > |W| entonces G no es Hamiltoniano.
TEOREMA (CONDICIÓN SUFICIENTE):Sea G un grafo con n ≥ 3 y tal que para todo v ∈ V se verifica que d(v) ≥ n/2.Entonces G es Hamiltoniano.
*No se conocen condiciones necesarias y suficientes que caractericen de formaconcreta a los grafos Hamiltonianos. Hasta el día de hoy, y a pesar de suestudio, no se llega a una conclusión definitiva.*No se conocen algoritmos polinomiales para determinar si un grafo esHamiltoniano o no (algoritmos de reconocimiento).
Definiciones
Multigrafo Un multigrafo G=(V,E) es una funcion que asigna a cada elemento ede E (ramas) un par no ordenado {u,v} de elementos de V (vertices) quellamamos los extremos de e. Por ejemplo,
Nota: Las ramas b y c tienen los mismos extremos (ramas multiples). Losextremos de la rama f son iguales (bucle).
Grafo Sea V un conjunto finito de elementos que llamamos vertices y sea E unconjunto de pares de vertices que llamamos ramas. Al par G=(V,E) lo llamamosgrafo. Advertimos que un grafo es un multigrafo que no tiene ramas multiples nibucles. Por ejemplo,
Nota: En adelante consideraremos sólo grafos. Cuando se trate de un multigrafo
2 f
e
d
c b
a
34
1 Ea
bcdef
V={1,2,3,4}{1,2}{1,4}{1,4}{3,4}{2,3}{2,2}
34
21
V={1,2,3,4}E={{1,2},{2,3},{3,4},{1,4},{1,3}}
fig .1
fig 2
![Page 5: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/5.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 5/37
lo aclararemos explicitamente.
Adyacente: Si (u,v)E decimos que los vertices u y v son adyacentes.
Tabla de adyacencia de un grafo Es una tabla que asigna a cada vertice u de Gla
lista de ramas que tienen uno de sus extremos en u.
Grado de un vertice El grado de un vertice u, escribiremos grad(u), es el numerode ramas que tienen a u como extremo. Decimos que las ramas inciden en u.
Grafo completo: Si u,vV implica que (u,v)E decimos que G es completo y
escribimos Kn donde n=V. En este caso,E=
2
n . Por ej. la figura 2 es un K4
si se agregara la rama (2,4).
Camino: Una sucesion de vertices u1, u2, ..., up tales que (ui,ui+1)E lo llamamosun camino (que une u1 con up). Si todos los ui son distintos decimos que elcamino es simple. Salvo indicacion en contrario los caminos que consideraremosson simples. Si el camino incluye a todos los vertices de V decimos que elcamino es hamiltoniano.
Circuito o Ciclo Un camino tal que u1,u2,...,up-1 son distintos y up=u1 lo llamamosun circuito o ciclo, es decir, un circuito es un camino cerrado. Si el circuitocontiene todos los vertices de V decimos que el circuito es hamiltoniano. Si Gtiene algun circuito hamiltoniano decimos que el grafo es hamiltoniano.
Dodecaedro: ejemplo de grafo hamiltoniano.
Grafo aciclico Un grafo que no contiene circuitos lo llamamos aciclico.
Grafo Bipartito Un grafo G=(V,E) se llama bipartito si V esta particionado en 2subconjuntos M y N tales que toda rama de E tiene un extremo en M y otro en N.Decimos que G es completo si para todo par uM y vN se tiene que (u,v)E.En este caso escribimos Kmn donde m=M y n=N
3
12
Tabla1 (1,2) (1,3)2 (1,2)3 (1,3)
![Page 6: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/6.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 6/37
Subgrafo Un grafo H se dice que es un subgrafo de G si todos los vertices yramas de H son vertices y ramas de G.
Grafo conexo Un grafo es conexo si u,vV implica que hay un camino que une ucon v. Un subgrafo H conexo y maximal de G se llama una componente de G
Subgrafo inducido Sea U un subconjunto de vertices del grafo G. El grafo Hcuyos vertices son U y tal que (u,v) con u,vU es rama en H si (u,v) es rama enG se llama grafo inducido por U.
Substraccion de vertices o ramas Sea G=(V,E) un grafo y U un subconjunto de Ventonces G-U es el grafo que resulta de G suprimiendo los vertices U y lasramas que inciden sobre los vertices de U. Sea R un subconjunto de E entoncesG-R es el grafo que resulta de G suprimiendo las ramas R.
Grafo dirigido o digrafo Un grafo dirigido o digrafo G=(V,D) esta formado por unconjunto de vertices V y un subconjunto D de pares ordenados de vertices que
llamamos arcos. Por ejemplo,
En un grafo dirigido una sucesion de vertices u1, u2, ..., up tales que (ui,ui+1)E lo
llamamos un camino dirigido. Si u1 =up decimos que es un circuito dirigido. Arbol Un grafo aciclico y conexo se llama arbol.
Arbol con raiz A rooted tree es un grafo dirigido cuyo arbol subyacente es unarbol que tiene un vertice distinguido, raíz, tal que hay un solo camino dirigido dela raiz a cualquier otro vertice.Si uv decimos que u es el padre de v y v es el hijo de u. Si v se encuentra enun camino dirigido a partir de u, decimos que v es descendiente de u. Si noexiste v tal que uv decimos que u es una hoja. Decimos que los hijos de la raiztienen profundidad 1, los hijos de los hijos de la raiz tienen profundidad 2, etc. Lamáxima profundidad de un vertice se llama altura del arbol. Un vertice que no es
una hoja o la raiz se llama vertice interno.Un arbol es m-ario significa que cada vertice tiene m hijos o menos.
Nota: Sea T un arbol m-ario con n vertices y altura h entonces)1/()1(1 1
mmnh h
Nota: El arbol binario completo tiene 2h+1 – 1 nodos (vertices).
34
21
V= {1,2,3,4}E={(1,2),(3,2),(4,3),(1,4),(4,1).(2,4)}
![Page 7: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/7.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 7/37
EjemplosCircuitos EulerianosEn la ciudad de Königsberg habia una isla en medio de un río y 7 puentesdispuestos segun lo que muestra la figura
Se plantea el problema de si es posible recorrer en un camino cerrado todos lospuentes una sola vez c/u. En el multigrafo de la figura 3 se traduce el problemaen hallar una secuencia de ramas que contenga una sola vez a todas las ramasdel grafo. A un tal camino lo llamamos circuito euleriano.
Teorema (Euler)En un multigrafo conexo existe un circuito euleriano sii los grados de todos losvertices son pares.
DemostracionObservamos que un tal circuito debe entrar y salir de cada vertice una o masveces y, por lo tanto, deben incidir en cada vertice un numero par de ramas. Asila condicion enunciada es necesaria. (En el caso de los puentes no se cumple lacondicion).Supongamos ahora que el numero de ramas que inciden en cada vertice es par.Construiremos un circuito euleriano. Sea G el grafo. Elijamos un vertice inicial a yuna rama que sale de a y llega a otro vertice que llamamos b. De b tiene quesalir otra rama que llegará, digamos, a c. De c tiene que salir otra rama...etc. Deesta manera debemos volver eventualmente a a. Hemos construido un circuitocon ramas distintas. Si las ramas R1 de este circuito agotaran las ramas de G elteorema esta demostrado. Si no, consideremos el grafo G-R1 y construyamos un
segundo circuito con ramas R2 en forma analoga. De esta manera construiremosuna secuencia de circuitos Ri cuya union será un circuito euleriano.
ARío
fig 3
![Page 8: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/8.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 8/37
TeoremaEn todo torneo existe un camino hamiltoniano.DemostracionPor induccion. Supongamos tener un camino v1v2...vivi+1...vk (k<n). Sea zun vertice distinto de los k vertices. Si para algún i=1,2,...,k-1 se tuviera
vizvi+1 podemos agregar z extendiendo el camino a k+1 vertices. Quedan 2casoszv1 con lo cual podemos extender el camino por la izquierdav1z, v2z,...,vn-1z, vkz. Pero vkz permite extender el camino por laderecha
Definiciones equivalentes de arbolTeoremaLas siguientes afirmaciones son equivalentes1) T es un conexo y no tiene ciclos (definicion original)2) T es conexo y todo e desconecta a TMostramos que T no tiene ciclos. Si tuviera un ciclo C eC no desconectaria
3) Cualesquiera u,vT son conectados por un solo camino.Si hubiera 2 caminos habria un ciclo y los e del ciclo no desconectarian a T4) T no tiene ciclos y si e es un nuevo edge el grafo T+e tiene un solo ciclo.Si T tuviera un ciclo C y (u,v) perteneciera a C dos caminos distintos conectariana u y v. Por tanto no hay ciclos. Si (u,v) no pertence a T al agregarlo a T (u,v)mas el camino de u a v forman un ciclo.4)1) Hay que demostrar que T es conexo. Sea C el ciclo que se forma alagregar (u,v). Entonces C\(u,v) es un camino que une a u con v T es conexo
GRAFOS
1. La matriz de adyacencia del grafo G es
R 1R 3
R 2
![Page 9: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/9.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 9/37
1110
1101
1011
0111
entonces,A) G es un pseudografoB) G es un grafo completo
G no es conexoSolución : Supongamos V={v 1,v 2 ,v 3,v 4 } son los vértices del grafo. En los
pseudografo están permitidas las aristas cuyos extremos coinciden, es decir, loslazos.En la matriz de adyacencia dada se observa quem11=1, un lazo en v 1m22 =1, un lazo en v 2m33=1, un lazo en v 3m
44=1, un lazo en v
4Se trata de un pseudografo.
2. Sea A la matriz de adyacencia de un multigrafo G con vértices {v1, v2,...,vn} ysea a23=3 una de las entradas de A. Entonces,
A) Existe un camino con tres vértices entre v2 y v3.B) Hay tres aristas con extremos los vértices v2 y v3.C) Hay tres vértices adyacentes con v2 y v3
Solución : en los multigrafos se define la matriz de adyacencia:
aij =número de aristas cuyos vértices son v i y v j , i jaii =0Por tanto si a23=3 entonces hay 3 aristas con vértices extremos v 2 y v 3
3. Sea G un grafo con 7 vértices y C=(v1,v3,v2,v4,v5,v7,v6,v1) un camino en G. A) C es un camino hamiltoniano
C es un ciclo hamiltonianoB) C no está bien definido
Solución : dibujando el subgrafo asociado al camino
Vemos que se trata de un ciclo hamiltoniano.Ciclo es un camino cerrado donde los únicos vértices repetidos son el primero yel últimoCuando un ciclo contiene todos los vértices del grafo se llama ciclo hamiltoniano.Nuestro grafo contiene siete vértices, y el camino en cuestión los recorre todossin repetir vértice, es por tanto ciclo hamiltoniano.
v1v2
v3
v4v5
v6
v7
![Page 10: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/10.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 10/37
4. Dado el grafo de la figura
A) Es hamiltonianoB) Es euleriano
Es bipartitoSolución : el subgrafo de la figura siguiente contiene un ciclo hamiltoniano
Un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano.No es euleriano porque hay seis vértices que tienen grado 3, es decir gradoimpar. Recuérdese que si un grafo es euleriano todo vértice tiene grado par.No es bipartito porque el ciclo asociado a la figura anterior es de longitud impar.
5. Sea G un grafo conexo cuyos vértices son {v1, v2, v3, v4, v5}. La sucesión(v1,v2,v3,v5,v1,) es:
A) Un camino eulerianoB) Un ciclo hamiltonianoC) Ninguno de los anteriores
Solución : el subgrafo asociado al camino es elde la figura.
Un camino euleriano es un camino que contiene todaslas aristas apareciendo cada una de ellas exactamenteuna vez.En nuestro caso desconocemos todas lasaristas del grafo, no podemos asegurar que seaeuleriano.Tampoco es un ciclo hamiltoniano, puesto quedebe pasar por todos los vértices sin repetir repetir ninguno.
6. Sea M un mapa cuyas regiones se pueden colorear con sólo dos colores:A) El pseudomultigrafo dual es bipartitoB) Todas las caras son polígonos con un número par de lados.
C) No existen tales mapas.Solución : veamos dos ejemplos de tales mapas
Ambos mapas se pueden colorear con dos colores.
v1v2
v3
v4v5
![Page 11: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/11.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 11/37
Entendiendo que “caras” se refiere a “regiones”, el grado de las regiones internases 3 y 4 respectivamente.Si un mapa se puede colorear con dos colores, regiones adyacentes tendránasociados colores diferentes; manteniendo la misma coloración para las regionesque para las aristas asociadas por la transformación dual, las aristas conectaranvértices que provienen de regiones adyacentes y por tanto tendrán distintos
colores.
7. Dado el digrafo etiquetado
¿Cuál es la distancia entre x e y? A) B) 5 C)12
Solución : siguiendo el algoritmo de Dijkstra y colocando en cada vértice ladistancia desde x, obtenemos:
8. Dadas las matrices de adyacencia A, B y C de tres grafos
0111
1011
1101
1110
;
0101
1001
0001
1110
;
0110
1010
1101
0010
C
B A
A) A y B son isomorfosB) A y C son isomorfos
1
1
113
2
7 2
2 2
x
1 2
0
4
2
3
5
![Page 12: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/12.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 12/37
C) B y C son isomorfosSolución : el grado de un vértice se obtiene sumando los elementos de la fila.Matriz A: gr(v 1 )=1; gr(v 2 )=3; gr(v 3 )=2; gr(v 4 )=2Matriz B: gr(v 1 )=3; gr(v 2 )=1; gr(v 3 )=2; gr(v 4 )=2Matriz C: gr(v 1 )=3; gr(v 2 )=3; gr(v 3 )=3; gr(v 4 )=3No se puede establecer un isomorfismo entre A y C, ni entre B y C, puesto que
no se pueden hacer corresponder los grados de los vértices.Entre A y B se puede establecer el isomorfismo:
Donde las líneas de puntos indica la corresponden-cia entre los vértices.Se observa que se conserva el grado de los vértices por el isomorfismo.
9. ¿Cuál de los siguientes grafos no se puede dibujar sin levantar el lápiz delpapel y sin dibujar dos veces la misma arista?
A) B)
C)
Solución : para resolver este ejercicio hay que analizar el grado de cada vértice.Para que se pueda dibujar en las condiciones pedidas debe ocurrir una de:- Todos los grados son pares, entonces es un grafo euleriano, es decir, admite
un circuito euleriano.- Dos y exactamente dos vértices tienen grado impar, entonces se podría
dibujar un camino eulariano que parta de uno de los vértices de grado impary termine en el otro.
Grafo A:
Admite un camino euleriano, partiendo de uno de los vértices señalados por unaflecha y terminando en el otro
Grafo B:
v1 v2
v3 v4
v1 v2
v3 v4
Grafo A Grafo B
2
4
4
3
3
2
3
3
4
4
2
![Page 13: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/13.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 13/37
Igual situación que en el grafo A.
Grafo C:
Tiene más de dos vértices con grado impar, luego no admite camino euleriano yno se puede dibujar sin levantar el lápiz del papel y sin dibujar dos veces lamisma arista
10. Dado un grafo con matriz de adyacencia
01101
10101
11010
00101
11010
A) El grafo es eulerianoB) El grafo es conexo
C) Es un multigrafoSolución : considerando el conjunto de vértices V={v 1,v 2 ,v 3,v 4,v 5 } yrepresentando el grafo asociado a la matriz, tenemos:
El grafo es visiblemente conexo, es decir, todos sus vértices están conectados através de un camino.
Un multigrafo es un grafo con (posiblemente) varias aristas entre dos vértices. Elque arriba vemos no es multigrafo (propiamente).Tampoco es euleriano porque tiene 4 vértices con grado impar y por tanto noadmite un circuito euleriano.
11. Sea Kn el grafo completo con n vértices, n par, n3.A) Kn es hamiltonianoB) Kn es euleriano
3
3
3
5
3
4
3
4
4
v1 v2
v3
v4 v5
![Page 14: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/14.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 14/37
C) Kn es bipartitoSolución : dos ejemplos de grafos completos nos permiten decidirnos por una delas tres opciones:
Ambos grafos completos son Hamiltoniano, basta escoger el ciclo: (v 1,v 2 ,v 3 ) enK 3 y (v 1,v 2 ,v 3,v 4 ) en K 4 K 3 es euleriano, pero K 4 no lo es.Ni K 3 es bipartito, ni K 4 no lo es.En general K n es hamiltoniano.En general K n no es bipartito, porque tres vértices están conectados entre sí yforman un ciclo de grado impar.En general K n para n par y n>2 no es euleriano, porque todos los vértices tienengrado n-1(impar ).
12. Sea M la matriz de adyacencia de un grafo con p>1 vértices. Sea C=Mp+Mp-1+...+M
A) Si C0 entonces el grafo es conexo.B) Si la entrada i,j de C es igual a 1 entonces existe una arista entre el
vértice i y el j en el grafo.C) Si el grafo es conexo entonces todas las entradas de C son no nulas.
Solución:Recordando la teoría: Si M es la matriz de adyacencia de un grafo, el elemento(i,j) de Mn nos da el número de caminos de longitud n con extremos vi y v j.Existirá un camino entre vi y v j si la entrada (i,j) de la matriz C=Mp+Mp-1+...+M esno nula.En C estarían reflejados todos los posibles caminos de longitudes: 1, 2, 3,...,p
El grafo es conexo si y sólo si todas las entradas de C son no nulas . Esto nosindica que la respuesta C) es correcta.Para ver que las otras respuestas son falsas, buscaremos ejemplos adecuados
Ejemplo 1: sea el grafo con tres vértices de la figura
La matriz de adyacencia es:
000
001
010
M
000
010
0012
M
000
001
0103
M
Por tanto:
000
012
021
23 M M M C
k 4k 3
v1
v2v3
v1 v2
v3v4
v1
v2
v3
![Page 15: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/15.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 15/37
000
000
000
C y no es conexo.
Ejemplo2: sea el grafo de la figura
En este caso:
001
001
110
M
110
110
002
2 M
002
002
220
3 M
Por tanto:
113
113
33223
M M M C
c23=1, pero no existe una arista de v2 a v3.
13. Sea G un grafo y M un mapa con #R regiones que representa a G.Supongamos que el grado de todos los vértices de G es 4 y que G tiene 14aristas. ¿Cuál de las siguientes afirmaciones es cierta?A) #R=9B) #R=12
C) #R=10Solución : aplicando el primer teorema de la teoría de grafos:
p
ii E v gr
1
·#2)(
En nuestro caso: #E=14, gr(v i )=4 para cualquier i.
El primer miembro es:
p
ii V v gr
1
·#4)(
El segundo miembro es: 2·#E=2·14=28Donde:- #E es el número de aristas
- #V el número de vértices- gr(v i ) es el grado del vértice iResumiendo el primer teorema:
4·#V=28 #V=7 Aplicando ahora la fórmula de Euler
#V - #E + #R =2
se obtiene: 7-14+#R=2 #R=9
v1
v2
v3
![Page 16: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/16.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 16/37
14. Los dos grafos de la figura
A) Son isomorfos pues tienen el mismo número de vértices y de aristas.B) Son isomorfos porque se puede establecer un isomorfismo entre ellosC) No son isomorfos pues en uno hay dos vértices de grado 2 y en el
otro hay tres vértices de grado 2.Solución : analizando los grados de los vérticesGrados del grafo 1º: 2, 3, 4, 2, 3, 4Grados del grafo 2º: 2, 4, 2, 4, 2, 4Si existiera un isomorfismo se tendría que conservar el grado de los vérticesisomorfos.
Dado que no se pueden hacer corresponder biunívocamente los vértices degrado 2 (por ejemplo), no puede existir un isomorfismo.
15. Sea el mapa M de la figura
A) M se puede colorear con tres colores diferentes.B) M necesita más de tres colores para ser coloreado.C) Son necesarios más de cuatro colores para colorear M.
Solución : según el teorema de los cuatro colores, como máximo son necesarioscuatro colores para colorear un mapa.Las tres regiones internas de nuestro mapa necesitan tres colores distintos, dadoque están en contacto entre sí.Como cada una de estas regiones internas toca a tres más va a ser necesarioun color más para colorear el mapa.Una solución con cuatro colores sería:
4
2
4
12
3
1
41
3
![Page 17: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/17.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 17/37
16. Dado el grafo G con matriz de adyacencia
01101
10100
11011
00101
10110
A) G tiene un camino eulerianoB) G no es conexoC) G tiene un vértice de grado 5
Solución :
A partir de la representación gráfica vemos que es conexo.Los grados de los vértices son respectivamente: 3,2,4,2,3; como hayexactamente dos vértices con grado impar, admite un camino euleriano.Ninguno de los vértices puede tener grado 5.
17. Los grafos de la figura, ¿son isomorfos?
A) No, porque uno es plano y el otro noB) Sí, pues existe un isomorfismo entre ellos.C) Sí, porque tienen el mismo número de vértices y aristas.
Solución : son isomorfos puesto que se puede establecer un isomorfismo.La correspondencia a través de los números:
produce el mismo grafo G=(V,E), donde:V={1,2,3,4,5,6,7,8,9,10}E={12,19,16,24,23,3A,35,48,47,57,56,68,79,8A,9A}Se trata de un isomorfismo.
18. En el grafo de la figura sea L(vi) la longitud del camino más corto entre losvértices u y vi
63
1 2
1
21 1
2 v1v4
u
v1 v2
v3
v4
v5
11
2 2
3
3
4
56 79
![Page 18: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/18.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 18/37
Entonces: A) L(v4)=6 y L(v2)=2 B) L(v3)=4 y L(v4)=6B) L(v3)=3 y L(v4)=5
Solución : siguiendo el algoritmo de Dijkstra y colocando L(v i ) en cada vérticetenemos:L(v 1 )=1L(v 2 )=2L(v 3 )=3L(v 4 )=5
19. Dado un grafo con matriz de adyacencia
01101
10101
11010
00101
11010
A) El grafo es eulerianoB) El grafo es conexoC) Es un multigrafo
Solución : gráficamente tenemos
Es conexo, dado que no hay ningún vértice aislado de los demás.No es euleriano porque los grados de los vértices son: 3, 2, 3, 3, 3. (Para quesea grafo euleriano tienen que ser todos los grados pares).
No es multigrafo porque no hay todos los números que aparecen son 0 ó 1. Paraque sea multigrafo propiamente deben existir más un número superior a 1,indicando con ellos que dos vértices se conectan con más de una arista.
20. Sea Kn el grafo completo con vértices, n par, n3, entonces A) Kn es hamiltonianoB) Kn es eulerianoC) Kn es bipartito
2 3
15
0
v1 v2
v3
v4
v5
![Page 19: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/19.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 19/37
Solución: Todo grafo completo es hamiltoniano, siempre existirá el ciclo (v 1, v 2 ,v 3,..., v n,v 1 ), dado que cualquier pareja de vértices está conectados por unaarista.Todo grafo completo de n vértices, con n pary n>2, no es euleriano, porquecada vértice tendrá grado (n-1), que es impar, y por tanto no admite circuitoeuleriano.
Todo grafo completo con n>2, no puede ser bipartito, porque tiene ciclos delongitud impar, concretamente tres puntos cualesquiera forman un ciclo delongitud 3:
21. a M la matriz de adyacencia de un grafo con p>1. Sea C=Mp+Mp-1+...+M A) Si C0 entonces el grafo es conexoB) Si la entrada (i,j) de C es igual a 1 entonces existe una arista entre los
vértices i y j.C) Si el grafo es conexo entonces todas las entradas de C son no
nulas.Solución : es similar al ejercicio 12
22. ¿Cuál es el número de veces que se debe levantar el lápiz para dibujar lafigura siguiente sin repetir ninguna arista?
A) Ninguna vezB) Una vezC) Dos veces
Solución : los grados son:
Al haber más de exactamente dos grados impares tendremos que levantar ellápiz al menos una vez.Si eliminamos la línea vertical central, tendremos
vkvk
vi
333
444
6
444
4443
332
442
4
42
44
24
![Page 20: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/20.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 20/37
Este se podrá dibujar sin levantar el lápiz desde un vértice de grado impar hastael otro de grado impar.Luego se levanta el lápiz y se dibuja la línea vertical, con lo que se completa elgrafo.
23. Sea el grafo de la figura
A) Es planoNo es plano
B) No es bipartitoSolución : es fácil ver que es bipartito
Como es conexo, si fuera plano debería cumplir la desigualdad: #E 2·#V-4En nuestro caso: #E=16, #V=8 y #E>2·#V-4Luego no puede ser plano.
24. Dado el grafo etiquetado
1
1
1
1
0
0
00
s
a
c d
b
t
18
15
7
28
9
1410
6
36
![Page 21: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/21.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 21/37
Se aplica el algoritmo de Dijkstra partiendo del vértice s. Se designa por (s,w) la distancia entre s y cualquier otro vértice w. ¿Cuál de los siguientes resultadoses cierto?
A) (s,a)=18, (s,b)=27, (s,c)=15, (s,d)=22, (s,t)=55.B) (s,a)=18, (s,b)=27, (s,c)=15, (s,d)=22, (s,t)=57.C) (s,a)=18, (s,b)=29, (s,c)=15, (s,d)=22, (s,t)=57.
Solución : aplicando Dijstra tenemos las distancias:
Con lo que:
(s,a)=18 (s,b)=27 (s,c)=15
(s,d)=22 (s,t)=55
25. Dados los grafos de la figura
A) No son planosB) Son isomorfosC) No son isomorfos
Solución : ambos grafos son visualmente planos (mapas: las aristas solo secruzan en los vértices).
Los grados de los vértices del primer grafo son:
2, 4, 3,4, 4, 4, 3Los grados de los vértices del segundo grafo son:4, 3, 3, 4, 2, 4Un isomorfismo podría ser:
Para ambos quedaría:
G=(V,E)V={1,2,3,4,5,6}E={16,15,62,52,65,63,54,24,23,34}
26. Sea G un grafo y A su matriz de adyacencia. ¿Cuál de las siguientesinformaciones dan los elementos de la diagonal principal de la matriz A?
A) Los grados de los vértices G.B) Los ciclos con a lo más dos aristasC) Ninguna de las anteriores
s
18
15 22
27
55
1
6 3
45
1
2
3 42
6 5
![Page 22: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/22.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 22/37
Solución : en los grafos la diagonal son elementos nulos porque no hay lazos, esdecir aristas con origen y extremo en el mismo vértice.En los pseudografos están permitidos los lazos.En los pseudografos, por tanto, en la diagonal deben haber elementos no nulos.La definición de matriz de adyacencia para multigrafos y pseudografos viene
propuesta en el problema 5 (página 167 del libro base).
En esencia el elemento mij debe reflejar el número de aristas que hay entre elvértice v i y v j .En los pseudografos afecta a la diagonal principal y a los multigrafos afecta a loselementos que no se limitan a ser 0 y 1. As-i, m ij =3 nos indicaría que existen 3aristas que unen los vértices v i y v j .
27. Sea G el grafo de la figura
A) G es hamiltonianoB) No tiene un camino simple que pase por todos los vértices
No es hamiltonianoPistas : Es fácil encontrar un camino simple que pase por todos los vértices.Hay, por tanto, que decidir si es o no hamiltoniano.Supongamos que es hamiltoniano, entonces si eliminamos k vértices y susaristas no deben obtenerse más de k componentes conexas.También podemos intertar buscar eun ciclo hamiltoniano.Véase al final de este documento
28. ¿Cuál de las siguientes afirmaciones sobre los grafos de la figura es cierta
A) B y C tienen un camino eulerianoB) A es eulerianoC) A tiene un camino euleriano y B un circuito euleriano.
Solución : analizamos los grafos por separado.En A hay dos vértices de grado impar, no es grafo euleriano pero admite un
camino euleriano.En B todos los vértices son de grado par, luego es una grafo euleriano.C tiene más de dos vértices con grado impar, luego no es euleriano ni admitecamino euleriano.
29. Dadas las matrices de adyacencia de los grafos A, B y C siguientes:
A BC
![Page 23: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/23.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 23/37
;
0011
0011
1101
1110
;
0101
1001
0001
1110
B A
0111
1000
1001
1010
C
A) A y B son isomorfosB) A y C son isomorfosC) B y C son isomorfos
Solución : analizando los grados tenemosGrafo A: 3,1,2,2
Grafo B: 3,3,2,2Grafo C: 2,2,1,3De ser isomorfos los serán A y C.
30. Sea K6 el grafo completo con 6 vértices, entonces: A) Es bipartito ya que tiene un número par de vérticesB) Es hamiltonianoC) Es euleriano
Solución : K 6 Es hamiltoniano como todos los grafos completos.No es euleriano porque todos seis vértices son de grado 5 (impar).No esa bipartito porque tiene ciclos de longitud impar (3, por ejemplo).
31. Consideremos el grafo G de la figura:
A) El grafo no es plano porque dos aristas se cortan.B) El grafo no es plano porque todo vértice es de grado 3.C) El grafo es plano
Solución : Es plano porque es isomorfo al mapa
![Page 24: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/24.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 24/37
32. Sea el grafo completo Kr (r>2). Entonces Kr es bipartito.A) No, cualquiera que sea r.
B) Sí, para todo valor de r.C) Sólo si r es par.
Solución : no puede ser bipartito, cualquiera que sea r, dado que paracualesquiera tres vértices v i , v j , v k podemos encontrar el ciclo de longitud 3:
Recordamos el teorema: “Un grafo es bipartito si y solo si no t iene ciclos conlongitud impar”
33. Cuál de estas afirmaciones es falsa:A) Todo grafo tiene un número impar de vértices de grado par.B) Todo grafo tiene un número par o cero de vértices de grado impar.C) La suma de los grados de los vértices de un grafo es par.
Solución : según el primer teorema la suma de todos los grados de los vérticestiene que ser par (proviene del hecho de que cada arista se cuenta dos veces).Por tanto, el número de vértices con grado impar tiene que ser par.En el ejemplo:
tenemos los siguientes grados: 3,2,2,3Tiene por tanto 2 vértices de grado par.
34. Sea el grafo completo Kr (r>1). Su matriz de adyacencia es: A) aii=1, aij=1 (i distinto de j)B) aii=1, aij=0 (i distinto de j)C) aii=0, aij=1 (i distinto de j)
Solución: analizamos
aii =1 tiene lazos y por tanto es un pseudografo
aij =0 no tiene arista entre los vértices v i y v j
Por tanto, en un grafo completo- no hay lazos aii =0
- toda pareja de vértices están conectados aij =1 (i j)
35. Sea el grafo de la figura:
vi
vk v j
![Page 25: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/25.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 25/37
A) El grafo es eulerianoB) El grafo es 3 regularC) El grafo es hamiltoniano
Solución :Los grados de los vértices son: 3, 3, 3, 3, 3, 3, 2 luego no puede ser grafoeuleriano.Un grafo es k-regular si todos los vértices tienen el mismo grado k.Evidentemente hay un vértice que no es de grado 3, luego no puede ser 3-regularEs hamiltoniano puesto que el camino cuyo subgrafo:
es un ciclo hamiltoniano, pues es un camino cerrado, pasa por todos los vérticesy no repite ninguno.
36. En el mapa de la figura las regiones que se designan por R i:
el grado de la región R2 es: A) 8B) 10C) 5
Solución : Se denomina gradode una región a la longitud del camino que labordea.
Poniendo nombre a los vértices
R 1
R 2
R 3 R 4R 5
R 1
R 2
R 3 R 4R 5
v1 v2
v3 v4
v5 v6
v7 v8
![Page 26: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/26.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 26/37
El camino que bordea R 2 es:
(v 1, v 2 , v 3, v 4, v 1, v 5 , v 6 , v 7 , v 8 , v 5 , v 1 )luego la longitud es 10
37. Sea K6 el grafo completo con 6 vértices, entonces: A) Es bipartito ya que tiene un número par de vértices.B) Es hamiltonianoC) Es euleriano
Solución : K 6 tiene 6 vértices, el grado de cada vértice es 5, porque existe unaarista por cada pareja de vértices.Si los vértices son { v 1, v 2 , v 3, v 4, v 5 , v 6 } los grados son: 5, 5, 5, 5, 5, 5No puede ser euleriano, para que lo fuera tienen que ser todos los grados
pares.
No es bipartito porque de tres vértices se puede obtener un ciclo de grado 3(impar).Es hamiltoniano porque el camino:(v 1,v 2 ,v 3,v 4,v 5 ,v 6 ,v 1 )
es un ciclo hamiltoniano.
38. Los dos grafos de la figura
A) Son isomorfos pues tienen el mismo número de vértices y de aristas.B) Son isomorfos porque se puede establecer un isomorfismo entre ellos.C) No son isomorfos pues en uno hay dos vértices de grado 2 y en el
otro hay tres vértices de grado 2.Solución : los grados de ambos grafos sonGrafo 1º: 2,3,4,2,3,4Grafo 2º: 2,4,2,4,2,4Si hubiera un isomorfismo tendría que correspon-derse biyectivamente igualesgrados. Así por ejemplo, los vértices de grado dos no se pueden asociarbiyectivamente, porque en una hay 2 y en el otro grafo hay 3.
39. Sea Kn el grafo completo con n>3 vértices, n par:
v1 v2
v3
v4 v5
v6
K 6
![Page 27: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/27.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 27/37
A) es eulerianoB) es bipartitoC) es hamiltoniano
Solución : este es un ejercicio que ha aparecido en varias ocasiones. Engeneral, para cualquier n>2 tenenmos:- K n es hamiltoniano
- K n es euleriano si n es impar, no lo es si n es par.- K n no es bipartito
40. La matriz de adyacencia del grafo G es
1110
1101
1011
0111
A) G es pseudografo
B) G es un grafo completoC) G no es conexoSolución : dado que tiene en los elementos de la diagonal un 1, hay lazos encada vértice, por tanto es un pseudografo.No es completo porque, por ejemplo, m14=0 y por tanto no hay arista entre v 1 yv 4.Es conexo porque el camino (v 1,v 2 ,v 4,v 3,v 1 ) recorre todos los vértices, y dichocamino es posible porque:
m12 =1 v 1 v 2m24=1 v 2 v 4m43=1 v 4 v 3m31=1 v 3 v 1
41. Sea A la matriz de adyacencia de un digrafo con {v1, v2, v3,...,v7} vértices, ysea a14=3, una de las entradas de la matriz A2.
Entonces: A) Hay un camino entre v1 y v4 con tres vértices intermedios.B) Hay tres caminos de longitud 2 de v1 a v4.C) Hay tres aristas distintas que unen v1 y v4.
Solución : la entrada a14 de A2 es el número de caminos de longitud 2 conextremos v 1 y v 4. Como es un digrafo, y por tanto las aristas están orientadasdichos caminos de longitud 2 tienen origen en v 1 y extremo en v 4
42. Sea G un grafo (no pseudografo ni multigrafo) plano conexo con 15 aristas.
Entonces el número de vértices de G es como mínimo A) 5 B) 7 C) 9Solución : si es un grafo plano conexo debe cumplirse
#E 3·#V – 6 con #V>2(Tal aspecto teórico puede consultarse en la página 174 del libro base)
Es decir: 15 3·#V – 6 #V 7
43. Sea el grafo de la figura:
![Page 28: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/28.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 28/37
A) Es bipartitoB) No es bipartito ya que todos los vértices tienen el mismo gradoC) Es euleriano ya que todos los vértices tienen el mismo grado.
Solución : es bipartito dado que se puede colorear con dos colores.
No es euleriano porque los grados de los vértices no son todos pares.
44. Sea G un grafo y M un mapa con r regiones que representa a G. Si el gradode todos los vértices es 5 y G tiene 20 aristas, entonces r es
A) 12B) 14C) 18
Solución : aplicamoe el primer teorema de grafos y la fórmula de Euler.La suma de todos los grados de los vértices es:5·número de vértices=5·#VTiene que coincidir con el doble de aristas
5·#V=2·20=40 #V=40/5=8La fórmula de Euler: #V - #E + #R = 2 Es decir: 8- 20 +r=2 r=14
45. Sea G el grafo formado por los vértices y aristas de un tetraedro T más elcentro de T y las aristas que unen dicho centro con los vértices de T.Entonces:
A) G es bipartitoB) G es eulerianoC) G no es hamiltoniano
Solución :Se trata de un grafo completo K 5 , por tanto
- G no es bipartito, porque tiene ciclos de longitud impar- G es euleriano porque el grado de cada uno de los vértices es 4 (todos par)- G es hamiltoniano porque el camino (v 1,v 2 ,v 3, v 4, v 5 , v 1 ) existe y es un ciclo
hamiltoniano.
46. Sea el mapa de la figura
![Page 29: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/29.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 29/37
Teniendo también en cuenta la región exterior para colorear el mapa se necesita A) 2 colores
B) 3 coloresC) 4 colores
Solución :
Se necesitan 3 colores mínimo.
47. Sea el mapa M de la figura
A) M se puede colorear con tres colores diferentesB) M necesita cuatro colores para ser coloreado.C) Son necesarios más de cuatro colores para colorear M.
Solución : véase el ejercicio 15
48. En el grafo de la figura sea L(v i) la longitud del camino más corto entre losvértices u y vi
A) L(v4)=6 y L(v2)=2B) L(v3)=3 y L(v4)=4C) L(v3)=2 y L(v4)=3
Solución :L(v 2 )=1 siguiendo el camino (u(1)v 2 )L(v 3 )=2 siguiendo el camino (u(1)v 2 (1)v 3 )L(v 4 )=3 siguiendo el camino (u(1)v 2 (1)v 3(1)v 4 )Recordamos, L(v i ) se forma con los recorridos más cortos.
49. Dado el grafo G con matriz de adyacencia:
61
v1
31
2
2
2 1
1
1v2
v4
v3
u
1
12
23
![Page 30: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/30.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 30/37
01101
10100
11011
00101
10110
A) G tiene un camino eulerianoB) G no es conexoC) G tiene un vértice de grado 5
Solución :Los grados de los vértices se obtiene sumando los números de las filas: 3, 2, 4,2, 3. Ninguno es de grado 5.Tiene un camino euleriano: (v 1(m12 =1)v 2 (m23=1)v 3(m34=1)v 4(m45 =1)v 5 (m51=1)v 1 )Por tanto es conexo.
50. Teniendo en cuenta la región exterior ¿cuántos colores son necesarios para
colorear las regiones del mapa?
A) TresB) Cuatro
C) CincoSolución :
Son necesarios al menos 3 colores.
51. El grafo formado por los vértices y aristas de la figura anterior es A) Euleriano
B) BipartitoC) Ninguno de los dos
Solución :No puede ser euleriano porque hay vértices de grado impar.No puede ser bipartito porque hay ciclos de longitud (3) impar.
52. La matriz de adyacencia de un grafo G es:
11
1
2
2
3
![Page 31: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/31.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 31/37
1110
1101
1011
0111
A) G es un pseudografoB) G no es conexoC) G es un grafo completo
Solución :Dado que en la diagonal principal hay unos, significa que hay lazos, es decir, setrata de un pseudografo.Existe el camino (v 1,v 2 ,v 4,v 3,v 1 ) porque:m12 = m24= m43= m31= 1Es conexo porque (v 1,v 2 ,v 4,v 3,v 1 ) es un camino que recorre todos los vértices,
por tanto están conectados
53. Sea el grafo con matriz de adyacencia:
0111
1010
1101
1010
El número de caminos distintos de longitud tres entre dos vértices v1 y v4 es A) 5B) 3C) 2
Solución:
54. El grafo que tiene por matriz de adyacencia
0111
1010
1101
1010
es: A) Un pseudografoB) Tiene un camino eulerianoC) Tiene un circuito euleriano
Solución : su representación gráfica esv1
v2
v3 v4
![Page 32: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/32.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 32/37
No es pseudografo porque la diagonal está formada por ceros y por tanto no haylazos.Contiene un camino euleriano (v 2 ,v 3,v 4,v 2 ,v 1,v 4 )
No admite circuito euleriano porque hay vértices con grado impar.
55. Sea K5 el grafo completo de cinco vérticesA) Es eulerianoB) Es bipartitoC) Es un pseudografo
Solución : una representación gráfica es
Es euleriano dado que es conexo y todos los vértices tienen grado par.No es bipartito porque tiene ciclos de longitud 3 y ciclos de longitud 5 (impar).No es pseudografo poruqe no tiene aristas con origen y extremo el mismovértice.
56. Sea G un grafo y A su matriz de adyacencia. ¿Cuál de las siguientes
informaciones dan los elementos de la diagonal principal de la matriz A2
? A) Los grados de los vértices de GB) Los ciclos con a lo sumo dos vérticesC) Ninguna de las anteriores
Solución : recordamos la teoria.La entrada (i,j) de la matriz M n es el número de caminos de longitud n conextremos v i y v j .En nuestro caso el elemento (i,i) de la diagonal de A2 es el número de caminosde longitud 2 con extremos v i y v i . Como el origen y el extremo coinciden, se tratade ciclos de longitud 2.
57. Dado el grafo de la figura:
A) Es bipartitoB) Es hamiltoniano
v1 v2
v3 v4
![Page 33: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/33.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 33/37
C) Es eulerianoSolución : contiene un ciclo hamiltoniano
No es euleriano porque es conexo y tiene vértices de grado impar.No es bipartito porque tiene ciclos de grado impar (como el representado)
58. Sea G un grafo y M un mapa con r regiones que representa a G.Supongamos que el grado de todos los vértices de G es 4 y que G tienen 14aristas. ¿Cuál de las siguientes afirmaciones es cierta?
A) r=12B) r=10C) r=9
Solución: aplicamos el primer teorema y la fórmula de Euler.
Primer teorema: 4·#V=2·14 #V=7Fórmula de Euler: 7-14+r=2 r=9
59. Sea G un grafo con n vértices y sea S la suma de los grados de los vérticesde G. Entonces:
A) S es parB) S es imparC) La paridad depende de n
Solución : según el primer teorema, la suma de los grados de los vértices esexactamente el doble de aristas que hay, por tanto debe ser par.
60. Sea G el grafo formado por los vértices y aristas de un cubo C más el centro
de C y las aristas que unen dicho centro con los vértices de C. Entonces:A) G es eulerianoB) G es bipartitoC) G no es hamiltoniano
Solución :Se trata de un grafo conexo, los vértices del cubo tienen grado 4, el centro delcubo tiene grado 8, al ser todos pares admite un circuito euleriano.No es bipartito porque hay ciclos de longitud impar, concretamente dos vérticesconectados por una arista con el centro forman un ciclo de longitud 3.Tiene un ciclo hamiltoniano:
![Page 34: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/34.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 34/37
BÚSQUEDA DE UN CICLO HAMILTONIANO
Ejercicio resuelto : encontrar un ciclo hamiltoniano al grafo:
Vamos a suponer que existe para este grafo un ciclo hamiltoniano.Tengamos en cuenta lo siguiente:- Cada vértice participa con dos de sus aristas al ciclo- Si sabemos que un vértice tenemos determinadas dos de sus aristas, las
demás no participarán en el ciclo y las podemos eliminar a fin de obtener elposible ciclo.
En el grafo anterior se observa que las cuatro esquinas únicamente tienen dosaristas, luego de existir el ciclo, formarían parte de él.
Podemos eliminar
![Page 35: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/35.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 35/37
Tenemos ahora dos nuevos vértices con dos aristas, están obligadas a participaren el ciclo:
Podemos eliminar dos aristas que no pueden participar en el ciclo
Hemos obtenido, así, un vértice que no puede participar en el ciclo con dosaristas.
![Page 36: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/36.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 36/37
CONCLUSIÓN
Del presente trabajo, se desprende, una vez más, la importancia de los caminosy circuitos en la representación de situaciones de la vida real. Y en cuanto a losgrafos en general, su variedad y diversidad aplicativa.
A pesar del paso del tiempo y la inversión del mismo hecha en el estudio de lateoría de grafos, aún no se han podido generar algoritmos cien por cientoeficaces para búsqueda de caminos y circuitos complejos.En lo que a informática respecta, los algoritmos implementados han conseguidodar solución a muchos casos que antes implicaban mucho tiempo en su
resolución; sin embargo, tampoco son cien por ciento eficaces.
![Page 37: caminos eurelianos y hamintonianos](https://reader035.fdocumento.com/reader035/viewer/2022082204/5695d0a81a28ab9b029357a5/html5/thumbnails/37.jpg)
7/23/2019 caminos eurelianos y hamintonianos
http://slidepdf.com/reader/full/caminos-eurelianos-y-hamintonianos 37/37
BIBLIOGRAFIA
WWW.DC.UBA.AR/MATERIAS/AED3/2013/1C/TEORICA/ALGO3_TEO_EULERI
ANO
TEORIADEGRAFOS.BLOGSPOT.COM/.../GRAFOS-EULERIANOS-Y-
HAMILTONIANOS.HTM
HTTPS://PREZI.COM/.../CAMINOS-EULERIANOS-HAMILTONIANOS-Y-DE-
LONGITUD
HTTPS://WWW.U-CURSOS.CL/INGENIERIA/2011/1/CC3101/1/MATERIAL