Examenes_resueltos (2)

Vista previa del material en texto

Escuela Técnica Superior
de Ingenieŕıa Informática Curso 2007/2008
Colección de Exámenes
de
Matemática Discreta
Depto. de Matemática Aplicada I
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
10 de Diciembre de 1999
Ejercicio 1
Se denomina grafo molinillo de orden n, Mn, a un grafo con vértices Vn = {0, 1, 2, . . . , 2n} y aristas An =
{{0, i} : 1 ≤ i ≤ 2n} ∪ {{2i− 1, 2i} : 1 ≤ i ≤ n}. Aśı por ejemplo M4 seŕıa el grafo
�
�� �
�� �
��
�
�� �
�� �
��
�
�� �
�� �
��
"
"
"
""
,
,
,
,,QQ
Q
Q
Q
Z
Z
Z
ZZ
4 3 2
105
6 7 8
1. ¿Para qué valores de n es Mn euleriano?
2. ¿Para qué valores de n admite Mn un recorrido euleriano?
3. Se define vértice de corte como aquel, que al eliminarlo del grafo, aumenta el número de componentes
conexas del mismo. Encontrar el número de vértices de corte de Mn para todo n.
4. ¿Para qué valores de n es Mn hamiltoniano?
5. ¿Para qué valores de n admite Mn un camino hamiltoniano?
6. Calcular el número cromático de Mn.
7. Dar un coloreado de aristas de Mn utilizando el menor número de colores posibles.
Solución. La Figura 1 muestra los grafos molinillo M1, M2, M3 y M4.
0
1
2
0
1
2
3
4
0
1
2
3
4
6
5
0
1
2
3
4
6
5
8
7
M
1
M
2
M
3
M
4
Figura 1: Los grafos molinillo M1, M2, M3 y M4.
1. Teniendo en cuenta que, para cualquier n: δ(0) = 2n, δ(i) = 2 (1 ≤ i ≤ 2n), el grafo es siempre euleriano,
ya que todos los vértices son pares.
E.T.S.I.Informática Página 2
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
2. Por la misma razón anterior, nunca admite un recorrido euleriano.
3. Si n = 1 el grafo no tiene vértices de corte, ya que se trata del ciclo C3. En cambio, si n > 1, el vértice 0
es un vértice de corte, ya que se trata de un grafo conexo y al eliminar el vértice 0 obtendŕıamos un grafo
con n componentes conexas.
4. Para n = 1 el grafo es hamiltoniano, pues se trata de C3. En cambio para n ≥ 2 no lo es ya que tiene un
vértice de corte.
5. Para n = 1 admite el camino hamiltoniano 0− 1− 2. Para n = 2 admite el camino hamiltoniano 1− 2−
0− 3− 4. Para n ≥ 2 no existe camino hamiltoniano, ya que tiene un vértice de corte de forma que al ser
eliminado, el número de componentes conexas del grafo aumenta en n ≥ 2 unidades.
6. Habida cuenta que Mn contiene el ciclo impar C3 ≡ 0 − 1 − 2 − 0, el grafo no es bipartito y por tanto
χ(Mn) ≥ 3. Por otro lado la aplicación c : V −→ N , c(0) = 0, c(2i − 1) = 1, c(2i) = 2 es una vértice–
coloración con tres colores, por lo que χ(Mn) = 3.
7. Está respondido en el apartado anterior.
Ejercicio 2
Responder a las siguientes cuestiones:
1. Se define estructura arbórea como todo grafo obtenido a partir del siguiente proceso:
a) Un vértice aislado es una estructura arbórea.
b) Si a una estructura arbórea se le añade un vértice y una arista que lo une a otro vértice cualquiera,
resulta otra estructura arbórea.
Demostrar que un grafo T es un árbol si y solo si T es estructura arbórea.
2. ¿Cuántas componentes conexas debe tener un grafo con 1200 vértices, 1000 aristas y sin ciclos? Describir
dos grafos no isomorfos cumpliendo las condiciones anteriores.
3. ¿Cuál es el número máximo de componentes conexas de un grafo con 1200 vértices y 1000 aristas, posea
o no ciclos? Describir dicho grafo.
Solución.
1. Es evidente que si un grafo T es una estructura arbórea es conexo, ya que en cada paso a.2) se conserva
la conexión del grafo y además el número nv de vértices y el número na de aristas verifican na = nv − 1,
ya que en el paso a.1) comenzamos con un vértice aislado y cada paso por a.2) aumenta tanto el número
como el de aristas en una unidad. Por lo tanto T es un árbol. Rećıprocamente, si T es un árbol, podemos
describirlo mediante una estructura arbórea eligiendo, para empezar, uno cualquiera de sus vértices, que
se puede considerar la ráız del árbol y recorrer el árbol mediante cualquiera de los algoritmos DFS o BFS.
2. Teniendo en cuenta la relación a = v − l entre las a aristas, los v vértices y las l componentes conexas de
un bosque, el bosque tendrá l = 200 componentes conexas.
3. Para conseguir el mayor número de componentes conexas habrá que conseguir el mayor número posible
de vértices aislados. Para ello hemos de incluir el mayor número de aristas con el menor número posible
de vértices en una misma componente conexa. Esto es, hay que conseguir un grafo completo con el mayor
número posible de las 100 aristas. Por lo tanto hemos de buscar el mayor número n tal que
n(n− 1)
2 ≤ 1000.
Es decir, como
√
2000 ≈ 44,7, n = 45. El grafo completo K45 tiene 45 vértices y 990 aristas. Si añadimos
un vértice unido a 10 de los vértices de K45 por el resto de las 10 aristas, tendremos una componente
conexa C1 con 46 vértices y 1000 aristas. Si consideramos los otros 1200 − 46 = 1154 vértices aislados
tendremos un grafo con 1200 vértices , 1000 aristas y 1155 componentes conexas (véase la Figura 2).
E.T.S.I.Informática Página 3
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
1
2
10
9
8
7
6
5
4
3
K
45
46
 47
 48
 1200
Figura 2: Un grafo con 1200 vértices, 1000 aristas y 1155 componentes conexas.
Ejercicio 3
A una fiesta de final de carrera acuden un grupo de amigos cuyos nombres son: Alicia (A), Berta (B), Celia (C),
Daŕıa (D), Elena (E), Felipe (F), Gerardo (G), Hilario (H), Ignacio (I) y Jacobo (J). Cada chica solo acepta
bailar con un chico según el esquema siguiente: A acepta como pareja a F,G,H. B acepta como pareja a
G,I. C acepta como pareja a F,G. D acepta como pareja a G,I,J. E acepta como pareja a F,G,H
1. Dibujar el grafo que modela la situación anterior, representando cada persona por un vértice.
2. ¿Es posible conseguir que, a la vez, cada chica baile con un chico de los que acepta como pareja de baile?
En caso afirmativo dar dichas parejas de baile. En caso contrario, encontrar el número máximo de parejas
de baile posibles cumpliendo las condiciones indicadas.
3. ¿Es posible la situación b) si Daŕıa baila con Ignacio? En caso afirmativo dar dichas parejas de baile.
4. Al grupo se incorporan seis nuevos amigos: Luisa (L), Maŕıa (M), Natalia (N), Otilio (O), Pedro (P) y
Quint́ın (Q) quedando el esquema del siguiente modo: A acepta como pareja a F,G,H,O. B acepta
como pareja a G,I. C acepta como pareja a F,G,O. D acepta como pareja a G,I,J. E acepta como
pareja a F,G,H,O,P,Q. L acepta como pareja a I,O. M acepta como pareja a J. N acepta como
pareja a G,I,J,O. Resolver las cuestiones b) y c) en esta situación.
5. Indicar cual es el número mı́nimo de bailes necesarios para que cada chica baile con todos y cada uno de
los chicos a los que acepta como pareja de baile.
Solución.
1. El resultado está en la Figura 3.
2. Podemos encontrar un emparejamiento completo (véase la Figura 4). Las parejas de baila son A − H ,
B − I , C −G, D − J y E − F .
3. Si Daŕıa baila con Ignacio, el problema se modeliza con un grafo de forma que D sólo es adyacente a I
e I sólo es adyacente a D. En este caso el grafo no admite un emparejamiento completo, la Figura 5 nos
muestra el emparejamiento máximo A−H , B −G, C − F y D − I .
E.T.S.I.Informática Página 4
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
A
 E
D
C
B
F
 J
I
H
G
Figura 3:
A
 E
D
C
B
F
 J
I
H
G
Figura 4:
A
 E
D
C
B
F
 J
I
H
G
Figura 5:
A
 M
L
E
D
C
B
 N
F
 P
O
J
I
H
G
 Q
Figura 6:
4. En este caso tenemos un nuevo grafo bipartito. Las Figuras 6 y 7 nos muestran, respectivamente, los
E.T.S.I.Informática Página 5
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
A
 M
L
E
D
C
B
 N
F
 P
O
J
I
H
G
 Q
Figura 7:
resultados a los dos problemas anteriores en la nueva situación.
5. En cada baile debe haber parejas, de forma que no pueden haber dos parejas con la misma persona,
por lo tanto se trata de obtener una arista–coloración del grafo correspondiente. Por tanto hemos de
obtener el ı́ndicecromático del grafo. Teniendo en cuenta que la valencia máxima del grafo es ∆ = 6,
6 ≤ χ1(G) ≤ 7. La Figura 8 muestra una arista–coloración del grafo con 6 colores. Por lo tanto el número
A
 M
L
E
D
C
B
 N
F
 P
O
J
I
H
G
 Q
1
2
2
1
1
5
5
3
1
2
1
4
3
1
3
2
2
1
4
3
2
1
 2
