Teoria De Grafos

Introducción:
En este trabajo se tratará de explicar lo que son los grafos, sus tipos, y algunas derivaciones de ellos, así como su representación gráfica. Explicando de manera muy sencilla los conceptos y algunas definiciones para su mayor entendimiento.
Desafortunadamente no existe una terminología estandarizada en la teoría de los grafos, por lo tanto es oportuno aclarar que las presentesdefiniciones pueden variar ligeramente entre diferentes publicaciones de estructura de datos y de teoría de grafos, pero en general se puede decir que un grafo como indica su nombre lo indica es la representación gráfica de los datos de una situación particular.
También un grafo es una terna G = (V, A, j), en donde V y A son conjuntos finitos, y j es una aplicación que hace corresponder a cadaelemento de A un par de elementos de V. Los elementos de V y de A se llaman, respectivamente, vértices y aristas de G, y j asocia entonces a cada arista con sus dos vértices.
Esta definición da lugar a una representación gráfica, en donde cada vértice es un punto del plano, y cada arista es una línea que une a sus dos vértices.
Aristas son las líneas con las que se unen las aristas de un grafo y conla que se construyen también caminos ahí diferentes tipos de aristas: Aristas Adyacentes, Aristas Paralelas,, Aristas Cíclicas y Cruce.
Vértices: son los puntos o nodos con los que esta conformado un grafo.
Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos.
A continuación se dará a conocer detalladamente de lo que nos estamos refiriendo anteriormente sobre el trabajo.Teoría de grafos:
Es de general aceptación que la teoría de grafos, tal como la conocemos hoy en día nació en lo que pudiere ser un problema trivial: el problema de los siete puentes de Königsberg. ( siglo XVIII).
Siete puentes cruzaban el rio Pregel en el pequeño pueblo universitario de Alemania llamado kônigsberg. Cuatro de los sietes puentes iban de una isla kneipohof a tierrafirme, otro puente unía a kneiphof con otra isla y los últimos dos puentes iban de esta ultima isla a tierra firme.

|[pic] |El problema de los puentes de Königsberg.  Esta |
| |ciudad esta recorrida por el río Pregel que crea |
||dos islas. ¿Se puede recorrer toda la ciudad |
| |pasando una sola vez por todos y cada uno de los |
| |7 puentes que unen la parte insular de la ciudad |
| |con el resto?|
| |Fuente: gráfico por el autor. |


El problema fe representado por Euler quien lo simplifico reemplazando por puntos vértices tanto la tierra firme como las islas y por líneas lados los puentes:
| |
||
| |
|La solución de Euler. El famoso matemático abstrajo los |
|detalles de la forma de la ciudad y sus puentes para |
|quedarse con la conectividad, dando lugar a una de los |
|primeros grafos. El orden de todos los vértices es |
|impar, lo que implica que es imposible recorrerlos ||pasando una sola vez por cada uno. |
| |
| |


[pic]
Llamó orden de cada vértice al numero de arcos que se reunían en el y se percató que el orden de cada vértice visitado en un recorrido sin saltos ha de ser par sale un enlace y entra...