Arboles Y Grafos Matematicas Discretas

Unidad 6.- Teoría de Grafos
Teoría de Grafos

Elementos y características de los Grafos

Representación de Grafos

Algoritmo de recorrido y búsqueda

Arboles

Redes

Cibergrafia y Bibliografia

Teoría de Grafos
La teoría de grafos es una teoría que sorprende por su sencillez inicial  por su versatilidad, así como por su fuerza para resolver problemas de lo más variado. Esprecisamente su sencillez lo que hace que puedan utilizarse para crear modelos en temas tan dispares, como las telecomunicaciones, Internet, la teoría de la información, la química, la física, el estudio de probabilidades, en temas de planificación, en el estudio de las redes sociales, en juegos recreativos, en redes neuronales, en programación,…
Se suele decir que la teoría de grafos se inició con laresolución de Euler del problema de los puentes de Königsberg. Según cuenta la historia, en la ciudad de Königsberg (actualmente Kaliningrado) hacia 1700, sus habitantes se divertían con un curioso juego que consistía en pasar una vez, y sólo una vez, por cada uno de los siete puentes que cruzaban su río, volviendo al punto de partida.
Para entender este problema es importante saber cómo estabandistribuidos los puentes en el río. Tenemos el río, con sus dos orillas, una isla en medio que está unida a cada una de las orillas por dos puentes hacia cada orilla, después de la isla el río se separa en dos partes, y hay un puente en cada rama del río, y otro puente entre la isla y el terreno entre los dos brazos del río (en total siete puentes).
Podéis intentar resolver vosotros mismos elproblema de los puentes de Königsberg, y después de un tiempo, os pasará como a los habitantes de esta ciudad, que no fueron capaces de encontrar el recorrido que resolviera el problema. Entonces, se nos plantean dos cuestiones: a) ¿tiene solución el problema de los puentes de Königsberg? b) Y si no la tiene ¿cómo demostrarlo?
Teoría de grafos |
En matemáticas lo que se suele hacer es simplificarlos problemas que se están estudiando, eliminando lo que no es importante, para poder crear después un “modelo” que describa nuestro problema y sobre el que podamos trabajar matemáticamente para resolverlo. En el problema de los puentes de Königsberg se puede intentar simplificar el problema, como de hecho lo hizo el gran matemático suizo Leonhard Euler (1707-1783).
Para ello transformó loselementos que aparecían en el problema (puentes, río y zonas de tierra) en un grafo de puntos y aristas que recogiera lo importante del problema, eliminando lo superfluo, para ello cada zona de tierra aislada sería un punto, un vértice del grafo, y los puentes son las aristas que unen esos puntos, obteniéndose así el grafo del problema (nuestro modelo matemático).
Elementos y Características de losGrafos.

Un grafo consta de dos cosas:
^ Un conjunto N cuyos elementos se llaman nodos, puntos o vértices.
^ Un conjunto S de parejas no ordenadas de nodos diferentes, llamadas
segmentos, aristas o arcos.

Denotaremos un grafo por G =(N, S) cuando queremos destacar las dos partes de G. Los nodos u y v se llaman adyacentes si hay un segmento {u, v}
Representaremos de unamanera natural los grafos por diagramas en el plano. O sea, cada nodo v de N se representa por un punto (o pequeño círculo) y cada segmento s = {v1, v2} se representa por una curva que conecta sus terminales v1 y v2.

EJEMPLO.

La figura 1.1 representa el G con cuatro vértices, A, B, C y D, y cinco segmentos s1 = {A, B}, s2 = {B, C}, s3 = {C, D}, s4 = {A, C}, s5 = {B, D}. Usualmentedenotamos un grafo dibujando su diagrama en lugar de hacer una lista explicita de sus nodos y segmentos.

La figura 1.2 no es un grafo sino un multigrafo. La razón es que s4 y s5 son segmentos múltiples, o sea segmentos que conectan las mismas terminales, y s6 es un lazo, o sea, un segmento cuyas terminales son el mismo nodo. La definición de grafo no permite ni segmentos...