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
10 de Diciembre de 1999

Curso 2007/2008

Ejercicio 1
Se denomina grafo molinillo de orden n, Mn , a un grafo con v´rtices Vn = {0, 1, 2, . . . , 2n} y aristas An = 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 como aquel, que al eliminarlo del grafo, aumenta el n´mero de componentese u u e 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? 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 colores posibles. u Soluci´n. La Figura 1 muestra los grafos molinillo M1 , M2 , M3 y M4 .o
2 4 3 2 4 3 2

0

1

M1
4

M2

0

1

5

0

1

3

2

6

M3

5

0

1

M4
6 7

8

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

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

P´gina 2 a

´ MATEMATICA DISCRETAColecci´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 grafo conexo y al eliminar el v´rtice 0 obtendr´ e e ıamos un grafo con n componentes conexas. 4. Para n = 1 el grafo eshamiltoniano, 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 un v´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 comotodo 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. o Demostrar 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 1200v´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? Describir dicho 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 yadem´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 unidad. Por lo tanto T es un arbol. Rec´ ´ ıprocamente, si T es un arbol, podemos ´ describirlo mediante una estructura arb´rea eligiendo, para empezar, uno cualquiera de sus...