GRAFOS Vemos que se trata de un ciclo hamiltoniano.

Ciclo es un camino cerrado donde los únicos

1. La matriz de adyacencia del grafo G es vértices repetidos son el primero y el último
1 1 1 0 Cuando un ciclo contiene todos los vértices del

1 1 grafo se llama ciclo hamiltoniano.
1 0 0 1
Nuestro grafo contiene siete vértices, y el camino
 
1 1 en cuestión los recorre todos sin repetir vértice,
0 1  es por tanto ciclo hamiltoniano.

1 1

entonces,
A) G es un pseudografo 4. Dado el grafo de la figura
B) G es un grafo completo
3. G no es conexo
Solución: Supongamos V={v1,v2,v3,v4} son los
vértices del grafo. En los pseudografo están
permitidas las aristas cuyos extremos coinciden,
es decir, los lazos.
En la matriz de adyacencia dada se observa que
m11=1, un lazo en v1 A) Es hamiltoniano
m22=1, un lazo en v2 B) Es euleriano
m33=1, un lazo en v3 3. Es bipartito
m44=1, un lazo en v4 Solución: el subgrafo de la figura siguiente
Se trata de un pseudografo. contiene un ciclo hamiltoniano

2. Sea A la matriz de adyacencia de un multigrafo

G con vértices {v1, v2,...,vn} y sea a23=3 una de
las entradas de A. Entonces,
A) Existe un camino con tres vértices entre v2 y
v3. Un grafo que contiene un ciclo hamiltoniano se
B) Hay tres aristas con extremos los denomina grafo hamiltoniano.
vértices v2 y v3. No es euleriano porque hay seis vértices que
C) Hay tres vértices adyacentes con v2 y v3 tienen grado 3, es decir grado impar. Recuérdese
Solución: en los multigrafos se define la matriz de que si un grafo es euleriano todo vértice tiene
adyacencia: grado par. No es bipartito porque el ciclo
aij=número de aristas cuyos vértices son vi y vj, asociado a la figura anterior es de longitud impar.
ij aii=0
Por tanto si a23=3 entonces hay 3 aristas con 5. Sea G un grafo conexo cuyos vértices son {v1,
vértices extremos v2 y v3 v2, v3, v4, v5}. La sucesión (v1,v2,v3,v5,v1,) es:
A) Un camino euleriano
3. Sea G un grafo con 7 vértices y B) Un ciclo hamiltoniano
C=(v1,v3,v2,v4,v5,v7,v6,v1) un camino en G. C) Ninguno de los anteriores
A) C es un camino hamiltoniano Solución: el subgrafo
v
2. C es un ciclo asociado al camino es el de la 1 v2
hamiltoniano figura.
C) C no está bien definido Un camino euleriano es un v3
Solución: dibujando el subgrafo asociado al camino que contiene todas las
camino v aristas apareciendo cada una v4
v
1 v2 de ellas exactamente una vez. v
7 5
v En nuestro caso desconocemos
3 todas las aristas del grafo, no podemos asegurar
v
6
que sea euleriano.
v4 Tampoco es un ciclo hamiltoniano, puesto que debe
v
5
pasar por todos los vértices sin repetir repetir
ninguno.
  0 1 0
 0  0 1 1 1
  

6. Sea M un mapa cuyas regiones se pueden A
1  0 1 1  0 0 0
1 ;B ;
colorear con sólo dos colores: 0 1 1 0 1
0 1 0
A) El pseudomultigrafo dual es bipartito    
B) Todas las caras son polígonos con 0 1 1 0 1 0 1 0
1
un número par de lados.  0 1 1
 
C) No existen tales mapas. 1 0 1
C  1
Solución: veamos dos ejemplos de tales mapas 1 1 0
 1
1 1 1 

