Tarea de anillos

MATEMATICAS DISCRETAS II
TAREA II
11 / OCTUBRE / 10

1) Di qué es una gráfica dirigida. Revisa el capítulo 11 del libro de Grimaldi, la sección11.2 y responde 2 de abajo.

2) Siete ciudades a, b, c, d, e, f y g están conectadas por un sistema de autopistas como sigue:
• I-22 va de a a c.• I-33 va de c a d y entonces pasa por b y continúa hacia f.
• I-44 va de d por e hacia a.
• I-55 va de f a b, pasando por g.
• I-66 vade g a d.

a) Use los vértices para las ciudades y las aristas dirigidas para los tramos de autopista que las unen y dibuje una gráfica dirigida quemodele esta situación.

b) Enumere los caminos simples de g a a.

c) ¿Cuál es el menor número de segmentos de autopista que tendrían que cerrarsepara interrumpir el paso de b a d?

d) ¿Es posible salir de la ciudad c y regresar a ella visitando una sola vez las otras ciudades?

e) ¿Esposible comenzar en alguna ciudad y viajar por todas las autopistas exactamente una vez? ( Se permite visitar una ciudad mas de una vez y no es necesarioregresar a la ciudad donde se inició el recorrido)

3) Investiga en qué consiste el problema de Los siete puentes de Konigsberg.

4) Di qué es uncircuito euleriano y da un ejemplo.

5) ¿Para qué sirven las matrices? Di qué es una matriz de adyacencia y de incidencia. Da un ejemplo para cada una.6) ¿Qué es una gráfica plana?

7) ¿Qué dice el teorema de Kuratowski?

8) ¿Qué es un ciclo y camino hamiltoniano? Da un ejemplo de cada uno.