Teoría de Grafos

TEORÍA DE GRAFOS



Presentado Por:
JOHANN S. FIGUEREDO SALGADO
RICARDO ANAYA ZABALA
LUIS ÁNGEL COGOLLO JIMÉNEZ



Presentado a:
Ing. EDINSON SUÁREZ DOMÍNGUEZ




UNIVERSIDAD COOPERATIVA DE COLOMBIA
SEDE MONTERÍA
FACULTAD DE INGENIERÍA DE SISTEMAS
SEMESTRE IV
2015
1. Realizar un resumen explicando detalladamente en qué consiste el problema de los puentes Königsberg y su aplicación con la teoríade grafos.

2. Mostrar un ejemplo de los siguientes grafos:
a) Grafos Isomorfos.
b) Grafos Conexos.
c) Grafos Bipartitos.

3. Define y muestra con 3 ejemplos los conceptos de matriz de adyacencia y matriz de incidencia.

4. Ayúdele a Herminda Yasbleidy a describir y comprender de la mejor manera las siguientes aplicaciones de los grafos: El problema del cartero chino, El problema de los puentesde Königsberg, El juego del dodecaedro, las redes eléctricas de Kirchhoff, enumeración de isómeros Cayley, El problema del mapa de 4 colores.








1.
Los 7 puentes de Königsberg.
Se trata de un célebre problema resuelto matemáticamente por Leonard Euler en 1736. Pues bien, el problema consistía en encontrar una ruta por la que cruzando una vez por cada puente se pudiera regresar al punto departida. En su propuesta Euler lo hizo de una forma general para cualquier número de puentes, sean sietes o más.
El problema de los 7 puentes de Königsberg es un problema complejo. Pero con una solución muy simple de entender









En la imagen anterior podemos ver de una manera esquemática los 7 puentes y las cuatro zonas, A,B,C,D, y las dos islas en el que rio Pregel divide la ciudad.
Eulerconvirtió las cuatros zonas (A, B, C y D) en puntos (los también llamados vértices o nodos), y cada uno de los puentes (1, 2, 3, 4, 5, 6,7) en líneas (aristas o arcos). De esta manera tuvo un grafico:








Con esto Euler quería saber si existe o no un camino que comience por uno de los puntos azules, pase por todas las líneas una sola vez, y regrese al punto de partida.
La conclusión que obtuvoEuler de su teoría, es muy sencilla.
“Para cumplir con las condiciones del problema, si uno llega a un nodo (zona) a través de una arista (puente) debe salir de él por una arista distinta (puente), lo que nos lleva a que cada nodo (zona) el número de aristas que confluyen debe ser par”.
En el caso de los puentes de Königsberg este anunciado no se cumple en ninguno de los casos. Porque a losnodos (zonas) B, C y D llegan tres aristas (puentes), mientras que al nodo (zona) A llegan cinco.
Con esto Euler concluye diciendo que se trata de un problema irresoluble: no existe solución que permita hacer el recorrido pasando una sola vez por cada uno de los puentes.
Su aplicación a la teoría de grafos.
Con el problema de los sietes puentes de Königsberg era la primera vez que se hacíareferencia a una geometría basada en la estructura de los objetos y no en las medidas que suelen ser lo habitual. Euler lo llamo “geometriam situs”, hoy más conocida como Topología, dando lugar a la Teoría de Grafos o teoría de las gráficas. Un grafo se define como un conjunto de objetos llamados vértices (o nodos) y una selección de aristas (o arcos). Se suelen representar mediante una serie de puntos(los vértices) conectados por líneas (las aristas).
2.
Grafos isomorfos: Dos grafos son isomorfos si sólo varía la apariencia, es decir, cuando ambos mantienen las mismas adyacencias, estructura, caminos, ciclos, número de vértices y número de aristas.

Ejemplos:






Grafos conexos: Un grafo es conexo si tiene una única componente conexa, es decir, todos los vértices del grafo estánrelacionados. En el caso contrario sería un grafo disconexo.
Ejemplos:


Grafos bipartitos: Un grafo bipartito es un grafo no dirigido cuyos vértices se pueden separar en dos conjuntos disjuntos y teniendo que las aristas siempre unirán vértices de un conjunto con vértices de otro.
Ejemplos:



3.
Matriz de adyacencia: Todo grafo simple puede ser representado por una matriz, que llamamos...