Download TEMA 5 Grafos

TEMA
5
Grafos
Ejercicio 1. Expresa en forma matricial los grafos
v•HH
vv HHH
v
HH
v
HH
vv
•v)) v
•
))
))
))
)
•
•111
•
1
•11
11
11
1
•
11
11
1
•
•
•
Ejercicio 2. Representa gráficamente los siguientes grafos cuyas matrices de adyacencia son




0 1 0 1 1
0
1
1
1
1 0 1 1 1


1 0 0 0
0 1 0 0 0




1 0 0 1
1 1 0 0 0
1 0 1 0
1 1 0 0 0
Ejercicio 3. (*) Calcula las geodésicas que unen el vértice 4 con el vértice 9 en el grafo siguiente:
2
1
2
5
2
3
3
4


3 
2 
1 
2 
1




6 3 7 1 8
3
2
3
9
2
2
1
1
10
11
2
1
12
Ejercicio 4. Sea G un grafo completo con cuatro vértices. Construye todos sus subgrafos salvo isomorfismos.
Ejercicio 5. ¿Son isomorfos los grafos de la figura 1? ¿Y los de la figura 2? ¿Y los de la 3?
Figura 1:
◦?
◦
◦?
◦
◦
◦
◦
◦
??
??
??
?
1
?? 
??
 ??
 ?
2
Matemática Discreta
Figura 2:
◦
 ???
??


??


?

◦
◦ OOO
OOO ooooo
O
oo
O
oO
ooo OOOOO
o
o
o
◦
◦
◦
 //???

// ??

 // ???

 //
◦ // ◦
//
//
◦
◦
Figura 3:
◦ ?OOO
◦
◦
◦
?? OO
 ???
ooo
o

O
o
?? OOO 
?? ooo 
?o
?? OOO

??  OOO ooooo??? 
??
ooOoOOOO ???
?
 ?o??ooo
O

 ooo ??
OOOO ???


O
o
?? 
 o
OOO??
oooo

O
◦
◦
◦1
◦1
111
111
11
11 11
11
11
◦111
◦
11
11
11 11 1
1
◦
◦
Ejercicio 6. Encuentra un circuito de Euler para los grafos
a
 ???
??


??

?

c
b?
 ???
 ??


??
??


??
??


? 
?

e?
f?
d?
 ???
 ???
 ???



??
?


??
??


??
? 
? 

g
j
h
i
a
 ???
??


??

?

c
b OOO
o
OOO oooo
OOoo
ooo OOOOO
o
o
O
oo
e
d?

??


??
??

? 
f
Ejercicio 7. Encuentra un camino de Euler para los grafos
a
b?
 ???

 ???

??

??

?? 
??



e
c OOO
O
d OO
OOO ooooo
OOO ooooo
OoOo
OOoo
ooo OOOOO
ooo OOOOO
o
o
o
o
O
O
o
oo
g ?o
f ??
h
 ??

??
??


??


??

?? 
? 

j
i
a?
 ???

??


??

c
b?
??

??

??

? 
e
f?
d
 ???

??

??


g
h
Departamento de Álgebra
Tema 5. Grafos
3
Ejercicio 8. Determina cuáles de los siguientes grafos son planos
a
 //??
 //???

// ???
  //
b /oo c
ooo///
o
o
//
ooo
oooo
e
d
a/
///
//
//
b OOO
/ oc
O
ooo/
O
OOoOoOoo //
oo OOOO //
oooo
O
e
d
a OO
c
OOO b oooo
OOoOoo
oO
ooo OOOOO
ooo
e
d
f
a
c
b/
//
//
//
// e
d OOO
/
OOO
OOO //
OOO //
 OO