0
A) A y B son isomorfos
B) A y C son isomorfos
C) B y C son isomorfos
Solución: el grado de un vértice se obtiene
Ambos mapas se pueden colorear con dos sumando los elementos de la fila.
colores. Entendiendo que “caras” se refiere a Matriz A: gr(v1)=1; gr(v2)=3; gr(v3)=2; gr(v4)=2
“regiones”, el grado de las regiones internas es 3 Matriz B: gr(v1)=3; gr(v2)=1; gr(v3)=2; gr(v4)=2
y 4 respectivamente. Matriz C: gr(v1)=3; gr(v2)=3; gr(v3)=3; gr(v4)=3
Si un mapa se puede colorear con dos colores, No se puede establecer un isomorfismo entre A y
regiones adyacentes tendrán asociados colores C, ni entre B y C, puesto que no se pueden hacer
diferentes; manteniendo la misma coloración corresponder los grados de los vértices.
para las regiones que para las aristas asociadas Entre A y B se puede establecer el isomorfismo:
por la transformación dual, las aristas conectaran
vértices que provienen de regiones adyacentes y v1 v2 v1 v2
por tanto tendrán distintos colores.
Grafo A Grafo B
7. Dado el digrafo etiquetado x
1 2
v4 v3 v4 v3
1 1
3 1 Donde las líneas de puntos indica la corresponden-
7 2 cia entre los vértices.
Se observa que se conserva el grado de los vértices
2 2 por el isomorfismo.
y
9. ¿Cuál de los siguientes grafos no se puede
¿Cuál es la distancia entre x e y? dibujar sin levantar el lápiz del papel y sin
A)  B) 5 C)12 dibujar dos veces la misma arista?
Solución: siguiendo el algoritmo de Dijkstra y
colocando en cada vértice la distancia desde x, A) B)
obtenemos:
0

1 2 C)

2
Solución: para resolver este ejercicio hay que
4 3 analizar el grado de cada vértice. Para que se
pueda dibujar en las condiciones pedidas debe
ocurrir una de:
5 - Todos los grados son pares, entonces es un
8. Dadas las matrices de adyacencia A, B y C de grafo euleriano, es decir, admite un circuito
tres grafos 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 impar y termine en el otro.
Grafo A:
3 4 El grafo es visiblemente conexo, es decir, todos
sus vértices están conectados a través de un
camino.
2 Un multigrafo es un grafo con (posiblemente)
3 varias aristas entre dos vértices. El que
arriba
4 vemos no es multigrafo (propiamente).
Admite un camino euleriano, partiendo de uno de Tampoco es euleriano porque tiene 4 vértices
los vértices señalados por una flecha y terminando con grado impar y por tanto no admite un
en el otro circuito euleriano.

Grafo B: 2
11. Sea Kn el grafo completo con n vértices, n
43 par, n3.
A) Kn es hamiltoniano
B) Kn es euleriano
C) Kn es bipartito
43 Solución: dos ejemplos de grafos completos nos
permiten decidirnos por una de las tres opciones:
2
v1 v1 v2
Igual situación que en el grafo

A. Grafo C: 3 v k v4 k4 v
3 3
3
v2 3
4 Ambos grafos completos son Hamiltoniano, basta
escoger el ciclo: (v1,v2,v3) en K3 y (v1,v2,v3,v4) en K4
4
5 K3 es euleriano, pero K4 no lo es.
43 Ni K3 es bipartito, ni K4 no lo es.
En general Kn es hamiltoniano.
3 3
En general Kn no es bipartito, porque tres vértices
están conectados entre sí y forman un ciclo de
Tiene más de dos vértices con grado impar, luego grado impar.
no admite camino euleriano y no se puede dibujar En general Kn para n par y n>2 no es euleriano,
sin levantar el lápiz del papel y sin dibujar dos porque todos los vértices tienen grado n-1(impar).
veces la misma arista
12. Sea M la matriz de adyacencia de un grafo con
10. Dado un grafo con matriz de adyacencia p>1 vértices. Sea C=Mp+Mp-1+...+M
0 1 0 1 1
 A) Si C0 entonces el grafo es conexo.

1 0 1 0 0 B) Si la entrada i,j de C es igual a 1 entonces
0 1 0 1 1
 
existe una arista entre el vértice i y el j en el
1 0 1 0 1 grafo.
 C) Si el grafo es conexo entonces todas las
 1 0 1 1 0
entradas de C son no nulas.
A) El grafo es euleriano
B) El grafo es conexo Solución:
C) Es un multigrafo Recordando la teoría: Si M es la matriz de
Solución: considerando el conjunto de vértices adyacencia de un grafo, el elemento (i,j) de Mn nos
V={v1,v2,v3,v4,v5} y representando el grafo da el número de caminos de longitud n con
asociado extremos vi y vj .
a la matriz, tenemosv:
1 v2 Existirá un camino entre vi y vj si la entrada (i,j) de
la matriz C=Mp+Mp-1+...+M es no nula.