4
3
1
3
2
2
1
4
3
2
5
5
4
4
6
6
1
1
5
5
3
3
6
6
4
4
3
Figura 8:
de bailes necesarios para que cada chica baile con cada uno de los chicos será 6.
E.T.S.I.Informática Página 6
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
13 de Junio de 2000
Ejercicio 1
Para cada n ∈ N, sea Pn el panal simétrico formado por 2n−1 columnas de celdillas hexagonales apiladas unas
encima de otras, que en las columnas i y 2n− i consta de exactamente i celdillas:
eu u u uuu
u
u
u u
u u
u u
u
uu
uu
u
u ux1
x2
x3
x4
x5
x6
x7
x8
x9
x10
x11
x12
x13
x14
x15
x16
P2
P1
· · ·u u u
u u u u u u uupuuu u u u uuuuuuuuu u u u u
P3
Se pide:
1. Hallar el número de caras, vértices y aristas del grafo plano Pn.
Ayuda: Contar vértices y celdillas de Pn por columnas.
2. Calcular el número de aristas que seŕıa necesario eliminar para obtener un árbol recubridor en Pn.
3. ¿Es Pn bipartito?. Justif́ıquese la respuesta. Calcular el número cromático de Pn, aśı como el número
mı́nimo de colores que se puede utilizar para realizar una arista-coloración de Pn.
4. Llamemos Xn (Yn, respectivamente) al conjunto de vértices en Pn situados en las columnas impares
(pares, respectivamente). Probar que en Xn y en Yn hay el mismo número de vértices. Encontrar en P2
un emparejamiento máximo a partir del emparejamiento inicial entre X2 e Y2 que constituyen todas las
aristas horizontales. Enunciar la condición de Hall. ¿Se verifica esta condición para P2? Justif́ıquese la
respuesta.
5. Estudiar el carácter euleriano y hamiltoniano de Pn, según el valor de n.
Solución
1. Si llamamos ci al número de caras interiores que se encuentran en la columna i de celdillas y teniendo en
cuenta la simetŕıa del grafo:
c = 1 + c1 + c2 + · · ·+ cn−1 + cn + cn−1 + · · ·+ c2 + c1 = 1 + 2(1 + 2 + · · ·+ (n− 1)) + n
c = 1 + 2
1 + (n− 1)
2
(n− 1) + n = n2 + 1
Igualmente, si llamamos vi al número de vértices de la columna i de celdillas, i = 1, . . . , 2n− 1 y teniendo
en cuenta de nuevo la simetŕıa del grafo:
v = 1 + v1 + v2 + · · ·+ vn−1 + vn + vn−1 + · · ·+ v2 + v1 + 1 = 1 + 2(4 + 6 + · · ·+ 2n) + 2(n + 1) + 1
v = 2 + 2
4 + 2n
2
(n− 1) + 2n + 2 = 2n2 + 4n
Como se trata de un grafo plano conexo, verifica la fórmula de Euler,
v + c = a + 2 =⇒ a = v + c− 2 = 2n2 + 4n + n2 + 1− 2 = 3n2 + 4n− 1
E.T.S.I.Informática Página 7
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
2. Teniendo en cuenta que un árbol recubridor tiene v − 1 aristas, éste tendrá 2n2 + 4n − 1 aristas, por lo
que habrá que eliminar a− v aristas:
3n2 + 4n− 1− (2n2 + 4n− 1) = n2
3. Śı es un grafo bipartito, ya que los únicos ciclos que contiene son de longitud par. En efecto, para formar
un ciclo, cada vez que nos desplacemos hacia un vértice a la derecha, hemos de realizar el mismo des-
plazamiento hacia la izquierda y por tanto tendrá un número par de aristas. En virtud de lo anterior, el
número cromático de Pn será χ(Pn) = 2. Igualmente y teniendo en cuenta que la máxima valencia de Pn
es 3, el ı́ndice cromático de Pn será χ
1(Pn) = ∆ = 3.
4. Teniendo en cuenta que el grafo es simétrico respecto de una ĺınea imaginaria que divida verticalmente la
columna central de celdillas y que el número de columnas verticales en que quedan divididos los vértices
es par, concretamente 2(2n − 1) + 2 = 4n, el número de vértices de columnas impares coincidirá con el
número de vértices de columnas pares. En cuanto al estudio de P2, la Figura 9 muestra el árbol de camino
alternado obtenido a partir del emparejamiento inicial y nos muestra el emparejamiento completo obtenido
produciendo el correspondiente cambio en el camino alternado x1 − x2 − x4 − x6 − x9 − x12 − x14 − x16.
El grafo P2 si verifica la condición de Hall, ya que admite un emparejamiento completo.
x
1
x
4
x
13
x
12
x
11
x
10
x
9
x
8
x
7
x
6
x
5
x
3
x
2
x
16
x
15
x
14
x
1
x
3
x
2
x
4
 x
5
x
6
 x
7
 x
8
x
9
 x
10
 x
11
x
12
 x
13
x
14
 x
15
x
16
Figura 9:
5. El grafo Pn es euleriano si y sólo si n = 1, ya que en otro caso tiene vértices de valencia 3. Igualmente Pn
es hamiltoniano si y sólo si n = 1, ya que si tratamos de encontrar un ciclo Hamiltoniano en Pn (n > 1)
y empezamos dicho ciclo en x1, al llegar a x4 o x5 tenemos las opciones x6, x7, x8, por lo que al volver de
nuevo al punto x5 o x4 dejaŕıamos uno de los vértices x6, x7, x8 sin visitar.
Ejercicio 2
(2.1) Sea G un grafo sin ciclos con p vértices y q aristas.
1. Probar que si q = p− 1, entonces G es un árbol.
2. Si q < p− 1, ¿puede ser G conexo?. Justificar la respuesta.
(2.2) Se considera el siguiente algoritmo, que toma como dato de entrada un grafo G = (V, A) conexo, ponderado
de p vértices y q aristas.
P1 S ← ∅
P2 Tomar una arista a ∈ A de peso mı́nimo de entre las que verifiquen que a /∈ S y (V, S∪{a}) no tenga
ciclos; entonces S ← S ∪ {a}
E.T.S.I.Informática Página 8
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
P3 Si |S| = p− 1, entonces el proceso termina y retorna como salida T = (V, S). En otro caso, volver a
P2.
Nota: En todo lo que sigue, G denotará el grafo entrada del algoritmo y T el grafo salida.
1. Ejecutar este algoritmo sobre el grafo siguiente:
g g
1
g
g
g
2 2
6
2
5 5
3 4
u v
w
x
y
2. Probar que si |S| < p − 1 y (V, S) no tiene ciclos, entonces existe una arista de G, a, satisfaciendo
que a /∈ S y (V, S ∪ {a}) no tiene ciclos. Deducir que el algoritmo termina siempre. ¿Cuantas veces
son necesarias ejecutarse P2 para que el algoritmo termine?.
3. Probar que T es un árbol recubridor de G.
4. Para cualquier arista a denotaremos su peso por ω(a). Se define el peso de G, ω(G), como la suma
de los pesos de cada una de sus aristas. Denotaremos por a1, a2, . . . , ap−1 las aristas de T ordenadas
según se van incorporando a S en el algoritmo.
Sea H un árbol recubridor de G de peso mı́nimo; (esto es, si F es cualquier árbol recubridor de G,
entonces ω(H) ≤ ω(F ) ). Supongamos que H 6= T y que ai es la primera arista de T que no está en
H .
a) Probar que G′ = H ∪ {ai} posee un ciclo.
b) Probar que existe una arista a′ del ciclo del apartado anterior que no está en T , verificando que
T ′ = G′ − {a′} es un árbol recubridor de G y ω(a′) ≤ ω(ai).
c) Deducir que ω(a′) = ω(ai) por la construcción de T según el algoritmo.
d) Probar que ω(H) = ω(T ′).
e) Haciendo uso del apartado anterior, probar que T es un árbol recubridor de peso mı́nimo para
G.
Solución.
(2.1) 1. Si T = (V, A) es un grafo aćıclico, de forma que sus números p de vértices y q de aristas verifican
q = p− 1, probemos que T es conexo. Si T no fuera conexo, sean T1 = (V1, A1), . . . Tk = (Vk , Ak) sus
componentes conexas. Obviamente p = |V | = |V1|+ · · ·+ |Vk| y q = |A| = |A1|+ · · ·+ |Ak|.
Sean v1 ∈ V1, v2 ∈ V2, . . ., vk ∈ Vk un vértice de cada una de las componentes conexas. Si al grafo T
le añadimos, como muestra la Figura 10, las k−1 aristas {v1, v2}, {v2, v3}, . . . , {vk−1, vk} obtenemos
un grafo que ya es conexo y que sigue sin tener ciclos, por lo tanto es un árbol. Pero el número de
aristas de este árbol seŕıa q+k−1 y por lo tanto tendŕıamos la contradicción de disponer de un árbol
que no verifica la propiedad T.5. Por lo tanto el grafo T ha de ser conexo y se trata de un árbol.
2. Si fuera conexo, seŕıa un árbol. Pero esto es contradictorio con el hecho de que q < p− 1.
(2.2) Demostración extráıda del texto:
“Applied and Algorithmic Graph Theory”de G. Chartrand y O.R. Oellermann
1. Se obtiene el árbol de aristas S = {{u, v}, {y, x}, {u, w}, {u, x}} (véase la Figura 11).
E.T.S.I.Informática Página 9MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
v
1
 v
2
v
k
(V
1
,A
1
)
(V
2
,A
2
)
(V
k
,A
k
)
Figura 10: Todo grafo sin ciclos con nv − 1 aristas es conexo.
5
y
u
 v
x
w
5
2
6
4
3
2
1
2
Figura 11:
2. Si |S| < p− 1 y (V, S) no tiene ciclos, entonces (V, S) no puede ser conexo, ya que si lo fuera seŕıa un
árbol, lo que es contradictorio con el hecho de tener un número de aristas inferior a p−1. Por lo tanto
(V, S) tiene al menos dos componentes conexas C1 y C2. Ahora bien, como el grafo G es conexo, ha
de existir una arista a que une un vértice de C1 con otro de C2 y tenemos entonces que (V, S ∪ {a})
no tiene ciclos. Según la demostración anterior, el algoritmo tendrá fin, ya que está garantizado que
podemos llevar a cabo el paso P2 cada vez que pase por él. Este algoritmo terminará cuando pase
por P2 un total de p− 1 veces.
3. Al terminar el algoritmo tenemos un grafo T = (V, A), con el mismo conjunto de vértices que el grafo
inicial G, por lo tanto será un subgrafo recubridor de G. Además este grafo T = (V, A) no tiene ciclos
y conserva la relación |A| = |V | − 1 y por tanto será un árbol. Por tanto T es un árbol recubridor de
G.
4. Sea T = (V, A), siendo A = {a1, a2, . . . , ap−1}, el árbol recubridor proporcionado por el algoritmo. Sea
H un árbol recubridor de peso mı́nimo de G. Supongamos que H fuera distinto del árbol recubridor
T . Sea ai la primera arista de T que no está en H .
a) El grafo G′ = H ∪ {ai} es conexo. Además como H es un árbol, tiene p − 1 aristas, por lo que
el grafo G′ tiene p aristas, por lo tanto debe contener un ciclo C, que obviamente contendrá la
arista ai.
b) Además este ciclo debe contener una arista a′ no contenida en T , ya que de lo contrario el ciclo
E.T.S.I.Informática Página 10
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
C estaŕıa contenido en T . Por otro lado T ′ = G′ − {a′} es conexo y tiene p− 1 aristas, luego es
un árbol recubridor de G, cuyo peso viene dado por
w(T ′) = w(H) + w(ai)− w(a′)
Como H es mı́nimo, w(T ′) ≥ w(H), por lo que w(ai) ≥ w(a′).
c) Ahora bien, ai es la arista de menos peso de G, de forma que {a1, a2, . . . , ai−1} ∪ {ai} no tiene
ciclos. Pero {a1, a2, . . . , ai−1} ∪ {a′} ⊆ H y por tanto no tienen ciclos, por lo que w(ai) ≤ w(a′).
Tenemos por tanto que w(ai) = w(a
′).
d) Como w(T ′) = w(H) + w(ai)− w(a′), tenemos que w(T ′) = w(H).
e) Si T no fuera un árbol recubridor de peso mı́nimo, tomaŕıamos como árbol H el árbol recubridor
de peso mı́nimo que tenga el mayor número de aristas en común con T . Como este árbol H seŕıa
distinto de T podŕıamos seguir los pasos anteriores y llegaŕıamos a una contradicción, ya que el
nuevo árbol T ′ tiene una arista más en común con T que el árbol H .
E.T.S.I.Informática Página 11
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
Septiembre de 2000
Ejercicio 1
Sea G = (V, A) un grafo conexo, plano con p vértices y q aristas. Denotaremos por ni el número de vértices de
valencia i.
1. Probar que q ≤ 3p− 6.
2. Probar que
∑
i≥1
(6− i)ni ≥ 12. Ayuda:
∑
i≥1
ni = p,
∑
i≥1
ini = 2q.
3. Probar que G contiene, al menos, un vértice u de valencia menor o igual que cinco.
4. Supongamos que G− {u} admite una vértice-coloración con cinco colores. Probar que:
a) Si δ(u) < 5, o bien, si δ(u) = 5 pero dos de los vértices adyacentes a u están coloreados con un mismo
color para la 5-coloración de G− {u}, entonces G admite una vértice-coloración con cinco colores.
b) Si δ(u) = 5 donde para la 5-coloración de G − {u} los vértices adyacentes a u que denotamos por
{z1, z2, z3, z4, z5} tienen colores diferentes, suponemos que zi está coloreado con el color i. Definimos
el conjunto S formado por los vértices de colores 1 o 3 que están conectados a z1 por caminos formados
por vértices de colores 1 o 3.
Probar que si en S intercambiamos el color 1 por 3. La 5-coloración de G−{u} no se ve alterado.
Probar que si z3 no pertenece a S, entonces G admite una vértice-coloración con cinco colores.
5. Suponiendo en el apartado d,2) que en el caso en que z3 ∈ S, también se pueda obtener una vértice-
coloración de G con cinco colores. Probar que todo grafo plano, conexo admite una vértice coloración con
cinco colores.
Solución:
1. Está demostrado en teoŕıa.
2.
∑
i≥1
(6− i)ni =
∑
i≥1
6 ni −
∑
i≥1
i ni = 6 p− 2q ≥ 12, utilizando el apartado anterior.
3. Según el apartado anterior
∑
i≥1
(6− i)ni ≥ 12 > 0, entonces
6n0 +5n1+4n2 +3n3+2n4+n5 +
∑
i≥6
(6− i)ni > 0 =⇒ 6n0 +5n1+4n2+3n3 +2n4+n5 >
∑
i≥7
(i−6)ni > 0
Por lo que alguno de los números no negativos n0, n1, n2, n3, n4, n5 ha de ser no nulo y por lo tanto debe
haber al menos un vértice u con valencia menor o igual que 5.
4. Demostración extráıda del texto:
“Applied and Algorithmic Graph Theory”de G. Chartrand y O.R. Oellermann
Tengamos una vértice-coloración de G− {u}, con cinco colores.
a) Si u es un vértice con valencia δ(u) < 5 (o con valencia δ(u) = 5 pero dos de sus vértices adyacentes
tienen el mismo color en la coloración de G−{u}), uno de los colores de dicha coloración no está siendo
utilizado por ninguno de los vértices adyacentes a u, por lo que podremos asignar dicho color al vértice
u y tendremos una vértice-coloración de G con 5 colores.
b) Sea δ(u) = 5, de forma que los vértices adyacentes a u, z1, z2, z3, z4, z5, tienen colores diferentes, por
ejemplo cada zi tiene el color i (véase la Figura 12).
E.T.S.I.Informática Página 12
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
u
z
1
z
5
z
4
z
3
z
2
1
 2
