Ejercicios grafos

Ejercicios 1) Construir un grafo de orden 5 cuyos vértices tengan grados 1, 2, 2, 3, 4. ¿Cuál es el tamaño del grafo? 2) A una fiesta asisten 20 invitados. Cada uno de ellos conoce a un nºdiferente de invitados. ¿Es esto posible? Probar que todo grafo sin bucles de orden n≥2 tiene al menos dos vértices con el mismo grado. 3) En un mapa de carreteras de una región aparecen 25tramos de carretera. Sabiendo que los cruces de carretera se producen siempre en una población y que de cada lugar parten al menos cuatro caminos, ¿cuántos lugares aparecen en el mapa? 4) Si Ges un grafo simple con 52 aristas, ¿cuál es el menor número de vértices que puede tener G? 5) Dibujar los grafos simples no isomorfos de orden 4. 6) Disponemos de 6 ordenadores y 9 cables deconexión. Queremos que cada ordenador se conecte con otros 3 ordenadores. ¿Existe alguna forma de conectarlos? ¿Es única? 7) Determinar cuáles de los siguientes grafos son bipartidos:

8)9)

10) 11) 12) 13)

¿Cuántas aristas tiene un grafo simple si sus vértices tienen los siguientes grados 4,3,3,2,2? Dibuja tal grafo. Estudia si las siguientes sucesiones son gráficas:3,3,3,3,2 1,2,3,4,4 3,4,3,4,3 5,5,4,4,3,3,3,1,0,0 3,3,2,2,2,2,1,1 6,4,4,4,3,3,3,3 5,3,3,3,2,2,1,1 Estudia la regularidad de los grafos, Kn , Cn , W n y Qn para los diferentes valores de nDescribe todos los grafos no isomorfos cuya sucesión de grados sea 3,3,2,2,2. Sea G un grafo simple con n vértices y q aristas, cuyos vértices tienen grado k ó k+1. Demostrar que si G tiene n kvértices de grado k entonces n k =(k+1)n-2q Obtener la lista de adyacencia y las matrices de adyacencia e incidencia para los siguientes grafos:

14) Representa la matriz de adyacencia de cadauno de los siguientes grafos: b) K1,4 c) K2,3 a) K4 d) C4 e) W 4 f) Q3 15) Determinar cuáles de los siguientes pares de grafos son isomorfos:

a)

b)

a)

b)

a)

b)