v 3
v5
v
4
En C estarían reflejados todos los posibles caminos aristas. ¿Cuál de las siguientes afirmaciones es
de longitudes: 1, 2, 3,...,p cierta?
El grafo es conexo si y sólo si todas las entradas de A) #R=9
C son no nulas . Esto nos indica que la respuesta C) B) #R=12
es correcta. C) #R=10
Para ver que las otras respuestas son falsas, Solución: aplicando el primer teorema de la
buscaremos ejemplos adecuados teoría de grafos:
p
Ejemplo 1: sea el grafo con tres vértices de la figura  gr(vi )  2·# E
i1
v1 En nuestro caso: #E=14, gr(vi)=4 para cualquier i.
p
v El primer miembro es:  gr(vi )  4·#V
2
i1
v El segundo miembro es:
3
2·#E=2·14=28 Donde:
La matriz de adyacencia es: - #E es el número de aristas
 0 1 0  1 0 0 - #V el número de vértices
M  1 0  M2   0 1  - gr(vi) es el grado del vértice i
 0 0 0  0 0 0 Resumiendo el primer teorema:
 
0 1 0 0 4·#V=28  #V=7

 
0
 
M3  Aplicando ahora la fórmula de Euler
0 0

0 #V - #E + #R =2
1 se obtiene: 7-14+#R=2  #R=9
1 2
 0 0
 0   
Por tanto: C  M 3  M 2  M   2 1 0
 0 0 0
 
 0 0 14. Los dos grafos de la figura
0 0 0 y no es conexo.
C 0
0 0 


0
Ejemplo2: sea el grafo de la figura
v
1

v
2 A) Son isomorfos pues tienen el mismo
número de vértices y de aristas.
v3 B) Son isomorfos porque se puede establecer
En este caso: un isomorfismo entre ellos
 0 1 1 0 C) No son isomorfos pues en uno hay dos
M  1 0  2 0 vértices de grado 2 y en el otro hay
 1 0  M2  0 1 
 0  0 1 1 tres vértices de grado 2.
 Solución: analizando los grados de los vértices
 0 2 0 1
M 3   2 0 Grados del grafo 1º: 2, 3, 4, 2, 3, 4
 
 2 0 2 Grados del grafo 2º: 2, 4, 2, 4, 2, 4
 Si existiera un isomorfismo se tendría que

0 conservar el grado de los vértices isomorfos.
 3 Dado que no se pueden hacer corresponder
3
0 
  2


3 2
Por tanto: C  M  M  M   3 1 1 1 

 3 1

biunívocamente los e emplo), no puede existir un isomorfismo.
vértices de grado 2 (por j
c23=1, pero no existe una arista de v2 a v3.
15. Sea el mapa M de la figura
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 14
 Ninguno de los vértices puede tener grado 5.

17. Los grafos de la figura, ¿son isomorfos?

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. A) No, porque uno es plano y el otro no
Solución: según el teorema de los cuatro B) Sí, pues existe un isomorfismo entre ellos.
colores, como máximo son necesarios cuatro C) Sí, porque tienen el mismo número de
colores para colorear un mapa. vértices y aristas.
Las tres regiones internas de nuestro mapa Solución: son isomorfos puesto que se puede
necesitan tres colores distintos, dado que están establecer un isomorfismo.
en contacto entre sí. La correspondencia a través de los números:
Como cada una de estas regiones internas toca a
2 2 3
tres más va a ser necesario un color más para
colorear el mapa. 1 3 4
4
Una solución con cuatro colores sería: 1 5
9 10 8 6
7 10
8
6 5 9 7
3
4
2 1
produce el mismo grafo G=(V,E), donde:
1 2
V={1,2,3,4,5,6,7,8,9,10}
3 E={12,19,16,24,23,3A,35,48,47,57,56,68,79,8A,9A}
4 4 Se trata de un isomorfismo.
1

18. En el grafo de la figura sea L(vi) la longitud del

16. Dado el grafo G con matriz de adyacencia camino más corto entre los vértices u y vi
u

6 1
 0 1 v
 1 0 1 3 2
1 0 v4 1
1
1 1  2

 2
0 0 1 0 0 1 1
 0 1 1 Entonces: 1 v3 v2
 1 