3
4
5
3
1
3
1
1
2
4
2
 5
S
3
2
Figura 12:
Si no pudiéramos intercambiar los colores 1 y 3 en S seŕıa debido a que algún vértice y de S,
por ejemplo de color 1, es adyacente a un vértice w, de color 3, que no está en S. Pero esto es
imposible, ya que entonces este nuevo vértice es un vértice conectado a u con un camino formado
por vértices coloreados con 1 y 3. Por lo tanto se puede alterar los colores 1 y 3 en los vértices
de S y seguiŕıamos teniendo una vértice-coloración de G− {u} con 5 colores.
Si z3 /∈ S, al cambiar los colores de los vértices de S, tendŕıamos que z1 y z3 tendŕıan asignados
el color 3, por lo que podemos asignar a u el color 1 y tendŕıamos una vértice-coloración de G
con 5 colores.
5. En este caso podŕıamos probar que todo grafo plano conexo es 5-coloreable. Procederemos por inducción:
Todo grafo de un número de vértices p ≤ 5 es 5-coloreable. Supongamos que la propiedad es cierta para
cualquier grafo con p vértices. Sea G un grafo con p + 1 vértices. Según hemos visto anteriormente, G ha
de tener un vértice u con valencia menor o igual que 5, entonces el grafo G − {u} tiene p vértices y por
tanto 5-coloreable. Siguiendo el proceso descrito anteriormente podemos obtener una vértice-coloración
de G con 5 colores.
Ejercicio 2
Consideremos un juego completo de dominó compuesto por 28 fichas que son todos los pares de combinaciones
posibles entre los elementos {0, 1, 2, 3, 4, 5, 6}. El juego consiste en concatenar las fichas por un lado común.
1. Tomando como vértices los elementos {0, 1, 2, 3, 4, 5, 6}, ¿qué representa una ficha?, ¿cuáles son las fichas
que se corresponden con los lazos?. Identificar el grafo que se obtiene con todas las fichas, sin dibujarlo.
2. Usando el grafo obtenido en el apartado anterior, demostrar que se puede concatenar las 21 fichas que no
son dobles (sin dibujarlo). ¿Se pueden concatenar todas las fichas?.
3. Consideremos ahora sólo aquellas fichas que contengan a un elemento impar y a un elemento par a la vez.
Decir de qué grafo se trata. ¿Se pueden concatenar todas estas fichas?. Razonar la respuesta.
4. En el juego clásico de dominó (en el que se reparten las 28 fichas entre 4 jugadores y sucesivamente van
poniendo una ficha cada uno de ellos) en un momento determinado se cierra el juego (no se puedenponer
más fichas por ningún extremo). Demostrar que cada componente conexa del grafo que resulta de eliminar
las aristas correspondientes a las fichas utilizadas, es euleriano. Como consecuencia, deducir que en un
cierre de dominó, el número de puntos que resta sin jugar ha de ser necesariamente par.
5. Representemos de otro modo el juego completo de dominó. Los vértices del grafo serán las fichas del do-
minó y existirá una arista entre dos vértices si las fichas correspondientes se pueden concatenar. ¿Se puede
encontrar un ciclo hamiltoniano en este grafo?. ¿Se cumple la condición suficiente de grafo hamiltoniano
(teorema de Hamilton)?.
E.T.S.I.Informática Página 13
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
Solución:
1. Cada ficha será una arista del grafo. Las fichas dobles serán lazos que unen un vértice consigo mismo. Se
trata del grafo K7 con un lazo en cada vértice.
2. Concatenar fichas significa encontrar dos aristas incidentes en un vértice. Por lo tanto nos preguntan si
el grafo formado por las 21 fichas no dobles es euleriano. La respuesta es afirmativa ya que la valencia de
cada vértice es δ(v) = 6 y por tanto par. Śı se pueden concatenar todas las fichas, ya que en la solución
anterior bastaŕıa incorporar el lazo, correspondiente a la ficha doble n−n en cualquier unión de dos aristas
incidentes en el vértice n.
3. En este caso el conjunto de vértices lo podemos dividir en dos V1 = {0, 2, 4, 6} y V2 = {1, 3, 5}, siendo
V = V1 ∪V2 y el grafo será K4,3. En este caso no se pueden concatenar todas las fichas, ya que la valencia
de los vértices {0, 2, 4, 6} es impar δ(2n) = 3 y por tanto no es un grafo euleriano.
4. Si el juego se cierra tendremos un circuito (secuencia de aristas incidentes, comenzando y terminando en
un mismo vértice). Entonces en cada vértice incide un número par de estas aristas, por lo que al eliminar
dichas aristas, la valencia de los vértices ha disminuido en un número par, por lo que dichos vértices siguen
siendo de valencia par y todas las componentes conexas del grafo resultante son eulerianas.
5. El grafo que aqúı se describe es el grafo de ĺınea del grafo original. Por lo tanto como el grafo original es
euleriano, el grafo de ĺınea es hamiltoniano. No obstante este grafo G′ no verifica la condición suficiente
de grafo hamiltoniano, ya que tiene 28 vértices y la valencia de cada vértice m n es
δ(m n) =
{
12 si m 6= n
6 si m = n
Por lo tanto δ(G′) = 6 < 14 y no verifica la condición suficiente.
E.T.S.I.Informática Página 14
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
27 de noviembre de 2000
Ejercicio 1
Se considera el grafo G que tiene por matriz de adyacencia:
0 0 0 1 1 1 1 0
0 0 0 0 1 1 1 1
0 0 0 0 0 1 1 1
1 0 0 0 0 1 1 1
1 1 0 0 0 0 0 1
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
0 1 1 1 1 0 0 0
Se pide:
1. Demostrar que el grafo es conexo, construyendo un árbol recubridor mediante la búsqueda en profundidad.
2. Estudiar si el grafo admite circuitos o recorridos Eulerianos y Hamiltonianos y en caso afirmativo hallarlos.
3. Responder a la pregunta anterior si se añade una arista entre el vértice 3 y el vértice 5.
Solución:
1. La Figura 13 muestra el árbol recubridor DFS.
1
 4
 6
 2
 5
 8
 3
 7
1
4
6
2
5
8
 3
7
Figura 13:
2. δ(1) = 4, δ(2) = 4, δ(3) = 3, δ(4) = 4, δ(5) = 3, δ(6) = 4, δ(7) = 4 y δ(8) = 4. Por lo tanto el grafo no
admite circuito euleriano, pero śı admite un recorrido euleriano (tiene dos vértices impares y los demás
pares). El algoritmo de Euler-1 nos aporta el recorrido euleriano:
3–7–4–8–2–5–8–3-6–2–7–1–4–6–1–5
Śı admite un ciclo hamiltoniano. Basta añadir al árbol obtenido en el apartado a, la arista 7–1, es decir:
1–4–6–2–5–8–3–7–1
La Figura 14 muestra el ciclo hamiltoniano.
3. Si se añade la arista 3–5, el grafo es euleriano y por tanto admite un circuito euleriano. Sigue lógicamente
siendo hamiltoniano.
E.T.S.I.Informática Página 15
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
1
4
6
2
5
8
 3
7
Figura 14:
Ejercicio 2
El responsable de organización académica de un centro en el que se imparte una diplomatura está tratando
de diseñar un calendario de exámenes en el que se utilice el mı́nimo número de d́ıas posible. En cada uno de
los tres cursos hay 4 asignaturas, que etiquetamos según el orden natural (en primero, {1, 2, 3, 4}; en segundo,
{5, 6, 7, 8}; y en tercero, {9, 10, 11, 12}). Aparte de las incompatibilidades propias entre las asignaturas de un
mismo curso, se da la siguiente lista de incompatibilidades:
La asignatura 5 es incompatible con las asignaturas 2, 3, 4, 10, 11, 12.
La asignatura 6 es incompatible con las asignaturas 2 y 10.
La asignatura 7 es incompatible con la asignatura 11.
Se pide:
1. Calcular una distribución de asignaturas por d́ıas de exámenes que utilice el menor número posible de
d́ıas.
2. Hay disponibles tres aulas, con capacidad para 50, 100 y 150 alumnos, respectivamente. La relación de
matriculados por asignatura es la siguiente:
Asignatura 1 2 3 4 5 6 7 8 9 10 11 12
N. alumnos 100 125 110 115 105 75 60 50 25 45 35 40
¿Se puede llevar a cabo la distribución hallada en el apartado anterior? En caso negativo, encontrar una
distribución válida en el menor número de d́ıas.
Solución:
1. La Figura 15 muestra una vértice–coloración del grafo del problema con 4 colores (a, b, c y d), obtenida
utilizando el algoritmo voraz de coloración de vértices con el orden natural de los vértices. Por lo que
χ(G) ≤ 4, pero como el grafo contiene a K4, χ(G) ≥ 4. Por lo tanto χ(G) = 4 y la vértice–coloración
ofrecida es óptima en cuanto al número de colores. Por lo tanto una solución del problema con el menor
número de d́ıas es la siguiente:
Dı́a Asignaturas
1 1, 5 y 9
2 2, 7 y 10
3 3, 6 y 11
4 4, 8 y 12
E.T.S.I.Informática Página 16
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
1
12
11
10
9
8
7
 6
5
4
3
2
(a)
(b)
(c)
(d)
(a)
(c)
(b)
(d)
(d)
(c)
(b)
(a)
Figura 15:
2. Sirve la misma distribución, si llamamos 1 al aula grande, 2 a la mediana y 3 a la pequeña:
Dı́a Aula 1 Aula 2 Aula 3
1 5 1 9
2 2 7 10
3 3 6 11
4 4 8 12
Ejercicio 3
Para 0 ≤ r ≤ 5, sea Gr = (V, Ar) el grafo regular cuyos vértices son todos los números binarios de 5 cifras
V = {(x1, . . . , x5) : xi ∈ {0, 1}},
y en el que dos vértices son adyacentes si se diferencian en exactamente r posiciones,
Ar = {uv : u = (u1, . . . , u5), v = (v1, . . . , v5), u 6= v,
5
∑
i=1
|ui − vi| = r}.
Se pide:
1. Calcular el número de vértices de Gr y sus valencias.
2. Calcular el número de aristas de G0. Deducir de qué grafo se trata.
3. Estudiar todas las propiedades del grafo G5.
4. Demostrar que G1 es conexo y bipartito.
5. Probar asimismo que G2 no es conexo y tiene exactamente dos componentes conexas.
Solución:
1. |V | = 25 = 32. Son todos grafos regulares de valencias:
δ(v) =



0 si r = 0
(
5
r
)
si r 6= 0 =















0 si r = 0
5 si r = 1
10 si r = 2
10 si r = 3
5 si r = 4
1 si r = 5
E.T.S.I.Informática Página 17
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
2. G0 no tiene aristas, se trata del grafo trivial formado por 32 vértices aislados.
3. G5 es un grafo formado por 16 componentes conexas, todas ellas isomorfas a P2.
4. En efecto. Dados dos vértices cualesquiera, siempre existe un camino entre ellos. Si u = (u1, . . . , u5) y
v = (v1, . . . , v5) son dos vértices cualesquiera. Podemos “transformar.el primero de ellos en el segundo
cambiando en cada paso uno de los elementos ui que lo difieren de v. Cada una de estas transformaciones
representan una arista del grafo G1. Además es bipartito, ya que el conjunto de vértices V se pueden
partir en dos subconjuntos independientes de vértices
V1 = {(x1, . . . , x5) :
5
∑
i=1
es impar} V2 = {(x1, . . . , x5) :
5
∑
i=1
es par},
5. Este grafo está formado pordos componentes conexas, cuyos conjuntos de vértices respectivos son
V1 = {(x1, . . . , x5) :
5
∑
i=1
es impar} V2 = {(x1, . . . , x5) :
5
∑
i=1
es par},
E.T.S.I.Informática Página 18
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
19 de Junio de 2001
Ejercicio 1
Para cada n ≥ 3, sea Pn la figura formada por tres poĺıgonos regulares concéntricos de n lados cada uno, unidos
por los vértices del siguiente modo:
�
�
�
�
�
�
�
�
�
�
�
�
�
��T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T�
�
�
�
�
�
�
�
�
�
T
T
T
T
T
TT�
�
�
�
�
��
Q
Q
Q
Q
Q
������
t
t
rst
sv ss ut
tuu
@
@
@ �
�
�
@
@
@�
�
�
ct u t u u
t
t u
t ss t t
P3 P4
1. Determinar para cada n, el mı́nimo número de colores necesarios para una vértice-coloración adecuada.
2. Demostrar que para todo n, el mı́nimo número de colores necesarios para una arista-coloración es 4.
3. ¿Existe un emparejamiento completo en Pn para n impar?
4. Dar un emparejamiento completo para P4. Generalizarlo para Pn, con n par.
5. Enunciar la condición de Hall y razonar si se verifica para los grafos Pn.
6. Usando el algoritmo de búsqueda en anchura, obtener el árbol recubridor para P3 con ráız en el vértice 0.
Solución:
1. La Figura 16 nos muestra cómo χ(P2k−1) = 3 y χ(P2k) = 2.
2. Véase la Figura 17.
3. Imposible. Tienen un número impar de vértices.
4. Véase la Figura 18.
5. Se verifica para los grafos P2k.
6. Véase la Figura 19.
Ejercicio 2
1. Sea G un grafo 3–regular y hamiltoniano. Se pide:
a) Probar que G tiene un número par de vértices.
b) Demostrar que admite una arista coloración con tres colores.
c) ¿Es G euleriano?
2. Dado un grafo G = (V, A), llamemos L(G) (grafo ĺınea de G) al grafo cuyos vértices son las aristas (ai ∈ A)
de G y donde {ai, aj} es una arista de L(G) si ai y aj tienen en G un vértice común. Se pide:
a) Probar que K4 y L(K4) son hamiltonianos.
E.T.S.I.Informática Página 19
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
1
2
3
4
5
6
7
8
9
1
2
3
14
13
12
11
10
9
8
7
6
5
4
15
1
7
6
5
4
 3
