matematicas discretas

Escuela T´cnica Superior
e
´
de Ingenier´ Informatica Curso 2007/2008
ıa

´
´
Coleccion de Examenes
de
´
Matematica Discreta

´
Depto. de Matematica Aplicada I

´
MATEMATICA DISCRETA

Colecci´n de ex´menes
o
a

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 aristasAn =
e
{{0, i} : 1 ≤ i ≤ 2n} ∪ {{2i − 1, 2i} : 1 ≤ i ≤ n}. As´ por ejemplo M4 ser´ el grafo
ı
ıa



4
3
2




D
D

D

D
  D


0
5
1



4 
4

4

4

 
4
6
7
8



1. ¿Para qu´ valores de n es Mn euleriano?
e
2. ¿Para qu´ valores de n admite Mn un recorrido euleriano?
e
3. Se define v´rtice de corte comoaquel, que al eliminarlo del grafo, aumenta el n´mero de componentes
e
u
conexas del mismo. Encontrar el n´mero de v´rtices de corte de Mn para todo n.
u
e
4. ¿Para qu´ valores de n es Mn hamiltoniano?
e
5. ¿Para qu´ valores de n admite Mn un camino hamiltoniano?
e
6. Calcular el n´mero crom´tico de Mn .
u
a
7. Dar un coloreado de aristas de Mn utilizando el menor n´mero de coloresposibles.
u
Soluci´n. La Figura 1 muestra los grafos molinillo M1 , M2 , M3 y M4 .
o
2

3

2
4

1

0

2

3

4

M2

M1

1

0

3

5

6

2

1

0

M3

4

5

0

M4

1

8
6

7

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 todoslos v´rtices son pares.
e

E.T.S.I.Inform´tica
a

P´gina 2
a

´
MATEMATICA DISCRETA

Colecci´n de ex´menes
o
a

Curso 2007/2008

2. Por la misma raz´n anterior, nunca admite un recorrido euleriano.
o
3. Si n = 1 el grafo no tiene v´rtices de corte, ya que se trata del ciclo C 3 . En cambio, si n > 1, el v´rtice 0
e
e
es un v´rtice de corte, ya que se trata de un grafoconexo y al eliminar el v´rtice 0 obtendr´
e
e
ı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.
e
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 unv´rtice de corte de forma que al ser
e
eliminado, el n´mero de componentes conexas del grafo aumenta en n ≥ 2 unidades.
u
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–
o
e
coloraci´n con tres colores, por lo que χ(Mn ) = 3.
o
7. Est´respondido en el apartado anterior.
a

Ejercicio 2
Responder a las siguientes cuestiones:
1. Se define estructura arb´rea como todo grafo obtenido a partir del siguiente proceso:
o
a) Un v´rtice aislado es una estructura arb´rea.
e
o
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,
o
n
e
e
resulta otra estructura arb´rea.
oDemostrar que un grafo T es un arbol si y solo si T es estructura arb´rea.
´
o
2. ¿Cu´ntas componentes conexas debe tener un grafo con 1200 v´rtices, 1000 aristas y sin ciclos? Describir
a
e
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
a
u
a
e
o no ciclos? Describirdicho grafo.
Soluci´n.
o
1. Es evidente que si un grafo T es una estructura arb´rea es conexo, ya que en cada paso a.2) se conserva
o
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,
o
a
u
e
u
ya que en el paso a.1) comenzamos con un v´rtice aislado y cada paso por a.2) aumenta tanto el n´mero
e
u
como el de aristas en una...