0
1 0 1 3 y L(v4)=6
A) L(v4)=6 y L(v2)=2 B) L(v3)=4
B) L(v3)=3 y L(v4)=5
1 1 0
A) G tiene un camino euleriano Solución: siguiendo el algoritmo de Dijkstra y
B) G no es conexo colocando L(vi) en cada vértice tenemos:
C) G tiene un vértice de grado 5 L(v1)=1 0
Solución: v v L(v2)=2
1 L(v3)=3
L(v4)=5
5 1
v
5 v3
3 2
A partir de la represevntación gráfica vemos que 19. Dado un grafo con matriz de adyacencia
es
conexo. 4

Los grados de los vértices son respectivamente:

3,2,4,2,3; como hay exactamente dos vértices con
grado impar, admite un camino euleriano.
 0 1 0 1 1 B) Si la entrada (i,j) de C es igual a 1 entonces

1 0 1 0 0 existe una arista entre los vértices i y j.
0 1
0 1 1 C) Si el grafo es conexo entonces todas las
 
1 0 1 0 1 entradas de C son no nulas.
 Solución: es similar al ejercicio 12
 1 0 1 1 0
A) El grafo es euleriano 22. ¿Cuál es el número de veces que se debe
B) El grafo es conexo levantar el lápiz para dibujar la figura siguiente
C) Es un multigrafo sin repetir ninguna arista?
Solución: gráficamente tenemos

v1 v2

v
v5 3

v A) Ninguna vez
B) Una vez
4
Es conexo, dado que no hay ningún vértice aislado C) Dos veces
de los demás. Solución: los grados son:
No es euleriano porque los grados de los 3
vértices son: 3, 2, 3, 3, 3. (Para que sea grafo 3 3
euleriano tienen que ser todos los grados pares). 4
No es multigrafo porque no hay todos los números 4 4
que aparecen son 0 ó 1. Para que sea multigrafo 6
propiamente deben existir más un número
superior a 1, indicando con ellos que dos vértices 4 4 4
se conectan con más de una arista. 4
4 4
20. Sea Kn el grafo completo con vértices, n 3
par, n3, entonces Al haber más de exactamente dos grados impares
A) Kn es hamiltoniano tendremos que levantar el lápiz al menos una
B) Kn es euleriano vez. Si eliminamos la línea vertical central,
C) Kn es bipartito tendremos
Solución: Todo grafo completo es hamiltoniano,
2
siempre existirá el ciclo (v1, v2, v3,..., vn,v1), dado 3 3
que cualquier pareja de vértices está
2
conectados por una arista. 4 4
Todo grafo completo de n vértices, con n pary
n>2, no es euleriano, porque cada vértice tendrá 4
grado (n-1), que es impar, y por tanto no admite 4 2 4
circuito euleriano.
Todo grafo completo con n>2, no puede ser 4 2
4
bipartito, porque tiene ciclos de longitud impar, 2
concretamente tres puntos cualesquiera forman Este se podrá dibujar sin levantar el lápiz desde un
un ciclo de longitud 3: v vértice de grado impar hasta el otro de grado
i
impar.
Luego se levanta el lápiz y se dibuja la línea
v vertical, con lo que se completa el grafo.
vk k
21. a M la matriz de adyacencia de un grafo con
p>1. Sea C=Mp+Mp-1+...+M
A) Si C0 entonces el grafo es conexo 23. Sea el grafo de la figura
 (s,d)=22 (s,t)=55

25. Dados los grafos de la figura

A) Es plano
2. No es plano
C) No es bipartito A) No son planos
Solución: es fácil ver que es bipartito B) Son isomorfos
0 C) No son isomorfos
1 1 Solución: ambos grafos son visualmente planos
(mapas: las aristas solo se cruzan en los vértices).

0 0 Los grados de los vértices del primer grafo son:

2, 4, 3,4, 4, 4, 3
Los grados de los vértices del segundo grafo son:
1
1 4, 3, 3, 4, 2, 4
0 Un isomorfismo podría ser:
Como es conexo, si fuera plano debería cumplir la
6 3 2
desigualdad: #E  2·#V-4
En nuestro caso: #E=16, #V=8 y #E>2·#V-4 2
1 4
Luego no puede ser plano. 3
1

24. Dado el grafo etiquetado 6 5