2
2
1
3
12
11
10
 9
8
4
14
13
12
11
10
9
8
7
6
5
18
17
16
15
Figura 16:
Figura 17:
b) Demostrar que si un grafo G es hamiltoniano entonces su grafo ĺınea L(G) también lo es.
c) ¿Es cierto el rećıproco del teorema anterior? Si no lo es, poner un contraejemplo.
E.T.S.I.Informática Página 20
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
1
7
6
5
4
 3
2
2
1
3
12
11
10
 9
8
4
14
13
12
11
10
9
8
7
6
5
18
17
16
15
Figura 18:
0
1
2
3
4
5
6
7
8
0
1
 2
3
4
5
6
 7
8
Figura 19:
Solución:
1. a) Teniendo en cuenta que la suma de valencias es par, como cada vértice tiene valencia 3, no puede
tener un número impar de vértices.
b) Si el grafo es hamiltoniano, existe un ciclo que contiene a todos sus vértices. Podemos colorear las
aristas de este ciclo con dos colores (y están incluidos todos los vértices), ya que este ciclo tiene un
número par de aristas. El resto de aristas puede ser coloreado con el tercer color, ya que serán sólo
incidentes a aristas ya coloreadas, pues están incluidos todos los vértices.
c) No puede ser euleriano pues tiene vértices impares (todos ellos).
2. a) La Figura 20 muestra los grafos K4 y L(K4). En el primero de ellos el ciclo a− b− c− d− a es un
ciclo hamiltoniano, mientras que en el segundo los es el ciclo a1 − a6 − a2 − a3 − a4 − a5 − a1.
b) Si G es hamiltoniano entonces admite un ciclo v1− v2− · · · − vn− v1. Si ordenamos las aristas según
el orden previsto por este ciclo: en primer lugar las aristas a11, . . . , a1i1 incidentes en v1, siendo a11
la arista vn − v1 y a1i1 la arista v1 − v2, en segundo lugar las aristas a21, . . . , a2i2 incidentes con v2
que no lo son con v1,siendo a2i2 la arista v2 − v3, en tercer lugar las aristas a31, . . . , a3i3 incidentes
con v3 no incidentes ni con v1 ni con v2, siendo a3i3 la arista v3 − v4 y aśı sucesivamente. El grafo de
ĺınea tiene como ciclo a11, . . . , a1i1 , a21, . . . , a2i2 , a31, . . . , a3i3 , . . . , a11.
c) No es verdad. Basta encontrar un grafo G euleriano que no sea hamiltoniano, como el de la Figura 21,
ya que si G es euleriano entonces L(G) es hamiltoniano y tendŕıamos L(G) hamiltoniano sin serlo G.
Ejercicio 3
La red de ordenadores de una determinada empresa se puede representar por un grafo ponderado donde los
E.T.S.I.Informática Página 21
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
K
4
a
d
 c
b
a
1
a
2
a
3
a
4
 a
5
a
6
a
1
 a
2
a
3
a
4
a
5
a
6
L(K
4
)
Figura 20:
a
1
a
3
a
1
 a
2
a
3
a
4
a
5
a
6
L(G
)
a
2
a
6
a
5
a
4
G
Figura 21:
pesos de las aristas vienen dados por la longitud de los cables en metros.
B C D E F G H I
A 5 5 2
B 2 2
C 2 2
D 3 3
E 3 4
F 3
1. ¿Se trata de un grafo plano?. En caso afirmativo calcular el número de caras.
2. ¿Es bipartito?, ¿es árbol?. Razonar la respuesta.
3. Calcular el número de aristas que seŕıa necesario eliminar para obtener un árbol recubridor del grafo.
4. Usar el algoritmo del camino más corto para determinar el camino mı́nimo desde el terminal A al terminal
D.
5. ¿Se puede mandar un mensaje desde el terminal I que recorra todos los demás terminales, pasando una
sola vez por cada terminal?. En caso afirmativo decir cuál seŕıa el camino.
Solución:
1. Śı es plano. La Figura 22 nos muestra una inmersión en el plano. Tiene v = 9 vértices y a = 12 aristas,
por tanto tiene c = a + 2− v = 5 caras.
E.T.S.I.Informática Página 22
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
A
B
I
H
G
F
E
D
C
5
5
2
2
2
2
2
 3
3
3
4
3
Figura 22:
2. No es bipartito ya que contiene ciclos de longitud impar. No es un árbol por el mismo motivo.
3. Un árbol recubridor tendŕıa v − 1 = 8 aristas, por lo que es necesario eliminar 4 aristas.
4. Siguiendo el algoritmo de Dijkstra, se obtiene d(A, D) = A − E − D = 5. La Figura 23 nos muestra el
resultado de la ejecución de dicho algoritmo.
A
I
H
G
F
E
D
C
5
5
2
2
2
2
2
 3
3
3
4
3
0,-
4,E
2,A
5,E
 8,D
5,E
8,F
6,E
4,E
B
A
E
B
 F
C
 D
 H
G
 I
3
2
2
2
3
3
4
3
Figura 23:
5. No. El grafo no contiene ningún camino hamiltoniano ya que tiene más de dos vértices de valencia 1: I ,
H y G.
E.T.S.I.Informática Página 23
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
7 de Septiembre de 2001
Ejercicio 1
Dada la siguiente figura:
�
�
���
#
"
 