g
f
h
Ejercicio 9. Determina qué grafos de los que aparecen en el ejercicio 6 se pueden convertir en grafos
dirigidos de forma que dos vértices cualesquiera se puedan unir por medio de un camino dirigido.
Ejercicio 10. Se conocen los siguientes datos sobre las personas a, b, c, d, e, f y g:
1.
La persona a habla inglés.
2.
La persona b habla inglés y español.
3.
La persona c habla inglés, italiano y ruso.
4.
La persona d habla japonés y español.
5.
La persona e habla alemán e italiano.
6.
La persona f habla francés, japonés y ruso.
7.
La persona g habla francés y alemán.
¿Es cierto que cada par de personas se pueden comunicar entre ellas utilizando si, es necesario, a otra
persona como intérprete?
Ejercicio 11. Demuestra que en un grafo el número de vértices de grado impar es par.
Ejercicio 12. ¿Cuáles de los siguientes grafos contienen un circuito Hamiltoniano?
•
•
•
•





•
•
•
•
•
•
• OOO •
OOO
OOO
OOO
OO
•?
??
??
??
?
•
•
•
•
•
•
o•
ooo
o
o
oo
ooo
o
o
o
•
•
 ???

??

??

??


??

??


??


??

?


•?
•
•
??

??


??

??

??

??


??

??

? 
•
•
P. Jara, F. J. Lobillo, J. García, J. C. Rosales, J. Urbano
4
Matemática Discreta
Ejercicio 13. ¿Para qué valores de n el grafo Kn es un circuito de Euler?
Ejercicio 14. Obtén una fórmula para el número de lados de Km,n .
Ejercicio 15. ¿Para qué valores de m y n el grafo Km,n es un circuito de Euler?
Ejercicio 16. Demuestra que si n ≥ 3, entonces Kn contiene un circuito hamiltoniano.
Ejercicio 17. ¿Cuándo Km,n contiene un circuito de Hamilton?
Ejercicio 18. Demuestra que cualquier grafo con cuatro vértices o menos es siempre plano.
Ejercicio 19. Demuestra que si un grafo tiene a lo sumo cinco vértices y uno de ellos es de grado dos
entonces es plano.
Ejercicio 20. Calcular un árbol generador para los grafos del ejercicio 8.
Ejercicio 21. Demuestra que en cualquier árbol con dos o más vértices existe, al menos, un vértice de
grado uno.
Ejercicio 22. ¿Es cierto que todo grafo se puede colorear con, a lo sumo, cuatro colores?
Ejercicio 23. Demuestra que en todo grafo con más de un vértice existen dos vértices con el mismo
grado.
Ejercicio 24. Prueba que si un grafo G contiene sólo dos vértices de grado impar, entonces ambos han
de encontrarse en la misma componente conexa.
Ejercicio 25. ¿Existe algún grafo regular de grado cinco con veinticinco vértices?
Ejercicio 26. ¿Existe un grafo completo con quinientos noventa y cinco lados?
Ejercicio 27. ¿Depende el número de caras resultante de una representación plana de un grafo plano de
la representación que escojamos?
Ejercicio 28. ¿Existe un grafo con seis vértices cuyos grados sean uno, dos, dos, tres, cuatro y cuatro
respectivamente?
Ejercicio 29. Sea un grafo plano y conexo con nueve vértices de grados dos (tres veces), tres (tres veces),
cuatro (dos veces) y cinco. ¿Cuántos lados hay? ¿Y caras?
Ejercicio 30. ¿Es plano el grafo siguiente?
a/
/
//
//
//
f? // b ?
?? // ???
??

??

??
 //
??
?? 
?

g
c
 ???
??

??

?

e
d
h
Departamento de Álgebra
Tema 5. Grafos
Ejercicio 31. Calcula el dual del grafo
•





•?
•
•
??


??

??

? 
•
•
•





•
Ejercicio 32. Construye todos los árboles binarios completos con siete vértices.
Ejercicio 33. ¿Cuántas ramas tiene un árbol binario completo con treinta y cinco vértices?
P. Jara, F. J. Lobillo, J. García, J. C. Rosales, J. Urbano
5