5 4
a 9 Para ambos quedaría:
b G=(V,E)
18
28 V={1,2,3,4,5,6}
s 14 E={16,15,62,52,65,63,54,24,23,34}
6 t
15 10
36 26. Sea G un grafo y A su matriz de adyacencia.
c 7 d
¿Cuál de las siguientes informaciones dan los
Se aplica el algoritmo de Dijkstra partiendo del elementos de la diagonal principal de la matriz
vértice s. Se designa por (s,w) la distancia A?
entre s y cualquier otro vértice w. ¿Cuál de los A) Los grados de los vértices G.
siguientes resultados es cierto? B) Los ciclos con a lo más dos aristas
A) (s,a)=18, (s,b)=27, (s,c)=15, (s,d)=22, C) Ninguna de las anteriores
(s,t)=55. Solución: en los grafos la diagonal son elementos
B) (s,a)=18, (s,b)=27, (s,c)=15, (s,d)=22, nulos porque no hay lazos, es decir aristas con
origen y extremo en el mismo vértice.
(s,t)=57.
En los pseudografos están permitidos los lazos.
C) (s,a)=18, (s,b)=29, (s,c)=15, (s,d)=22, En los pseudografos, por tanto, en la diagonal
(s,t)=57. deben haber elementos no nulos.
Solución: aplicando Dijstra tenemos las La definición de matriz de adyacencia para
distancias: multigrafos y pseudografos viene propuesta en el
problema 5 (página 167 del libro base).
18 27 En esencia el elemento mij debe reflejar el
número de aristas que hay entre el vértice vi y vj.
s En los pseudografos afecta a la diagonal principal
55
y a los multigrafos afecta a los elementos que no se
Con lo que: 15 22 limitan a ser 0 y 1. As-i, mij=3 nos indicaría que
(s,a)=18 (s,b)=27 (s,c)=15 existen 3 aristas que unen los vértices vi y vj.
  0 1 0 1
27. Sea G el grafo de la figura  0 1 
1 0
C  0 1
0 0 

 1 1 1 0
A) A y B son isomorfos
B) A y C son isomorfos
 C) B y C son isomorfos
Solución: analizando los grados tenemos
A) G es hamiltoniano Grafo A: 3,1,2,2
B) No tiene un camino simple que pase por Grafo B: 3,3,2,2
todos los vértices Grafo C: 2,2,1,3
3. No es De ser isomorfos los serán A y C.
hamiltoniano
Pistas: Es fácil encontrar un camino simple que 30. Sea K6 el grafo completo con 6 vértices,
pase por todos los vértices. entonces:
Hay, por tanto, que decidir si es o no hamiltoniano. A) Es bipartito ya que tiene un número par de
Supongamos que es hamiltoniano, entonces si vértices
eliminamos k vértices y sus aristas no deben B) Es hamiltoniano
obtenerse más de k componentes conexas. C) Es euleriano
También podemos intertar buscar eun Solución: K6
ciclo hamiltoniano. Es hamiltoniano como todos los grafos completos.
Véase al final de este documento No es euleriano porque todos seis vértices son de
grado 5 (impar).
28. ¿Cuál de las siguientes afirmaciones sobre los No esa bipartito porque tiene ciclos de
grafos de la figura es cierta longitud impar (3, por ejemplo).

31. Consideremos el grafo G de la figura:

C
A
B

A) B y C tienen un camino euleriano

B) A es euleriano
C) A tiene un camino euleriano y B un circuito
euleriano. A) El grafo no es plano porque dos aristas se
Solución: analizamos los grafos por separado. cortan.
En A hay dos vértices de grado impar, no es B) El grafo no es plano porque todo vértice es
grafo euleriano pero admite un camino euleriano. de grado 3.
En B todos los vértices son de grado par, luego es C) El grafo es plano
una grafo euleriano. Solución: Es plano porque es isomorfo al mapa
C tiene más de dos vértices con grado impar, luego
no es euleriano ni admite camino euleriano.

29. Dadas las matrices de adyacencia de los grafos

A, B y C siguientes:
 0 1 1 1  0 1 1 1
   

A
1 0 0 0  0 1 1
1 ;B ;
1 0 0 1 1 1 0 0 
   
1 0 1 0 1 1 0 0
32. Sea el grafo completo Kr (r>2). Entonces Kr es
bipartito. 35. Sea el grafo de la figura:
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 para cualesquiera tres vértices vi,
vj, vk podemos encontrar el ciclo de longitud 3:
vi

