• Author / Uploaded
• CJ Cotrina

• Categories
• Teoría de grafos
• Matemáticas discretas
• Relaciones matematicas
• Combinatoria
• Conceptos matemáticos

Citation preview

..

SEMINARIO DE ´ TEORIA DE GRAFOS Matem´atica Discreta

1. Dados los siguientes grafos:

a)

b)

Determinar si ”v” y ”x” son puntos de corte y cu´antas componentes conexas generan dichos v´ertices en cada grafo. 2. Indicar los puntos de corte y puentes de los siguientes grafos:

3. Hallar la matriz de adyacencia y de incidencia de los siguientes grafos:

a)

b)

c)

4. De los grafos a) y b) del ejercicios anterior determinar : a) El n´ umero de caminos de longitud 2, entre el v´ertice 5 y el v´ertice 4 para cada grafo. b) El n´ umero de caminos de longitud 3, entre el v´ertice 1 y el v´ertice 2 para cada grafo. 5. Construir un grafo de orden 5 cuyos v´ertices tengan grados 1, 2, 2, 3, 4. ¿Cu´antas aristas tiene el grafo? 6. Una compa˜ n´ıa de autopistas ha contratado a una empresa de seguridad para que patrulle la red de autopistas cuyo mapa esta esquematizado a continuaci´on:

La empresa de seguridad quiere realizar el servicio con un solo veh´ıculo, y quiere determinar la existencia de un recorrido de la red, de modo que se vigilen los tramos de autopista una sola vez. ¿Existe tal recorrido?. ¿Cu´al es?. ¿Es u ´nica la soluci´on ? 7. En el mapa de carreteras de una regi´on aparecen 25 tramos de carretera. Sabiendo que los cruces se producen siempre en una poblaci´on y que de cada poblaci´on parten al menos cuatro caminos, ¿cu´antas poblaciones aparecen en el mapa? 8. ¿Cu´ales de estos grafos son biconexos?

9. ¿Se puede construir un grafo regular con 10 aristas en el que cada v´ertice tenga grado 4?, en caso de ser posible representar dicho grafo. 10. Disponemos de 6 ordenadores y 9 cables de conexi´on. Queremos que cada ordenador se conecte con otros 3. ¿Existe alguna forma de conectarlos? ¿Es u ´nica?

11. Dado el siguiente grafo:

a) b) c) d) e) f)

Describir un camino simple entre los v´ertices 1 y 6. Describir un ciclo en el grafo que contenga a los v´ertices 1 y 4. ¿Es conexo? Hallar un subgrafo generador y otro inducido por { 2; 3; 4; 5 } Hallar el complemento del grafo. Indicar si el grafo es euleriano o hamiltoniano, si fuera euleriano describir el recorrido para trazar dicho grafo.

12. Verificar si los grafos G1 y G2 son bipartidos.

13. Verificar si G ≃ H, indicando la funci´on biyectiva (isomorfismo) entre los dos grafos.

14. Verificar que las matrices A y B son matrices de adyacencia de dos grafos isomorfos. 

0  1 A=  0 1

1 0 1 1

0 1 0 1

 1 1   1  0



y

0  0 B=  1 1

0 0 1 1

1 1 0 1

 1 1   1  0

15. Dado el grafo G, encontrar su matriz de adyacencia de A. A partir de ella, deducir: a) Los caminos posibles de longitud 2 desde c a b. b) Los caminos posibles de longitud 3 desde c a d. c) Los caminos posibles de longitud 4 desde a a d.

16. Probar si los siguientes grafos son isomorfos: a) G1 y G2 . b) G2 y G3 .

17. Determinar cu´ales de los siguientes pares de grafos son isomorfos:

18. Dar un ejemplo de grafo, para cada item, con un m´aximo de 6 v´ertices. a) Un grafo euleriano pero no hamiltoniano. b) Un grafo hamiltoniano pero no euleriano. c) Un grafo que tenga un camino euleriano abierto pero que no tenga un camino hamiltoniano abierto.

M AF S