Matemática Discreta

1.- Dado un grafo simple con n vértice y q aristas, expresar en función de n y q el número de aristas del grafo complementario.

2.- Demostrar que un grafo regular de grado impar tiene un númeropar de vértices. ¿Puede afirmarse algo similar de un grafo regular de grado par?

3.- Un grafo tiene 5 vértices de grados 1,2,2,3 y 4 respectivamente:
a) Calcular su número de aristas
b) Construirun ejemplo
c) Demostrar que todos los ejemplos son isomorfos.

4.- A una fiesta acuden 20 personas que pueden o no conocerse entre sí. Se entiende que la relación “conocerse” es simétrica: si Felipeconoce a Juana, entonces Juana conoce a Felipe. Demostrar que hay al menos dos personas con el mismo número de conocidos. (Indicación, probar que en todo grafo simple de orden mayor o igual que dos,hay al menos dos vértices del mismo grado). ¿Qué podemos decir sobre la primera cuestión si quitamos la condición de simetría a la relación “conocerse”?

5.- En el mapa de carreteras de una regiónaparecen 25 tramos de carretera. Los cruces se producen siempre en las poblaciones, y de cada población parten al menos 4 caminos. Determinar el máximo número de poblaciones del mapa.

6.- Determinarpara que valores de n es cierta la afirmación siguiente: Todos los grafos simples Hamiltonianos con n vértices y n+1 aristas son isomorfos.

7.- Determinar cuales de los siguientes pares de grafosson isomorfos




8.- Dar ejemplos de grafo conexo:
a) Euleriano no Hamiltoniano
b) Hamiltoniano no Euleriano con camino Euleriano abierto
c) Euleriano y Hamiltoniano
d) No Euleriano, concamino Euleriano abierto y sin camino Hamiltoniano abierto
e) No Euleriano, con un camino Euleriano abierto y sin camino Hamiltoniano abierto.
f) No Hamiltoniano, con un camino Hamiltoniano abierto ysin camino Euleriano abierto.
g) No Hamiltoniano ni Euleriano pero con caminos abiertos de ambos tipos.
h) Sin caminos Eulerianos ni Hamiltonianos

9.- Responder utilizando terminología de la...