v A) El grafo es euleriano
k vj B) El grafo es 3 regular
Recordamos el teorema: “Un grafo es bipartito si C) El grafo es hamiltoniano
y solo si no tiene ciclos con longitud impar” Solución:
Los grados de los vértices son: 3, 3, 3, 3, 3, 3, 2
luego no puede ser grafo euleriano.
33. Cuál de estas afirmaciones es falsa: Un grafo es k-regular si todos los vértices tienen
A) Todo grafo tiene un número impar el mismo grado k.
de vértices de grado par. Evidentemente hay un vértice que no es de grado 3,
B) Todo grafo tiene un número par o cero luego no puede ser 3-regular
de vértices de grado impar. Es hamiltoniano puesto que el camino cuyo
C) La suma de los grados de los vértices de un subgrafo:
grafo es par.
Solución: según el primer teorema la suma de
todos los grados de los vértices tiene 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:

es un ciclo hamiltoniano, pues es un camino

cerrado, pasa por todos los vértices y no repite
ninguno.

tenemos los siguientes grados: 3,2,2,3 36. En el mapa de la figura las regiones que se
Tiene por tanto 2 vértices de grado designan por Ri:
par.
R2
34. Sea el grafo completo Kr (r>1). Su matriz de
adyacencia es: R
A) aii=1, aij=1 (i distinto de j) 1 R3RR 5 4
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 el grado de la región R2 es:
aij=0  no tiene arista entre los vértices vi y vj A) 8
Por tanto, en un grafo completo B) 10
- no hay lazos  aii=0 C) 5
- toda pareja de vértices están conectados  Solución: Se denomina gradode una región a la
aij=1 (ij) longitud del camino que la bordea.

Poniendo nombre a los vértices

 Solución: los grados de ambos grafos son
v1 v2 Grafo 1º: 2,3,4,2,3,4
R Grafo 2º: 2,4,2,4,2,4
2

v v Si hubiera un isomorfismo tendría que correspon-

R1 5 R R 6
derse biyectivamente iguales grados. Así por
R3 5 4
v ejemplo, los vértices de grado dos no se pueden
7
v8 asociar biyectivamente, porque en una hay 2 y en el
v v3 otro grafo hay 3.
4

El camino que bordea R2 es: 39. Sea Kn el grafo completo con n>3 vértices, n
(v1, v2, v3, v4, v1, v5, v6, v7, v8, v5, v1) par:
luego la longitud es 10 A) es euleriano
B) es bipartito
37. Sea K6 el grafo completo con 6 vértices, C) es hamiltoniano
entonces: Solución: este es un ejercicio que ha aparecido
A) Es bipartito ya que tiene un número par de en varias ocasiones. En general, para cualquier
vértices. n>2 tenenmos:
B) Es hamiltoniano - Kn es hamiltoniano
C) Es euleriano - Kn es euleriano si n es impar, no lo es si n
Solución: K6 tiene 6 vértices, el grado de cada es par.
vértice es 5, porque existe una arista por cada - Kn no es bipartito
pareja de vértices.
Si los vértices son { v1, v2, v3, v4, v5, v6} los grados 40. La matriz de adyacencia del grafo G es
son: 5, 5, 5, 5, 5, 5  1 1 1 0
No puede ser euleriano, para que lo fuera tienen  1 
1 1 0
que ser todos los grados pares. 1 0 1 1
 
No es bipartito porque de tres vértices se
puede obtener un ciclo de grado 3 (impar). 0 1 1 1

Es hamiltoniano porque el camino: A) G es pseudografo

B) G es un grafo completo
(v1,v2,v3,v4,v5,v6,v1)
C) G no es conexo
es un ciclo hamiltoniano.
Solución: dado que tiene en los elementos de la
v1 v2
diagonal un 1, hay lazos en cada vértice, por tanto
es un pseudografo.
v No es completo porque, por ejemplo, m14=0 y por
v6 3
tanto no hay arista entre v1 y v4.
K Es conexo porque el camino (v1,v2,v4,v3,v1)
recorre todos los vértices, y dicho camino es
6
v5 v4 posible porque:
m12=1  v1 v2
38. Los dos grafos de la figura m24=1  v2 v4
m43=1  v4 v3
m31=1  v3 v1

41. Sea A la matriz de adyacencia de un digrafo con

