Prueba de conceptos básicos de tg

Cuestionario acerca de nociones b´sicas de Teora de Grafos a

1. Dibuja los siguientes grafos: K5 , C6 , K3,2 , R7 siendo Rn con n ≥ 3 el grafo rueda de n + 1. 2. ¿Cu´les de las siguientesmatrices son a multigrafo?, ¿y de un digrafo?. En caso    0 1 0 0 1 2 1  0 0 1 1  2 1 0      1 0 1 1  1 1 2  0 0 1 1 1 0 1 la matriz de adyacencia de un grafo simple?, ¿y de un afirmativo,¿determinan un s´lo grafo o m´s de uno? o a      0 1 1 0 0 2 3 1  1 0 0 1   2 0 2 1         1 0 0 1   3 2 0 3   0 1 1 0 1 1 3 0

3. (a) ¿Cu´ntas aristas tiene Kn ?, ¿Y Km,n ? a 4. ¿Esposible que las siguientes listas representen los grados de los v´rtices de un grafo? Si s´ ¿cu´ntas e ı, a aristas y v´rtices tendr´ dicho grafo?, repres´ntalo, ¿Es unic?. e ıa e ´ a) (6, 5, 4, 3,2) b) (5, 3, 3, 2, 1, 0) c) (3, 3, 2, 1, 1, 1) d) (5, 5, 4, 2, 2, 2)

5. Hallar todos los grafos regulares 4-valentes con 7 v´rtices (salvo isomorfismos). e 6. ¿ Cu´ntos C5 contiene el grafo K4,7 ? a7. Dibuja el complementario de un C6 y de un K7 . 8. ¿Cu´les de los siguientes grafos son autocomplementarios? a

9. Hallar las componentes conexas en el grafo de v´rtices V = {0, 1, . . . , 9} yaristas e (a) A = {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}, {1, 4}, {4, 7}, {0, 8}, {3, 9}, {5, 8}} (b) A = {{0, 6}, {1, 2}, {1, 8}, {0, 9}, {2, 7}, {3, 4}, {3, 5}, {6, 9}, {7, 8}} 10. ¿Cu´l es el ´ aındice de conectividad (por v´rtices) del grafo siguiente? ¿Cu´l es el menor n´mero e a u de aristas que habr´ que a˜adir para aumentar dicho ´ a n ındice?, ¿entre qu´ v´rtices?. ¿Y e´ e e ındice deconectividad lineal?

11. Obt´n 5 subgrafos distintos conocidos del k5 , uno de ellos recubridor. e 12. Un bosque es un grafo sin ciclos, es decir verificando T2 pero no necesariamente T1. Si unbosque tiene 526 v´rtices y 520 aristas, ¿cu´ntos ´rboles contiene? e a a 13. ¿Es cierto que todo ´rbol es un grafo bipartito? a

14. Si T es un ´rbol con n v´rtices, ¿cu´l(es) de las siguientes...