Practica 0 repaso de grafos

UNIVERSIDAD CENTRAL DE VENEZUELA
FACULTAD DE CIENCIAS
ESCUELA DE COMPUTACION
Matemáticas Discretas III (Cód. 6108)
Práctica # 0

Practica 0 repaso de grafos

1) Defina y de ejemplos de cada uno delos siguientes conceptos.
(a) Multigrafos dirigidos y no dirigidos.
(b) Grafo simple.
(c) Grado de un vértice; multiplicidad de un par de vértices.
(d) Grafo completo; grafo complementario; grafobipartito.
(e) Subgrafo.
(f) Camino; camino simple; circuito.
(g) Grafo conectado; componentes conectadas; conjunto de corte.
(h) Matrices de adyacencia y de incidencia.

2) Se debe planificar un calendariopara los cinco equipos de fútbol de una liga. Si cada
equipo juega con otros dos, diseñe un calendario usando un grafo.
3) Siete ciudades a, b, c, d, e, f y g están conectadas por un sistema deautopistas como
sigue: (1) A22 va de a a c, pasando por b; (2) A23 va de c a d, luego pasa por b y continúa
hacia f; (3) A44 va de d por e hacia a; (4) A55 va de f a b, pasando por g y (5) A66 va de
g ad.
(a) Use vértices para las ciudades y aristas dirigidas para los tramos de autopista
de las unen y dibuje un grafo dirigido que modele 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
cerrarse para interrumpir el paso de b a d.
(d) ¿Es posible salir de la ciudad c y regresar a ella, visitando una sola vez las otrasciudades?
(e) ¿Cuál es la repuesta a la pregunta anterior si no es necesario regresa a c?
(f) Si se permite visitar una ciudad más de una vez y no es necesario regresar a la
ciudad donde se inició elrecorrido, ¿es posible comenzar en alguna ciudad y
viajar por todas las autopistas exactamente una vez?

4) De un ejemplo de un grafo conectado G tal que al eliminar cualquier arista de G se
obtenga ungrafo desconectado.

5) Para cada uno de los siguientes enunciados:
(a) Sea Kn un grafo completo con n vértices. Muestre Kn para 1 ≤ n ≤ 6.
(b) Sea Wn un grafo rueda con n vértices. Muestre Wn para...