{v1, v2, v3,...,v7} vértices, y sea a14=3, una de las
entradas de la matriz A2.
A) Son isomorfos pues tienen el mismo número Entonces:
de vértices y de aristas. A) Hay un camino entre v1 y v4 con tres vértices
B) Son isomorfos porque se puede establecer intermedios.
un isomorfismo entre ellos. B) Hay tres caminos de longitud 2 de v1 a v4.
C) No son isomorfos pues en uno hay dos C) Hay tres aristas distintas que unen v1 y v4.
vértices de grado 2 y en el otro hay Solución: la entrada a14 de A2 es el número de
tres vértices de grado 2. caminos de longitud 2 con extremos v1 y v4.
Como
es un digrafo, y por tanto las aristas están 5·#V=2·20=40  #V=40/5=8
orientadas dichos caminos de longitud 2 tienen
La fórmula de Euler: #V - #E + #R = 2
origen en v1 y extremo en v4
Es decir: 8- 20 +r=2  r=14
42. Sea G un grafo (no pseudografo ni multigrafo)
plano conexo con 15 aristas. Entonces el 45. Sea G el grafo formado por los vértices y
número de vértices de G es como mínimo aristas de un tetraedro T más el centro de T y
A) 5 B) 7 C) 9 las aristas que unen dicho centro con los
Solución: si es un grafo plano conexo debe vértices de
cumplirse T. Entonces:
A) G es bipartito
 #E  3·#V – 6 con #V>2
B) G es euleriano
(Tal aspecto teórico puede consultarse en la
C) G no es hamiltoniano
página 174 del libro base)
Solución:
Es decir: 15  3·#V – 6  #V  7 Se trata de un grafo completo K5, por tanto
- G no es bipartito, porque tiene ciclos
43. Sea el grafo de la figura: 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 (v1,v2,v3,
v4, v5, v1) existe y es un ciclo hamiltoniano.

46. Sea el mapa de la figura

A) Es bipartito
B) No es bipartito ya que todos los
vértices tienen el mismo grado
C) Es euleriano ya que todos los vértices Teniendo también en cuenta la región
tienen el mismo grado. exterior para colorear el mapa se necesita
Solución: es bipartito dado que se puede colorear A) 2 colores
con dos colores. B) 3 colores
C) 4 colores
Solución:
1 3
2
2
1
Se necesitan 3 colores mínimo.

47. Sea el mapa M de la figura

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 grado de todos los vértices
es 5 y G tiene 20 aristas, entonces r es
A) 12
B) 14 A) M se puede colorear con tres colores
C) 18 diferentes
Solución: aplicamoe el primer teorema de grafos y B) M necesita cuatro colores para ser coloreado.
la fórmula de Euler. C) Son necesarios más de cuatro colores para
La suma de todos los grados de los vértices es: colorear M.
5·número de vértices=5·#V Solución: véase el ejercicio 15
Tiene que coincidir con el doble de aristas
48. En el grafo de la figura sea L(vi) la longitud del Solución:
camino más corto entre los vértices u y vi 2 3
1
u 1

6
1 2
12
1
v 2
4 v1 Son necesarios al menos 3 colores.
2 1
v2 1
1
v3 3 51. El grafo formado por los vértices y aristas de la
figura anterior es
A) L(v4)=6 y L(v2)=2 A) Euleriano
B) L(v3)=3 y L(v4)=4 B) Bipartito
C) L(v3)=2 y L(v4)=3 C) Ninguno de los dos
Solución: Solución:
L(v2)=1 siguiendo el camino (u(1)v2) No puede ser euleriano porque hay vértices
L(v3)=2 siguiendo el camino (u(1)v2(1)v3) de grado impar.
L(v4)=3 siguiendo el camino (u(1)v2(1)v3(1)v4) No puede ser bipartito porque hay ciclos de
Recordamos, L(vi) se forma con los recorridos longitud (3) impar.
más cortos.
52. La matriz de adyacencia de un grafo G es:
49. Dado el grafo G con matriz de adyacencia:  1 1 1 0
1 0  
 0 1 1 1 1 0 1
 1 0 1 1
1 0 
1 1 1 0 0  
 0 1 1 0 1 1 1

0 0 1 0 1 A) G es un pseudografo
 1 0 1 1 0 B) G no es conexo
A) G tiene un camino euleriano C) G es un grafo completo
B) G no es conexo Solución:
C) G tiene un vértice de grado 5 Dado que en la diagonal principal hay unos,
Solución: significa que hay lazos, es decir, se trata de
Los grados de los vértices se obtiene sumando los un pseudografo.
números de las filas: 3, 2, 4, 2, 3. Ninguno es de Existe el camino (v1,v2,v4,v3,v1) porque:
grado 5. m12= m24= m43= m31= 1
Tiene un camino euleriano: Es conexo porque (v1,v2,v4,v3,v1) es un camino que
(v1(m12=1)v2(m23=1)v3(m34=1)v4(m45=1)v5(m51=1)v1) recorre todos los vértices, por tanto están
Por tanto es conexo. conectados