!
w w u
uu
uu
uuu
uu
uu uu uu
u
u
Se pide:
1. Indicar el mı́nimo número de vértices necesarios que hay que añadir para transformar el multigrafo de la
figura en un grafo que llamaremos grafo G.
2. ¿Es posible pintar las ĺıneas del grafo G, con una carretilla, sin levantarla ni repintar ninguna ĺınea?. En
caso de no ser posible, ¿cuántas veces hay que levantar la carretilla como mı́nimo?.
3. Sea H un grafo cualquiera conexo con exactamente h vértices de valencia impar, razona cuántas veces
como mı́nimo hay que levantar el lápiz del papel para dibujarlo sin pasar dos veces por la misma arista.
4. Demuestra que dado un grafo cualquiera H’ se cumple que H’ es bipartito si y sólo si no hay tres vértices
u, v, w verificando que u y v son adyacentes y d(u, w) = d(v, w), (d(x, y) = { número de aristas del camino
más corto que une x e y }).
5. Usando el resultado del apartado anterior, di si el grafo G es bipartito.
Solución:
1. Hay que convertir las aristas múltiples en simples. Por lo que habrá que añadir 6 aristas, indicadas con
fondo blanco en la Figura: ex070901-1-a, donde se indica la valencia de cada vértice.
2
2
2
3
3
3
3
2
3
3
2
2
4
4
2
2
3
3
3
3
3
3
2
2
3
3
u
v
w
Figura 24:
E.T.S.I.Informática Página 24
MATEMÁTICA DISCRETA Colección de exámenesCurso 2007/2008
2. El grafo G tiene 14 vértices de valencia impar. Por lo que habrá que describir 7 recorridos independientes
para recorrer todos los vértices. Tendremos por tanto que levantar como mı́nimo 6 veces la carretilla.
3. Como en todo recorrido, los únicos vértices impares son los vértices primero y último, en total serán
necesario h2 recorridos para pasar por todos los vértices, luego el número de veces que habrá que levantar
el lápiz será h2 − 1.
4. Veamos la doble implicación: Si H ′ es bipartito H ′ = (V1 ∪ V2, A), entonces dados u, v adyacentes, si
u ∈ V1, v ∈ V2,. Entonces d(u, w) y d(v, w) tienen distinta paridad, por lo que no existen los tres vértices
en las condiciones mencionadas. Por el contrario, si no existen tres vértices en las condiciones mencionadas,
entonces no puede existir un ciclo de longitud impar. En efecto si existieran ciclos de longitud impar, en
el de menor número de aristas tendŕıamos tres vértices en las condiciones mencionadas.
5. Por ejemplo los tres vértices u, v, w indicados en la Figura 24 cumplen la condición mencionada, por lo
que G no es bipartito.
Ejercicio 2
Sea G = (V, A) un grafo e I un conjunto independiente en V (si no hay en I dos vértices adyacentes).
1. Probar que
∑
x∈I
δ(x) ≤ |A|.
2. Supongamos que G es hamiltoniano y sea C un ciclo hamiltoniano. Probar que el número de aristas de A
que no están en C es mayor o igual que
∑
x∈I
(δ(x)− 2) =
∑
x∈I
δ(x)− 2|I |.
3. Demostrar que si |A| −
∑
x∈I
δ(x) + 2|I | < |V | entonces G no es hamiltoniano.
4. Tomando un conjunto independiente I y utilizando el resultado del apartado c), probar que el grafo
siguiente no es hamiltoniano.
eu u
u
eu
u
u
u u
u u
u
Grafo de Herschel
Solución:
1. El número de aristas incidentes en vértices del conjunto independiente será la suma de las valencias de
sus vértices, ya que al contabilizar cada una de ellas no aparecen repetidas, ya que no existe ninguna que
tenga ambos vértices en I . Entonces:
∑
x∈I
δ(x) ≤ |A|
2. A cada x ∈ I , al eliminar las aristas de C, le quedan δ(x)− 2 aristas y además estas aristas no son aristas
incidentes en ningún otro vértice de I , por lo que el número de aristas de A que no están en C será:
|A| − |V | ≥
∑
x∈I
(δ(x)− 2) =
∑
x∈I
δ(x)− 2|I |
3. Es consecuencia del apartado anterior.
E.T.S.I.Informática Página 25
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
a
b
c
d
e
Figura 25:
4. El conjunto independiente I = {a, b, c, d, e} de la Figura 25 verifica la desigualdad anterior, por lo que el
grafo de Herschel no puede ser hamiltoniano.
Ejercicio 3
Un departamento de una empresa tiene establecidas dos redes locales de comunicación distintas entre sus ocho
terminales. Las ĺıneas de conexión de cada red están esquematizadas en los siguiente grafos:
u u u
w u
uu
u u u
u
uue
u
u
1 2 3
4
567
8
A B C
D
EFG
H
u
Red I Red II
1. Analizar si los grafos que representan las redes I y II son isomorfos.
2. En el grafo de la red I, ¿se pueden conectar los terminales evitando que haya superposición de las ĺıneas
de conexión?. ¿Y en el grafo de la red II?.
3. Se pretende colocar etiquetas en los terminales de modo que dos terminales conectadas directamente a
través de la red II reciban etiquetas distintas. ¿Cuál es el mı́nimo número de etiquetas necesarias?.
4. Comprobar que el grafo de la red I es bipartito y encontrar un emparejamiento completo para el mismo.
5. Hallar el camino de longitud mı́nima desde el terminal A hasta el terminal C en la red II, donde la longitud
de los enlaces (en metros) viene dada por la tabla adjunta.
B C D E F G H
A 6 13 5
B 7 8 6
D 8 5 12
F 11 10 9
G 6 10
Solución:
1. No lo son. El segundo grafo tiene ciclos de longitud 3 y el primero no.
E.T.S.I.Informática Página 26
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
2. El grafo I no es plano, pero el segundo śı. La Figura 26 nos muestra que el primer grafo contiene a K3,3
y una inmersión del segundo grafo.
A
G
F
E
D
C
B
H
1
8
7
6
5
4
3
2
Figura 26:
3. Se necesitarán al menos 3 etiquetas, ya que χ(G) = 3 (véase la Figura 27).
A
G
F
E
D
C
B
H
Figura 27:
4. Los vértices están divididos en impares y pares.
5. Siguiendo el algoritmo de Dijkstra se obtiene el camino mı́nimo A−B − C, de longitud 13.
E.T.S.I.Informática Página 27
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
26 de Noviembre de 2001
Ejercicio 1
Se define la suma de el grafo G1 = (V1, A1) con el grafo G2 = (V2, A2) como un nuevo grafo
G1 + G2 = (V, A) donde V = (V1 ∪ V2) y A = A1 ∪ A2 ∪ { {u1, u2} : u1 ∈ V1, u2 ∈ V2}
s
s
s s
s s
s
s s
s
G1 G2 G1 + G2
���
���
�
�
�
�
��XXXXXX
���
���
c
c
c
c
cc
XXXXXX
Se pide probar las siguientes propiedades:
1. G1 + G2 es siempre conexo.
2. G1 y G2 son grafos completos si y sólo si G1 + G2 es un grafo completo.
3. Si G1 y G2 son grafos que tienen caminos hamiltonianos entonces, G1 + G2 es hamiltoniano.
4. Si G admite una vértice-coloración con k colores entonces, G + G admite una vértice-coloración con 2k
colores.
5. Si G consiste en un conjunto de n vértices aislados, decir de qué grafo se trata G + G. Razonar cual es el
mı́nimo número de colores necesarios y suficientes para dar una vértice-coloración de G + G. Idem para
una arista-coloración.
6. Dar una condición necesaria y suficiente en G para que G + G sea euleriano.
Solución:
1. Veamos que dados dos vértices u, v ∈ V1 ∪ V2 cualesquiera de G1 + G2, siempre existe un camino entre
ellos: Si u ∈ V1 y v ∈ V2 (o viceversa), existe la arista {u, v} ∈ A en G1 + G2. En cambio si u, v ∈ V1
(alternativamente u, v ∈ V2), sea w ∈ V2 (alternativamente w ∈ V1) un vértice cualquiera. Entonces existen
las aristas {u, w}, {v, w} ∈ A por lo que existe el camino u− w − v en G1 + G2 y el grafo es conexo.
2. Si G1 y G2 son completos, todos sus vértices son adyacentes entre śı, como en G1 + G2 añadimos todas
las aristas que unen vértices de G1 con vértices de G2, dados dos vértices cualquiera de G1 + G2, serán
adyacentes y el grafo G1 + G2 será completo. Si por el contrario G1 + G2 es un grafo completo, también
lo serán G1 y G2, ya que las únicas aristas que se añaden al grafo G1 + G2 que no están en los grafos G1
y G2 unen un vértice de G1 y otro de G2.
3. Si G1 admite el camino hamiltoniano u1−u2−· · ·−un (que recorre todos los vértices de G1) y G2 admite
el camino hamiltoniano v1 − v2 − · · · − vn (que recorre todos los vértices de G2), entonces el ciclo
u1 − u2 − · · · − un − v1 − v2 − · · · − vn − u1
será un ciclo hamiltoniano en G1 + G2 y por tanto G1 + G2 es hamiltoniano.
4. Si G admite una vértice–coloración con k colores, sean c1, c2, . . . , ck los colores de una vértice coloración
de G1 = G y ck+1, ck+2, . . . , c2k un vértice–coloración de G2 = G, entonces la vértice–coloración de colores
c1, . . . , c2k es una vértice–coloración de G + G con 2k colores.
5. En este caso el grafo G + G es el grafo bipartito completo Kn,n y por tanto su número cromático es
χ(Kn,n) = 2 y su ı́ndice cromático es χ
1(Kn,n) = ∆ = n.
E.T.S.I.Informática Página 28
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
6. Sea G=(V, A) un grafo cualquiera. Si dado un vértice v ∈ V , denotamos por δ(v) y δ ′(v) las valencias de
dicho vértice en G y G + G, respectivamente, entonces δ′(v) = δ(v) + |V |:
G + G euleriano =⇒ δ′(v) = δ(v) + |V | es par, ∀v ∈ V =⇒



