grafos

UNIVERCIDAD COOPERATIVA DE COLOMBIA


TALLER DE GAFOS


ENTRAGADO POR

SERGIO DAVID ZULUAGA PEREZ




IV SEMESTRE ING DE SISTEMAS



MONTERIA CORDOBA


21 DE AGOSTO DE 2014TALLER TEORIA DE GRAFOS


1. Consulte y efectué un resumen de todos los aspectos relacionados con las propiedades de los grafos.
2. A que se denomina familia de grafos
3. Que es larepresentación de grafos.
4. A que se denomina matriz de adyacencia y matriz de incidencia. Muestre un par de ejemplos de cada una.
5. Ayúdele a Herminda Yasbleidy a describir y comprender de la mejormanera las siguientes aplicaciones de los grafos: El problema del cartero chino, El problema de los puentes de Konigsberg, El juego del dodecaedro, Las redes eléctricas de Kirchhoff, Enumeración deisómeros Cayley, El problema del mapa de cuatro colores.


De todo lo anterior, presente un resumen con ejemplo, consultando referentes bibliográficos.

Fecha de entrega: Martes 19 de Agosto de 2014.Solución taller de grafos

1) las propiedades de los grafos, que son colecciones de objetos llamados vértices (o nodos) conectados por líneas llamadas aristas (o arcos) que pueden tenerorientación (dirección asignada). Típicamente, un grafo está diseñado por una serie De puntos (los vértices) conectados por líneas (las aristas).

2) Grafos completos
Un grafo G es completo si cualquier parde vertices distintos de G son adyacentes. Llamamos Kn al grafo completo con n vertices.

Caminos
Un camino en un grafo G es una secuencia de vértices
Distintos P = v1, v2, . . . , vk , donde(vi, vi+1) ∈ E(G), i = 1, . . . , k − 1.
Una cuerda en P es una arista que une dos vértices no
Consecutivos de P. Un camino inducido es un camino sin cuerdas. Denotamos por Pk al camino inducido de kvértices.

Circuitos y ciclos
Un circuito en un grafo G es una secuencia de v´ertices
C = v1, v2, . . . , vk , no necesariamente distintos, donde
v1 = vk y (vi, vi+1) ∈ E(G), i = 1, . . . , k...