50. Teniendo en cuenta la región exterior ¿cuántos 53. Sea el grafo con matriz de adyacencia:
colores son necesarios para colorear las regiones  1 0 1
del mapa? 0 0 1 1 
 1 0 1
1 
 1 1 0
0


1
B) Cuatro
C) Cinco

A) Tres
 El
núm
ero
de
cami
nos
disti
ntos
de
longi
tud
tres
entre
dos
vérti
ces
v1 y
v4 es
5
3
C)
2

S
o
l
u
c
i
ó
n
:

54. El
grafo
que
tiene
por
matriz
de
adyace
ncia
 0 1 B) Los ciclos con a lo sumo dos vértices
 0 1 
  C) Ninguna de las anteriores
1 0
0 1 1 1 Solución: recordamos la teoria.
 
0 1
La entrada (i,j) de la matriz Mn es el número de
1 1
 caminos de longitud n con extremos vi y vj.
es:  En nuestro caso el elemento (i,i) de la diagonal de
1 0
A) Un pseudografo
A2 es el número de caminos de longitud 2 con
B) Tiene un camino euleriano
extremos vi y vi. Como el origen y el extremo
C) Tiene un circuito euleriano
coinciden, se trata de ciclos de longitud 2.
Solución: su representación gráfica es
v
1
v2 57. Dado el grafo de la figura:

v
4
v3
No es pseudografo porque la diagonal está
formada por ceros y por tanto no hay lazos.
Contiene un camino euleriano (v2,v3,v4,v2,v1,v4) A) Es bipartito
B) Es hamiltoniano
v1 C) Es euleriano
v Solución: contiene un ciclo hamiltoniano
2

v
4 v3
No admite circuito euleriano porque hay
vértices con grado impar. No es euleriano porque es conexo y tiene
vértices de grado impar.
55. Sea K5 el grafo completo de cinco vértices No es bipartito porque tiene ciclos de grado impar
A) Es euleriano (como el representado)
B) Es bipartito
C) Es un pseudografo 58. Sea G un grafo y M un mapa con r regiones que
Solución: una representación gráfica es representa a G. Supongamos que el grado de
todos los vértices de G es 4 y que G tienen 14
aristas. ¿Cuál de las siguientes afirmaciones es
cierta?
A) r=12
B) r=10
C) r=9
Solución: aplicamos el primer teorema y la fórmula
Es euleriano dado que es conexo y todos los
de Euler.
vértices tienen grado par.
No es bipartito porque tiene ciclos de longitud 3 Primer teorema: 4·#V=2·14 #V=7
y ciclos de longitud 5 (impar). Fórmula de Euler: 7-14+r=2 
No es pseudografo poruqe no tiene aristas con r=9
origen y extremo el mismo vértice.
59. Sea G un grafo con n vértices y sea S la suma
56. Sea G un grafo y A su matriz de adyacencia. de los grados de los vértices de G. Entonces:
¿Cuál de las siguientes informaciones dan los A) S es par
elementos de la diagonal principal de la matriz B) S es impar
A2? C) La paridad depende de n
A) Los grados de los vértices de G Solución: según el primer teorema, la suma de los
grados de los vértices es exactamente 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 euleriano Podemos eliminar
B) G es bipartito
C) G no es hamiltoniano
Solución:
Se trata de un grafo conexo, los vértices del cubo
tienen grado 4, el centro del cubo tiene grado 8, al
ser todos pares admite un circuito euleriano.
No es bipartito porque hay ciclos de longitud
impar, concretamente dos vértices conectados por
una arista con el centro forman un ciclo de
longitud 3. Tenemos ahora dos nuevos vértices con dos
Tiene un ciclo hamiltoniano: aristas, están obligadas a participar en el ciclo:

Podemos eliminar dos aristas que no pueden

participar en el ciclo
BÚSQUEDA DE UN CICLO HAMILTONIANO
Ejercicio pospuesto: encontrar un ciclo
hamiltoniano al grafo:

Hemos obtenido, así, un vértice que no puede

participar en el ciclo con dos aristas.
Luego no puede haber tal ciclo hamiltoniano.

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 el posible ciclo.
En el grafo anterior se observa que las cuatro
esquinas únicamente tienen dos aristas, luego de
existir el ciclo, formarían parte de él.