δ(v) es par y |V | es par, ∀v ∈ V
ó
δ(v) es impar y |V | es impar, ∀v ∈ V
pero esta última condición es imposible, por lo tanto
G + G euleriano =⇒ G euleriano y |V | es par
Veamos que esta condición es suficiente:
{
G euleriano =⇒ δ(v) es par, ∀v ∈ V
|V | es par
}
=⇒ δ′(v) = δ(v) + |V | es par, ∀v ∈ V =⇒ G + G euleriano
Por lo tanto. la condición necesaria y suficiente para que G + G sea un grafo euleriano es que G sea un
grafo euleriano con un número par de vértices.
Ejercicio2
Dado el grafo G = (V, A) con V = {v2, v3, . . . , v30}, donde vi es adyacente con vj si y sólo si m.c.d(i, j) 6= 1 con
2 ≤ i < j ≤ 30.
1. Razonar si G es conexo. ¿Cuántas componentes conexas tiene?
2. Determinar, razonadamente, el mayor n para el cual, Kn es subgrafo de G.
3. Sea Ḡ el complementario de G. Razonar si Ḡ es bipartito. Razonar si Ḡ es conexo.
4. Probar que G y Ḡ no son planos.
Solución:
1. No es conexo, ya que por ejemplo v17 es un vértice aislado. Tiene 5 componentes conexas, cuyos conjuntos
de vértice son V2 = {v17}, V3 = {v19}, V4 = {v23}, V5 = {v29} y V1 el resto de vértices del grafo.
2. Para que Kn sea subgrafo de G debe haber n vértices mutuamente adyacentes, por lo que sus sub́ındices
deben ser n números no primos entre śı. El mayor caso posible nos lo dan los números pares 2, 4, . . . , 30
que son no primos entre śı, por lo que K15 es subgrafo de G.
3. Ḡ = (V, (̄A)), siendo {vi, vj} ∈ (̄A) si y sólo si i y j son primos entre śı. Este grafo no es bipartito, ya que
{v2, v3}, {v3, v5}, {v5, v2} ∈ (̄A) son aristas del nuevo grafo, por lo tanto (̄G) contiene el ciclo v2− v3− v5.
El grafo Ḡ es conexo ya que, por ejemplo, el vértice v29 es adyacente a todos los demás.
4. G no es plano ya que, como vimos anteriormente, contiene a K15. Igualmente, como 2, 3, 5, 7, 11 son
mutuamente primos entre śı, los vértices v2, v3, v5, v7, v11 son mutuamente adyacentes en Ḡ y por lo tanto
Ḡ no es plano, ya que contiene a K5.
Ejercicio 3
3.1 Sea h ∈ Z, h ≥ 3. Si G = (V, A) es un grafo plano conexo, siendo v su número de vértices, a su número
de aristas y tal que cada ciclo tiene, al menos, h aristas. Se pide:
1. Probar que a ≤ h
h− 2(v − 2). (Ayuda: 2a ≥ hc donde c es el número de caras de G)
2. ¿Cual es la longitud mı́nima de un ciclo en K3,3 y en K5?
3. Usando los resultados anteriores probar que K3,3 y K5 no son planos.
E.T.S.I.Informática Página 29
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
3.2 Probar que si G = (V, A) es un grafo plano con l componentes conexas, v vértices, a aristas y c caras
entonces, se verifica: v − a + c = l + 1.
Solución:
3.1 1.
2a ≥ hc
c = a + 2− v
}
=⇒ 2a ≥ h(a + 2− v) =⇒ a ≤ h(v − 2)
h− 2
2. Las longitudes mı́nimas de los ciclos son h = 4 en K3,3 y h = 3 en K5.
3. En K3,3 tenemos v = 6, a = 9 y h = 4, por lo que
h(v − 2)
h− 2 = 8 < a = 9, por lo que no puede ser
plano. Igualmente en K5 tenemos v = 5, a = 10 y h = 3, por lo que
h(v − 2)
h− 2 = 9 < a = 10, por lo
que no puede ser plano.
3.2 Sean Gi = (Vi, Ai) (i = 1, . . . , l) las componentes conexas de G y sean vi, ai, ci los vértices, aristas y
caras, respectivamente, de cada componente conexa Gi. Como cada componentes conexa es un grafo
plano conexo, vi + ci = ai + 2. Entonces:
l
∑
i=1
(vi + ci) =
l
∑
i=1
(ai + 2) =⇒
l
∑
i=1
vi +
l
∑
i=1
ci =
l
∑
i=1
ai + 2l
Pero
l
∑
i=1
vi = v,
l
∑
i=1
ai = a y
l
∑
i=1
ci = c + (l − 1), ya que la cara exterior es considerada l veces. Entonces
v + c + (l − 1) = a + 2l, por lo que v − a + c = l + 1.
E.T.S.I.Informática Página 30
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
13 de Junio de 2002
Ejercicio 1
En el siguiente grafo las aristas representan los vuelos que oferta una compañ́ıa aérea entre diversas ciudades.
qs
s
s s s s
s ss
s
ss
s
s
s
s
s
s
�
�
�
�
�
T
T
T
J
J
J
��
(((((
E
E
EE
������
C
C
CC�
�
�
�L
L
LL�
�
��
hhhh �
��
�
�
�� �
�
�
�e
e
e
((((�
�
�
�
����
1
2
3
4
5
6
7
8
9 10 11 12
13
14
15 16
17
18
��
���
1. Estudiar, razonadamente, si una misma tripulación puede servir todos los vuelos sin repetir ninguno,
volviendo a la ciudad de partida. En caso negativo, ¿cuántos vuelos habŕıa que añadir y entre qué ciudades
para poder subsanar tal eventualidad? Determinar, por medio del algoritmo apropiado, un itinerario de
modo que la tripulación asista todos los vuelos programados en el grafo del dibujo.
2. 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, decidir cuántos vuelos habŕıa que fletar y entre qué ciudades para propiciar tal circunstancia.
Solución.
1. Dado que los vuelos vienen representados por las aristas del grafo, el problema que nos plantean se traduce
en la existencia de un circuito euleriano. Dado que el grafo es claramente conexo y hay exactamente dos
vértices de valencia impar (el 4 y el 14), el grafo admite un recorrido euleriano, con vértices extremos
4 y 14, aunque no un circuito euleriano. De este modo, para que la tripulación pudiera servir todos los
vuelos sin repetir ninguno, comenzando y terminando en la misma ciudad, bastaŕıa añadir un solo vuelo,
entre las ciudades marcadas con los vértices 4 y 14. Si añadimos la arista que representa este vuelo,
podŕıamos aplicar el algoritmo para construir el circuito euleriano, de modo que prescindiendo de tal
arista obtendŕıamos un recorrido euleriano entre los vértices 4 y 14. Este algoritmo busca identificar el
grafo dado como la unión por vértices de varios ciclos, tomando como base los vértices de unión. Más
concretamente, construido en una etapa un circuito con todas sus aristas distintas, se busca un vértice
de ese circuito que sea incidente con alguna de las aristas que están fuera del circuito (i.e., un vértice
no aislado) y se busca un ciclo con origen dicho vértice y cuyas aristas no pertenezcan al circuito dado.
Ahora, se inserta el ciclo en cuestión en el circuito y se repite el proceso hasta que todas las aristas del
grafo se hayan utilizado en el circuito. El proceso, desde luego, no es único. Por ejemplo, podemos realizar
los siguientes pasos:
Comenzando en el vértice 1, construimos el ciclo
C = {1, 5, 4, 9, 8, 10, 11, 12, 13, 14, 15, 7, 6, 1},
y consideramos el grafo obtenido del original al prescindir de las aristas utilizadas.
El primer vértice no aislado es el 4, de modo que insertamos en el camino anterior el ciclo {4, 2, 3, 4},
para obtener aśı el circuito
C = {1, 5, 4, 2, 3, 4, 9, 8, 10, 11, 12, 13, 14, 15, 7, 6, 1}.
Aún aśı, 4 sigue siendo un vértice no aislado, de modo que podemos insertar en C el ciclo {4, 8, 7, 11, 14, 4},
donde la última arista representa el vuelo a añadir que comentáramos previamente.
E.T.S.I.Informática Página 31
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
El siguiente vértice no aislado es el 15, de modo que insertamos en C el ciclo {15, 16, 17, 18, 15}. De
este modo todas las aristas han sido consideradas y obtenemos el circuito euleriano C dado por:
{1, 5, 4, 8, 7, 11, 14, 4, 2, 3, 4, 9, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 15, 7, 6, 1}.
Un recorrido euleriano entre los vértices 4 y 14 seŕıa, entonces:
{4, 2, 3, 4, 9, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 15, 7, 6, 1, 5, 4, 8, 7, 11, 14}.
2. En cuanto al segundo apartado, ahora el problema se traduce en encontrar un ciclo hamiltoniano, que
claramente no existe dado que {4, 2, 3, 4} y {15, 16, 17, 18, 15} son ciclos que sólo tienen en común con el
resto del grafo los vértices 4 y 15, respectivamente. Más aún, los vértices 4 y 15 constituyen vértices de corte
del grafo. Por tanto, al menos habŕıa que añadir dos nuevas aristas para subsanar estas irregularidades.
De hecho, dos aristas bastan: por citar un ejemplo de entre las multitudes opciones, las aristas {3, 9} y
{17, 7}.
Ejercicio 2
1. Sea G un grafo con χ(G− u− v) = χ(G)− 2 para todo par de vértices u, v de G. Probar que G ha de ser
una grafo completo. ¿Es cierto el rećıproco? Probarlo, en caso afirmativo, o dar un contraejemplo en caso
contrario.
2. Se dice que un grafo G es sensible para el color si χ(H) < χ(G) para todo subgrafo propio H de G (esto
es, con H 6= G). Se pide:
a) Demostrar que todo grafo sensible para el color ha de ser conexo.
b) Probar que todo grafo G posee un subgrafo H ⊆ G sensible para el color con el mismo númerocromático, χ(H) = χ(G).
Solución.
1. Sea G un grafo con χ(G − u − v) = χ(G) − 2 para todo par de vértices u, v de G. Vamos a demostrar
que G es necesariamente un grafo completo. En efecto, si hubiera dos vértices u, v en G no adyacentes, G
admitiŕıa una vértice coloración con ¡χ(G) − 1 colores!: los χ(G) − 2 colores que garantiza el enunciado
para G − u− v y un color adicional, a lo sumo, para los vértices u y v (que seŕıa suficiente, por tratarse
de vértices no adyacentes). Rećıprocamente, todo grafo completo verifica esta propiedad: si a un grafo
completo de n ≥ 2 vértices le quitamos un par de vértices, obtenemos el grafo completo de n− 2 vértices,
cuyo número cromático es n− 2 = χ(Kn)− 2.
a) Está claro que un grafo sensible para el color ha de ser conexo, necesariamente: en un grafo G
no conexo, el número cromático viene dado por el mayor de entre los números cromáticos de sus
componentes conexas, de modo que el subgrafo de G dado por una (no tiene por qué ser única)
componente conexa de mayor número cromático verifica que χ(H) = χ(G), con H 6= G.
b) Si un grafo no es sensible para el color, es porque posee un subgrafo propio H con el mismo número
cromático. Pensemos en el siguiente procedimiento, que toma como dato de entrada un grafo dado
G. Mientras G no sea sensible para el color.
Sea H un subgrafo propio de G con χ(H) = χ(G).
Hacer G = H.
Fin mientras.
Devolver H. El procedimiento anterior es finito, dada la finitud del grafo G inicial; y está bien
definido en virtud de la noción de grafo no sensible para el color. Esto demuestra la existencia, para
todo grafo G, de un subgrafo H ⊆ G sensible para el color.
E.T.S.I.Informática Página 32
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
Ejercicio 3
Se considera el siguiente grafo:
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
s
@
@
@
@
@
@�
�
�
�
�
�HHHHHHHHHHHH
�
�
�
�
�
�
�
�
�
�
�
�
A
A
A
A
AA
�
�
�
�
�
�
@
@
@
@
@
@�
�
�
�
�
�@
@
@
@
@
@
�
�
�
�
�
�
A
A
A
A
A
A�
�
�
�
��
x1 x2 x3 x4 x5 x6 x7 x8
y8y7y6y5y4y3y2y1
1. Estudiar la conexión del grafo anterior, realizando una búsqueda en profundidad con ráız el vértice x1.
2. Determinar un emparejamiento maximal para el grafo dado, comenzando con el emparejamiento
{{x1, y2}, {x2, y4}, {x4, y3}, {x5, y5}, {x7, y7}}. ¿Es completo el emparejamiento obtenido? Refrendar la
respuesta dada aplicando la condición de Hall. ¿Se trata del único emparejamiento maximal? Razonar la
respuesta.
3. Demostrar que todo grafo no plano ha de verificar alguna de estas dos condiciones:
a) Contiene al menos 5 vértices de valencia mayor o igual que 4.
b) Contiene al menos 6 vértices de valencia mayor o igual que 3.
4. Demostrar que el grafo dado es plano. ¿Se le puede aplicar la fórmula de Euler? Razonar la respuesta.
Solución.
1. Si realizamos una búsqueda en profundidad con ráız el vértice x1, obtenemos las siguientes ramas:
Primera rama: {x1, y2, x3, y3, x4, y5, x5}.
Segunda rama: {y5, x7, y7}.
De donde el grafo no es conexo. De hecho, tiene dos componentes conexas: la anterior y la formada por el
camino simple {y1, x2, y4, x6, y8, x8, y6.
2. Al emparejamiento dado se le puede añadir la arista {x8, y8}, puesto que ambos vértices no estaban
emparejados. Llamemos M al nuevo emparejamiento. Para determinar si es maximal o existe alguno con
más aristas buscamos si admite algún camino alternado. Los únicos vértices que no están emparejados
aún son x3 y x6. Con origen en x3 realizamos una búsqueda en anchura:
Nivel 0: {x3}, vértice no emparejado.
Nivel 1: {y2, y3, y7}, todos ellos emparejados en M .
Nivel 2: {x1, x4, x7}, parejas de vértices en el nivel anterior.
Nivel 3: {y5}, único vértice no utilizado previamente adyacente a alguno de los del nivel anterior
(más concretamente, a x4).
Nivel 4: {x5}, pareja del único vértice del nivel anterior.
La búsqueda en anchura termina, puesto que los vértices adyacentes a x5 ya están emparejados. Por tanto,
no existe un camino alternado para M con comienzo en x3. Hagamos lo propio con x6. Con origen en x6
realizamos una búsqueda en profundidad:
Nivel 0: {x6}, vértice no emparejado.
Nivel 1: {y4, y8}, todos ellos emparejados en M .
Nivel 2: {x2, x8}, parejas de vértices en el nivel anterior.
Nivel 3: {y1, y6}, ninguno de los cuales está emparejado.
E.T.S.I.Informática Página 33
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
Con comienzo en x6 tenemos dos caminos alternados distintos, lo que nos produce dos emparejamientos
distintos con una arista más que M , con más que realizar una de las dos siguientes sustituciones en M :
La arista {x2, y4} por las aristas {x6, y4} y {x2, y1}.
La arista {x8, y8} por las aristas {x6, y8} y {x8, y6}.
Cualquiera de los dos nuevos emparejamientos obtenidos es maximal, puesto que con comienzo en x3
no admiten ningún camino alternado. De este modo, el grafo no tiene ningún emparejamiento completo,
por lo que no puede verificar la condición de Hall. De hecho, si consideramos el conjunto de vértices de
la componente conexa hallada en el apartado primero del problema, P = {x1, x3, x4, x5, x7} y T (P ) =
{y2, y3, y5, y7} resulta que |P | = 5 > 4 = |T (P )|.
3. Téngase en cuenta que una subdivisión añade sólo vértices en el interior de aristas, de modo que no
modifica en absoluto la valencia de los vértices del grafo original. De este modo, los vértices originales de
K5 y K3,3 mantienen su valencia en cualquier subdivisión. Aśı, demostrar la propiedad que nos pide este
apartado consiste en una simple aplicación del T eorema de Kuratowski: si un grafo no es plano es porque
contiene un subgrafo isomorfo a una subdivisión bien de K5, bien de K3,3. En el primer caso, tendŕıa al
menos 5 vértices de valencia 4 y en el segundo tendŕıa al menos 6 vértices de valencia 3.
4. Dado que el grafo del enunciado no contiene ni 5 vértices de valencia mayor o igual que 4, ni 6 vértices de
valencia mayor o igual que 3; según el apartado anterior ha de ser necesariamente plano. Por otro lado,
como no es conexo, no se puede aplicar la fórmula de Euler, que sólo es válida para grafos conexos planos.
E.T.S.I.Informática Página 34
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
13 de Septiembre de 2002
Ejercicio 1
Dos personas, A y R, se plantean un juego en el que primero se dibujan n puntos aleatoriamente en el plano.
Después, cada jugador va dibujando alternativamente aristas: el jugador A las dibuja en color azul y el jugador
R en rojo. Pierde el primero que dibuje un triángulo de un solo color. Se pide:
1. Demostrar que si en el transcurso del juego se pintan de un mismo color tres aristas incidentes en un
mismo vértice, entonces el juego concluye sin empate.
2. Deducir que si n ≥ 6, entonces siempre hay un jugador que pierde. Probar que si 3 ≤ n ≤ 5 el juego puede
quedar en tablas.
Solución.
1. Supongamos que en el desarrollo del juego en un vértice v1 resultan ser incidentes tres aristas del mis-
mo color (llamémosle C), que tienen por extremos los vértices v2, v3 y v4. Supongamos que el juego
continuara sin acabar hasta completar todas las aristas posibles entre los n vértices (dando lugar a un
grafo completo Kn con sus aristas coloreadas con dos colores). Entre los cuatro vértices anteriores resta-
ban por dibujar aún tres aristas más, a saber, las que uńıan dos a dos los vértices v2, v3 y v4.
u
u
u
u��
�
�
�
�S
S
S
S
S
S��
v1
Si alguna de estas tres nuevas aristas fuera del mismo
color C que las incidentes en el vértice v1, daŕıa lugar a un triángulo monocolor, por lo que el juego habŕıa
acabado con un perdedor. Si ninguna de ellas es de color C, las tres son del otro color y formaŕıan entre
śı otro triángulo monocolor, por lo que también habŕıa acabado el juego con un perdedor. En definitiva,
de un modo u otro, el juego ha de acabar sin empate porque se llega a dibujar un triángulo monocolor.
2. Si n ≥ 6, cada vértice puede llegar a tenerhasta n − 1 ≥ 5 aristas incidentes en él, luego al menos
3 del mismo color. Por tanto, aplicando el apartado anterior, el juego ha de acabar con un perdedor,
necesariamente. Si n = 3, el jugador que sale dibujará dos aristas incidentes en un punto con el mismo
color y el otro jugador la arista que resta del ciclo de orden 3 con otro color; luego la partida siempre
acaba en empate en este caso. Si n = 4, la partida también puede acabar en empate. Sirva de ejemplo
la siguiente partida, en la que un jugador ha situado sus tres aristas en el peŕımetro de un cuadrado y
el otro ha rellenado las restantes aristas de K4:
u u
uu��
�
�
�
�
@
@
@
@
@
@
Si
n = 5, la partida nuevamente puede acabar en empate. Sirva de ejemplo la siguiente partida, en la que un
jugador ha situado sus aristas en el peŕımetro de un pentágono y el otro ha rellenado las restantes aristas
E.T.S.I.Informática Página 35
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
de K5:
u
u
uu
u
B
B
B
B
B
B
B
B
BQ
Q
Q
Q
Q
Q
Q
QQ ��
�
�
�
�
�
���
�
�
�
�
�
�
�
�bb
HH
HH
��
BB
��
!!
Ejercicio 2
Sea G un grafo plano conexo con v vértices, a aristas y c caras que verifica:
Todas las caras están limitadas por exactamente m aristas.
En cada vértice inciden n aristas, siendo n > 2.
1. Demostrar que 2 = a
(
2m−mn + 2n
mn
)
y deducir que 2m−mn + 2n > 0.
2. Demostrar que (m− 2)(n− 2) < 4 y que 3 ≤ n, m ≤ 5.
3. Demostrar que cualquier grafo con estas caracteŕısticas tiene a lo sumo 20 vértices.
Solución.
1. De un lado, por ser el grafo plano y conexo, la fórmula de Euler garantiza que c − a + v = 2. Por
otro, dado que todas las caras están limitadas por exactamente m aristas y cada arista pertenece a dos
caras simultáneamente, ha de ser 2a = mc. Además, como el grafo es n-regular, se tiene que 2a = nv,
según la relación existente entre aristas, vértices y valencias en un grafo. Despejando c y v de estas dos
últimas ecuaciones y sustituyendo los valores en la fórmula de Euler obtenemos que 2 = 2a
m
− a + 2a
n
.
Reduciendo a común denominador y sacando factor común a obtenemos el resultado buscado. Ahora,
dado que a, m, n > 0, resulta que 2m−mn + 2n = 2mn
a
> 0.
2. Desarrollando, obtenemos que
(m− 2)(n− 2) < 4⇔ mn− 2m− 2n + 4 < 4⇔ mn− 2m− 2n > 0,
que es la negación de la ecuación que se probó en el apartado anterior. Dado que n > 2, n − 2 ≥ 1, de
modo que ha de ser m − 2 < 4, de donde m > 6, es decir m ≤ 5. Por otro lado, como una cara de un
grafo plano está limitada como mı́nimo por tres aristas, ha de ser m ≥ 3. Según el enunciado ya es n ≥ 3.
Sólo resta probar que también es n ≤ 5. Como el valor mı́nimo de m es 3, despejando de la ecuación
(m− 2)(n− 2) < 4 llegamos a que n− 2 < 4, de donde n ≤ 5.
3. Sólo tenemos que probar para las distintas parejas de valores (n, m) con 3 ≤ n, m ≤ 5 y (m−2)(n−2) > 4,
cuántos vértices tienen los grafos que verifican las propiedades del enunciado. Para ello, despejaremos el
número de aristas de la ecuación del primer apartado y sustituiremos dicho valor en la ecuación v = 2a
n
.
Aśı, v = 4m2m−mn+2n . Posibles parejas:
(n, m) = (3, 3). Resulta v = 4.
(n, m) = (4, 3). Resulta v = 6.
(n, m) = (5, 3). Resulta v = 12.
(n, m) = (3, 4). Resulta v = 8.
(n, m) = (3, 5). Resulta v = 20.
Luego a lo sumo un tal grafo tiene 20 vértices. A modo de curiosidad, estos grafos existen para cada uno de
estos valores y se corresponden con los poliedros regulares, a saber: tetraedro, cubo, octaedro, dodecaedro
e icosaedro.
E.T.S.I.Informática Página 36
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
Ejercicio 3
Un operador por cable que aúna televisión y teléfono quiere introducirse en una comarca que consta de 8
poblaciones, que etiquetamos alfabéticamente desde la A hasta la H. En la siguiente tabla cada entrada indica
el número de rollos de cable que se han de utilizar para conectar entre śı las poblaciones correspondientes a
su fila y columna, sobrentendiendo que los huecos vaćıos corresponden a poblaciones que no pueden conectarse
directamente y que las entradas diagonales indican el número de rollos de cable que han de utilizarse para cubrir
el servicio en la población en cuestión.
A B C D E F G H
A 2 4 5
B 4 2 4
C 4 4 2 5 3
D 2 3 1 6
E 5 5 4 1 4
F 3 1 1 1 2 5
G 4 2 3 3
H 6 5 3 3
Se pide:
1. Determinar, mediante el algoritmo apropiado, cuál es el número mı́nimo de rollos de cable a utilizar y una
ruta para conectar las poblaciones A y H, sin necesidad de dar cobertura a las demás poblaciones por las
que la ĺınea pase.
2. Resolver el problema anterior si en esta ocasión śı se ha de cubrir el servicio en todas las poblaciones por
las que pase la ĺınea.
3. ¿Son únicas las rutas establecidas en los apartados anteriores? Razonar la respuesta.
Solución.
1. Sea G = (V, A) el grafo ponderado de 8 vértices, los cuales etiquetamos de A a H en correspondencia con
las poblaciones dadas, cuya matriz de adyacencia coincide con la tabla dada en el enunciado, a excepción
de la entrada diagonal. Determinar el número mı́nimo de rollos de cable a utilizar en una ruta que conecte
las poblaciones A y H sin dar cobertura a las poblaciones por la que pase la ĺınea, corresponde con
el problema de encontrar el camino más corto de A a H . Para determinar un tal camino, tomaremos
como base el vértice A y aplicaremos el procedimiento usual, de forma que en cada paso, sucesivamente,
tomaremos un vértice que dé la menor distancia con respecto a A y tomando como base ese nuevo punto
actualizaremos las distancias restantes. A continuación incluimos una tabla con todo el proceso.
A B C D E F G H Vértice Arista
0 - - - - - - - A -
- 4 - - 5 - - - B AB
- - 8 - 5 - - - E AE
- - 8 - - 6 9 - F EF
- - 8 7 - - 8 11 D FD
- - 8 - - - 8 11 C BC
- - - - - - 8 11 G FG
- - - - - - - 11 H FH
En el último paso, se comprueba que la distancia de G a H más la distancia de A a G coincide también
con 11, que era hasta entonces la menor distancia desde A hasta H , según el camino {A, E, F, H}. Aśı,
podemos concluir que la distancia más corta de A a H es 11 y se puede obtener por dos caminos distintos:
la alternativa al anterior viene dada por {A, E, F, G, H}. En definitiva, el número mı́nimo de rollos a
utilizar para conectar las poblaciones A y H , sin necesidad de dar cobertura a las demás poblaciones de
la ĺınea, es 11 + 2 + 3 = 16 rollos.
E.T.S.I.Informática Página 37
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
2. El problema que se nos plantea ahora es responder a la pregunta del apartado anterior, pero teniendo
en cuenta el número de rollos de cable que hay que utilizar en cada población por la que pase la ĺınea.
Este problema se podŕıa resolver igual que el anterior, pero sumando a cada arista el número de rollos
asociado a la población que corresponde al vértice de llegada de tal arista, según se recorre el camino.
También se podŕıa seguir un razonamiento del siguiente tipo para comprobar que el camino más corto
de A a H , contando el peso de cada vértice, ha de ser necesariamente {A, E, F, H}. Al vértice H sólo se
puede acceder desde los vértices D, F y G. Desde luego, los tendidos {F, H} y {G, H} utilizaŕıan 9 rollos
cada uno, mientras que {D, H} requeriŕıa el uso de 12 rollos. Suprimamos ahora H del grafo. De entre D,
F y G, la población que se conectaŕıa a A utilizando el menor número posible de rollos de cable seŕıa F ,
dado que:
El camino {A, E, F} requiere 13 rollos.
El camino más corto que conecte D con A habŕıa de pasar por F o por C. La primera opción
directamente nos diŕıa que D está de A más lejos que F . En cualquier caso, la segunda también,
porque o bien se llega a C por F , o a D a través de los caminos {A, B, C, D} ó {A, E, C, D}, que
requieren más de 13 rollos.
G sólo es adyacente a E, F y H . Dado que la arista EG pesa más que la arista EF , en cualquier
caso G está más lejos de A que el propio F .
Por lo tanto, el camino más cortode A a H pasa por F y nunca por D y G. Ahora, F sólo queda
adyacente a C y a E. Según la tabla que se hizo en el apartado anterior C dista 8 de A y pesa 4, mientras
que E dista 5 de A y pesa 4. Aśı, podemos concluir que el camino más corto que conecta A con F es,
efectivamente, {A, E, F}, de donde el camino más corto que conecta A con H es {A, E, F, H} y utiliza
2 + 5 + 4 + 1 + 1 + 5 + 3 = 21 rollos de cable.
3. Como se vio en los propios apartados anteriores, en el primer caso tenemos 2 posibles rutas, mientras que
en el segundo la solución śı es única.
Ejercicio 4
Un museo necesita comprar cámaras para vigilar 24 cuadros de una exposición, los cuales etiquetamos desde 1
hasta 24. Aunque algunas cámaras permiten vigilar más de un cuadro simultáneamente, no pueden ser vigilados
por una misma cámara aquellos cuadros cuyas etiquetas sean números cuyo máximo común divisor es distinto de
1 (esto es, no primos entre śı). Determinar razonadamente cuál es el menor número de cámaras que bastaŕıan para
completar la vigilancia y qué cuadros habŕıa de vigilar cada una de estas cámaras. ¿Son únicas las asignaciones
de vigilancia para dichas cámaras? Solución. Sea el grafo G = (V, A) de 24 vértices, en el que los vértices
representan los cuadros y las aristas unen pares de vértices que corresponden con cuadros que no pueden ser
vigilados por una misma cámara. Aśı, dos vértices x e y tienen una arista en común si y sólo si mcd(x, y) > 1.
Si hacemos corresponder a cada cámara un color y coloreamos los vértices según el color de la cámara que vigila
el cuadro correspondiente, resulta que encontrar el menor número de cámaras que bastaŕıan para completar la
vigilancia corresponde con el problema de encontrar una vértice coloración que utilice el menor número posible
de colores; de modo que se necesitarán tantas cámaras como número cromático tenga el grafo y vértices con
el mismo color corresponderán a cuadros que serán vigilados por la misma cámara. Si aplicamos el algoritmo
voraz al grafo, asignando el primer color libre, obtenemos la siguiente tabla:
V 1 2 3 4 5 6 7 8 9 10 11 12
C 1 1 1 2 1 3 1 4 2 5 1 6
V 13 14 15 16 17 18 19 20 21 22 23 24
C 1 7 4 8 1 9 1 10 5 11 1 12
De modo que 12 colores son suficientes, χ(G) ≤ 12. ¿Serán necesarios? Tal como se ha visto a la hora de aplicar
el algoritmo voraz, todos los cuadros que se corresponden con vértices pares presentan incompatibilidades 2 a
2 para ser vigilados por una misma cámara. Es decir, que el subgrafo formado por estos 12 vértices (todos los
pares) conforma un grafo completo K12. Dado que el número cromático de K12 es 12, el número cromático del
grado original ha de ser al menos 12, χ(G) ≥ 12. Concluimos, pues, que 12 ≤ χ(G) ≤ 12, de donde χ(G) = 12 y
12 es el menor número de cámaras que bastan para vigilar los cuadros. En la tabla anterior tenemos una posible
E.T.S.I.Informática Página 38
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
asignación de vigilancia de cada una de las 12 cámaras, por colores. Evidentemente, tal asignación no es única,
porque hay muchos cuadros que no presentan incompatibilidad con ningún otro: aquellos que se corresponden
con vértices aislados en el grafo y que resultan ser los números primos y la unidad, 1, 2, 3, 5, 7, 11, 13, 17, 19, 23.
Cualquiera de estos cuadros puede ser vigilado por cualquiera de las cámaras.
E.T.S.I.Informática Página 39
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
29 de Noviembre de 2002
Ejercicio 1
Los vértices de un árbol se pueden organizar por capas de la siguiente manera: en la capa 0 (o exterior) se sitúan
los vértices hoja (de valencia 1); en la capa 1 se sitúan los vértices que se convierten en hojas al eliminar del
árbol los de la capa 0; y sucesivamente, en la capa i se sitúan los vértices que se convierten en hojas al eliminar
del árbol los vértices de las capas anteriores. La última capa se denomina capa interior y sus vértices conforman
el centro del árbol. El siguiente algoritmo pretende calcular el centro de un árbol dado.
ENTRADA: Un árbol T = (V, A).
T ′ = T
Mientras T ′ conste de más de dos vértices
T ′ ← grafo que se obtiene al eliminar de T ′
todos los vértices de valencia 1
Fin Mientras
SALIDA: T ′
Se pide:
1. Hacer un seguimiento del algoritmo para los árboles T1 y T2 dados por:
(a) V1 = {1, 2, 3, 4, 5, 6}, A1 = {(1, 2), (1, 3), (1, 4), (4, 5), (5, 6)}.
(b) V2 = {1, 2, 3, 4, 5, 6, 7, 8}, A2 = {(1, 2), (1, 3), (1, 4), (2, 5), (2, 6), (3, 7), (5, 8)}.
2. Probar que si en un árbol de más de dos vértices se eliminan todos los vértices de valencia 1 se obtiene
un nuevo árbol.
3. Probar que el número de vértices de valencia 1 en un árbol es mayor o igual que 2, a excepción del árbol
que consta de un solo vértice.
4. Demostrar que el algoritmo funciona y es finito. Discutir las posibles salidas a que da lugar.
5. Concluir que el centro de un árbol está formado por uno o dos vértices.
Solución.
1. (a) Al realizar un seguimiento del algoritmo aplicado al árbol T1, se obtiene:
Inicialmente, T ′ = (V ′, A′) = T1 = (V1, A1) y por tanto consta de 6 vértices, tres de ellos hojas
(a saber, 2, 3 y 6).
Dado que T ′ tiene 6 > 2 vértices, se eliminan de T ′ todas las hojas, de modo que T ′ = (V ′, A′),
con V ′ = {1, 4, 5} y A′ = {(1, 4), (4, 5)}, que consta de tres vértices, dos de ellos hojas (1 y 5).
Como T ′ tiene ahora 3 > 2 vértices, el algoritmo realiza una segunda iteración, de modo que
V ′ = {4} y A′ = ∅.
Ahora T ′ consta de un solo vértice, por lo que el algoritmo para y se obtiene como salida
T ′ = ({4}, ∅).
(b) Un seguimiento del algoritmo aplicado al árbol T2 viene dado por:
Inicialmente, T ′ = (V ′, A′) = T2 = (V2, A2) y por tanto consta de 8 vértices, cuatro de ellos
hojas (a saber, 4, 6, 7 y 8).
Dado que T ′ tiene 8 > 2 vértices, se eliminan de T ′ todas las hojas, de modo que T ′ = (V ′, A′),
con V ′ = {1, 2, 3, 5} y A′ = {(1, 2), (1, 3), (2, 5)}, que consta de cuatro vértices, dos de ellos hojas
(3 y 5).
Como T ′ tiene ahora 4 > 2 vértices, el algoritmo realiza una segunda iteración, de modo que
V ′ = {1, 2} y A′ = {(1, 2)}.
Ahora T ′ consta de dos vértices, de modo que el algoritmo para y se obtiene como salida T ′ =
({1, 2}, {(1, 2)}).
E.T.S.I.Informática Página 40
MATEMÁTICA DISCRETA Colección de exámenes Curso 2007/2008
2. Recordemos que un árbol es un grafo conexo y sin ciclos. Por tanto, si en un árbol se eliminan vértices
(y las aristas que en ellos inciden) se obtiene otro grafo que asimismo no tiene ciclos. Para concluir que
al eliminar los vértices hoja de un árbol se obtiene otro árbol, basta entonces demostrar que el grafo
resultante sigue siendo conexo. Pero esto es inmediato, porque cualesquiera dos vértices del nuevo grafo
están conectados por el mismo camino que los conectaba en el árbol inicial, dado que las aristas y vértices
eliminados no pod́ıan aparecer en estos caminos (el camino habŕıa parado en el vértice extremo de la
arista de valencia 1).
3. En el árbol que consta de un solo vértice, obviamente dicho vértice tiene valencia 0. Para árboles con más de
un vértice, śı se tiene que el número de vértices de valencia 1 es mayor o igual que 2: a partir de la relación
entre vértices v, aristas a y valencia de vértices en un árbol, se tiene que
∑
x∈V
δ(x) = 2a = 2(v−1) = 2v−2.
Si no hubiera vértices de valencia 1, los v vértices tendŕıan valencia mayor o igual que 2 (un árbol es conexo,
por lo que no hay vértices de valencia 0), de modo que
2v − 2 =
∑
x∈V
δ(x) ≥ 2v,
lo que seŕıa una contradicción. Un razonamiento similar lleva a que no puede haber un solo vértice de
valencia 1, dado que en ese caso habŕıa v − 1 vértices de valencia al menos 2 y tendŕıamos
2v − 2 =
∑
x∈V
δ(x) ≥ 2(v − 1) + 1 = 2v − 1,
una nueva contradicción. Por tanto, en un árbol de más de un vértice hay al menos dos vértices hoja.
4. Según el apartado