UNIVERSIDAD NACIONAL DE UCAYALI

FACULTAD DE INGENIERIA DE SISTEMAS

TRABAJO DE INVESTIGACION

GRAFOS

CURSO : LENGUAJE DE PROGRAMACIÓN I

INTEGRANTES : PONCE MORALES, Edeher Rossetti. BLAZ ARTEAGA, Nixon. Acosta sourin,

DOCENTE : Ing. Inés Jesús Tolentino .

PUCALLPA – PERU

2007

DEDICATORIA:

A nuestros padres que con tanta dedicación, y

esfuerzo nos apoyan en el forjamiento de nuestra

carrera profesional en la facultad de ingeniería de

sistemas.

AGRADECIMIENTO:

A Dios por que su misericordia me permite

respirar día a día, y hace que pueda cumplir

nuestros sueños mas anhelados, a Jesús

por que su sacrificio, nos libro de todo dolor,

sufrimiento, fracaso y enfermedad, nos dio

libertad de soñar y vivir una nueva vida.

INDICE

OBJETIVO...................................................................................................................................................5

1) DEFINICIÓN:....................................................................................................................................6

1.1. ARISTAS DIRIGIDAS Y NO DIRIGIDAS...............................................................................................7

1.2. CICLOS Y CAMINOS HAMILTONIANOS..............................................................................................8

1.3. CARACTERIZACIÓN DE GRAFOS......................................................................................................9

1.3.1. Grafos Simples.......................................................................................................................9

1.3.2. Grafos Conexos.....................................................................................................................9

1.3.3. Grafos Completos................................................................................................................10

1.3.4. Grafos Bipartitos.................................................................................................................10

2) REPRESENTACIÓN DE UN GRAFO:........................................................................................10

2.1. MATRIZ DE ADYACENCIA................................................................................................................10

2.2. MATRIZ DE INCIDENCIA...................................................................................................................11

3) TÉCNICAS BÁSICAS DE BÚSQUEDA EN GRAFOS:.............................................................12

3.1. BÚSQUEDA EN PROFUNDIDAD (BEP)..............................................................................................12

3.2. BÚSQUEDA EN ANCHURA (BEA).....................................................................................................13

4) CAMINOS MINIMOS EN GRAFOS...........................................................................................14

4.1. ALGORITMO DE WARSHALL:.....................................................................................................14

4.2. ALGORITMO DE DIJKSTRA.............................................................................................................15

4.2.1. DESCRIPCIÓN DETALLADA........................................................................................................15

4.3. ORDENACIÓN TOPOLÓGICA:..........................................................................................................16

4.3.1 Definición.................................................................................................................................17

4.4. PUENTE DE KONIGSBERG...............................................................................................................18

5) BIBLIOGRAFIA:..............................................................................................................................22

Introducción

Hoy en día podemos ver muchas cosas que nos pueden parecer de lo mas cotidianas, carreteras, líneas telefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas mas; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos

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 y en algunos casos, su representación en algún programa informático, así como en la memoria.

En este trabajo, se explicando de manera muy sencilla los conceptos y algunas metodologías con un lenguaje no tan rebuscado 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 presentes definiciones 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 (para nuestro caso) gráfica de los datos de una situación particular, ejemplo:

   Los datos contienen, en algunos casos, relaciones entre ellos que no es necesariamente jerárquica. Por ejemplo, supongamos que unas líneas aéreas realizan vuelos entre las ciudades conectadas por líneas como se ve en la figura anterior (más adelante se presentaran grafos con estructuras de datos); la estructura de datos que refleja esta relación recibe el nombre de grafo.

Se suelen usar muchos nombres al referirnos a los elementos de una estructura de datos. Algunos de ellos son "elemento", "ítem", "asociación de ítems", "registro", "nodo" y "objeto". El nombre que se utiliza depende del tipo de estructura, el contexto en que usamos esa estructura y quien la utiliza.

En la mayoría de los textos de estructura de datos se utiliza el término "registro" al hacer referencia a archivos y "nodo" cuando se usan listas enlazadas, arboléis grafos.

OBJETIVO

El objetivo fundamental de este trabajo es facilitar el intercambio de datos, conocimientos y noticias entre todas las personas interesadas por el tema de grafos (en especial, docentes, investigadores, archiveros, bibliotecarios, documentalistas, alumnos, etc.).

GRAFOS

1) Definición:

En matemáticas y ciencias de la computación, la teoría de grafos estudia 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 tener orientació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).

 Los datos contienen, en algunos casos, relaciones entre ellos que no es necesariamente jerárquica. Por ejemplo, supongamos que unas líneas aéreas realizan vuelos entre las ciudades conectadas por líneas como se ve en la figura anterior (más adelante se presentaran grafos con estructuras de datos); la estructura de datos que refleja esta relación recibe el nombre de grafo.

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.

En la figura, V = { a, b, c, d, e, f }, y A = { ab, ac, ae, bc, bd, df, ef }.

Un grafo es una pareja G = (V, A), donde V es un conjunto de puntos, llamados vértices, y A es un conjunto de pares de vértices, llamadas aristas. Para simplificar, notaremos la arista {a, b} como ab.

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un grafo más claro. Generalmente, se considera que colocar los vértices en forma de polígono regular da grafos muy legibles.

Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o un alcantarillado.

1.1. Aristas dirigidas y no dirigidas

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus inevitables direcciones únicas. El conjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente:

Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).

En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece también una arista bidireccional, y corresponde a dos aristas orientadas.

Aquí V = {a, b, c, d, e}, y A = {(a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b)}.

Se considera la característica de "grado" (positivo o negativo) de un vértice v (y se indica como (v)), como la cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas que tocan este vértice. Por ejemplo, el grado positivo (salidas) de d es 3, mientras que el grado negativo (llegadas) de b es 1.

Según la terminología seguida en algunos problemas clásicos de Investigación Operativa (p.ej.: el Problema del flujo máximo), a un vértice del que sólo salen aristas se le denomina fuente (en el ejemplo anterior, el vértice d); tiene grado negativo 0. Por el contrario, a aquellos en los que sólo entran aristas se les denomina pozo o sumidero (en el caso anterior, el vértice e); tiene grado positivo 0.

1.2. Ciclos y caminos hamiltonianos

Ejemplo de un ciclo hamiltoniano.

Un ciclo es un camino, es decir una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (exepto el vértice del que parte y al cual llega).

Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).

Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada. Por ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.

Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempo polinómico, siendo la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos excesivamente costosos. Existen, sin embargo, métodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños.

El problema de determinar la existencia de ciclos hamiltonianos, entra en el conjunto de los NP-completos.

1.3. Caracterización de Grafos

1.3.1. Grafos Simples

Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

Un grafo que no es simple se denomina complejo.

1.3.2. Grafos Conexos

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

1.3.3. Grafos Completos

Un grafo simple es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.

El conjunto de los grafos completos es denominado usualmente ,

siendo el grafo completo de n vértices.

Un Kn, es decir, grafo completo de n vértices tiene exactamente

aristas.

La representación gráfica de los Kn como los vértices de un polígono regular da cuenta de su peculiar estructura.

1.3.4. Grafos Bipartitos

Artículo principal: Grafo bipartito

Un grafo G es bipartito si puede expresarse como

(es decir, la unión de dos grupos de vértices), bajo las siguientes condiciones:

V1 y V2 son disjuntos y no vacíos. Cada arista de A une un vértice de V1 con uno de V2. No existen aristas uniendo dos elementos de V1; análogamente

para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.

2) Representación de un grafo:

2.1. Matriz de adyacencia

Dado un grafo G = (V, E) con n vértices {v1, ..., vn} su matriz de adyacencia es la matriz de orden n*n, A(G)=(aij) donde aij es el número de aristas que unen los vértices vi y vj.

Ejemplo

La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la correspondiente fila (columna) esta compuesta sólo por ceros. Si el grafo es simple entonces la matriz de adyacencia contiene solo ceros y unos (matriz binaria) y la diagonal esta compuesta sólo por ceros.

2.2. Matriz de incidencia

Dado un grafo simple G = (V, E) con n=|V| vértices {v1, ..., vn} y m=|E| aristas {e1, ..., em}, su matriz de incidencia es la matriz de orden nxm, B(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario.

Ejemplo

La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El número de unos que aparece en cada fila es igual al grado del vértice correspondiente. Una fila compuesta sólo por ceros corresponde a un vértice aislado.

3) TÉCNICAS BÁSICAS DE BÚSQUEDA EN GRAFOS:

Para efectuar una búsqueda de los vértices de un grafo, se pueden emplear dos estrategias diferentes:

3.1. Búsqueda en profundidad (BEP).

Un recorrido en profundidad (en inglés DFS - Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo o árbol de manera ordenada, pero no uniforme. Su manera de funcionar se basa en ir expandiendo cada uno de los nodos que va localizando, de manera recursiva, recorriendo todos los nodos de un camino concreto. Cuando ya no quedan más nodos por visitar en este camino, regresa hacia atrás (backtracking), de tal manera que comienza el mismo proceso con cada uno de los hermanos del nodo ya procesado.

Esta técnica se utiliza cuando necesitamos encontrar respuesta a un problema sobre un grafo sin condiciones de optimización.

La idea en general de la búsqueda en profundidad comenzando en un nodo A es la siguiente:

Primero examinamos el nodo inicial A. Luego examinamos cada nodo N de un camino P que comience en A; a sea, procesamos un vecino de A, luego un vecino de un vecino de A y así sucesivamente, hasta llegar a un punto muerto o final del camino P, y de aquí volvemos atrás por P hasta que podamos continuar por otro camino P´ y así sucesivamente.

Este algoritmo es similar al del recorrido inorden de un árbol binario, y también a la forma en que se debe pasar a través de un laberinto. Observe que se hace uso una pila en lugar de una cola, y este es el detalle fundamental que hace la diferencia para realizar la búsqueda en profundidad.

Algoritmo para la búsqueda en profundidad:

Este algoritmo realiza la búsqueda en profundidad el grafo G comenzando en un nodo A

Si en tiempo de descubrimiento de u tenemos el arco (u,v):

i. Si v está a NO_VISITADO, entonces (u,v) DF.∈

ii. Si v está a VISITADO, entonces (u,v) es un arco hacia atrás.

iii. Si v está a TERMINADO, entonces (u,v) es un arco de cruce o arco hacia delante. Será de cruce si d[v]<d[u] y será hacia delante si d[v]>d[v]

3.2. Búsqueda en anchura (BEA).

En Ciencias de la Computación, Búsqueda en anchura (BFS o Breadth-first search en inglés) es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación para cada uno de los vecinos se exloran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.

Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución. No usa ninguna heurística.

El peso de las aristas para ejecutar BFS debe de ser de coste 1 (la unidad).

En caso de tener un coste > 1 (mayor que uno) aplicamos el algoritmo de Dijkstra .

Si las aristas tienen pesos negativos aplicaremos el algoritmo de Bellman-Ford en alguna de sus dos versiones

Algoritmo para la búsqueda en anchura:

Procedimiento Dado un vértice fuente s, Breadth-first search sistemáticamente explora

los vértices de G para “descubrir” todos los vertices alcanzables desde s.

Calcula la distancia (menor número de vertices) desde s a todos los vértices alcanzables.

Después produce un árbol BF con raíz en s y que contiene a todos los vértices alcanzables.

El camino desde s a cada vértice en este recorrido contiene el mínimo número de vértices. Es el camino más corto medido en número de vértices.

Su nombre se debe a que expande uniformemente la frontera entre lo descubierto y lo no descubierto. Llega a los nodos de distancia k, sólo tras haber llegado a todos los nodos a distancia k-1.

4) CAMINOS MINIMOS EN GRAFOS

Para lograr el propósito del recorrido mínimo dentro de un grafo G, es necesario para nuestro caso en particular (puesto que no es la única técnica existente) la utilización del algoritmo de WARSHALL para el camino mínimo, el cual se expresa de la forma siguiente:

Sea G un grafo con m nodos, u 1 , u 2 , ..., u m suponga que queremos encontrar la matriz de caminos P para el grafo G. WARSHALL dio un algoritmo para este propósito que es mucho más eficiente que calcular las potencias de la matriz de adyacencia A y aplicar la proposición:

Donde sea A la matriz de adyacencia y P = Pij la matriz de caminos de un grafo G entonces, Pij = 1 si y solo sí hay un numero positivo en la entrada ij de la matriz

Este algoritmo de WARSHALL se usa para calcular el camino mínimo y existe un algoritmo similar para calcular el camino mínimo de G cuando G tiene peso.

4.1. Algoritmo de WARSHALL:

Este algoritmo intenta resolver el problema de encontrar el camino más corto entre todos los pares de nodos o vértices de un grafo. Esto es similar a construir una tabla con todas las distancias mínimas entre pares de ciudades de un mapa, indicando la ruta a seguir para ir de la primera ciudad a la segunda.

Esto puede verse de la siguiente manera:

Sea G=(V,A) un digrafo en el cual cada arco tiene asociado un costo no negativo. El problema es hallar para cualquier par de vértices

(v,w) el camino más corto de v a w.

G=(V,A), V={1,...,n} y C[i,j] es el costo del arco que va de i a j.

El algoritmo calcula la serie de matrices

Ak[i,j] significa el costo del camino más corto que va de i a j y que no pasa por algún vértice mayor que k.

El objetivo es calcular An[i,j]

La programación de este algoritmo puede realizarse simplemente con tres ciclos anidados, de la siguiente manera:

Para k = '0' hasta n hacer{    Para i = '0' hasta n hacer    {        Para j = '0' hasta n hacer        {        A[i,j] = mínimo(A[i,j],A[i,k] + A[k,j])        }    }}

4.2. Algoritmo de Dijkstra.

También llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices

en un grafo dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo se atiene a la estrategia conocida como esquema de algoritmo voraz. El algoritmo no funciona en grafos con aristas de costo negativo.

4.2.1. Descripción detallada

Sea G=(V,A) un grafo dirigido y etiquetado. Sean los vértices a V y ∈ z V; ∈ a es el vértice de origen y z el vértice de

destino. Sea un conjunto C V, que contiene los vértices de V cuyo camino más ⊂

corto desde a todavía no se conoce. Sea un vector D, con tantas dimensiones como elementos tiene V, y que

“guarda” las distancias entre a y cada uno de los vértices de V. Sea, finalmente, otro vector, P, con las mismas dimensiones que D, y que

conserva la información sobre qué vértice precede a cada uno de los vértices en el camino.

El algoritmo para determinar el camino de longitud mínima entre los vértices a y z es:

1. C ← V 2. Para todo vértice i C, ∈ i ≠ a, se establece Di ← ∞ ; Da ← 0 3. Para todo vértice i C se establece P∈ i = a 4. Se obtiene el vértice s C tal que no existe otro vértice ∈ w C tal que D∈ w

< Ds o Si s = z entonces se ha terminado el algoritmo.

5. Se elimina de C el vértice s: C ← C−{s} 6. Para cada arista e A de longitud ∈ l, que une el vértice s con algún otro

vértice t C, ∈o Si l+Ds < Dt, entonces:

1. Se establece Dt ← l+Ds 2. Se establece Pt ← s

7. Se regresa al paso 4

Al terminar este algoritmo, en Dz estará guardada la distancia mínima entre a y z. Por otro lado, mediante el vector P se puede obtener el camino mínimo: en Pz estará y, el vértice que precede a z en el camino mínimo; en Py estará el que precede a y, y así sucesivamente, hasta llegar a a.

Algoritmo

DIJKSTRA (Grafo G, nodo_fuente s) // inicializamos todos los nodos del grafo. La distancia de cada nodo es infinita // y los padres son NULL

for u ∈ V[G] do distancia[u] = INFINITO padre[u] = NULL distancia[s] = 0 //encolamos todos los nodos del grafo Encolar (cola, V[G]) mientras cola != 0 do // OJO: Se extrae el nodo que tiene distancia mínima y se conserva la condición // de Cola de prioridad u = extraer_minimo(cola) for v adyacencia[∈ u] do if distancia[v] > distancia[u] + peso(u,v) do distancia[v] = distancia[u] + peso(u,v) padre[v] = u

 4.3. Ordenación Topológica:

Hasta recientemente todos los trabajos sobre Topología (Digital principalmente) se basaban en un enfoque de Teoría de GRAFOS. Este enfoque presenta, sin embargo, el problema de determinar la relación de adyacencia más razonable en Zn. Actualmente existen enfoques alternativos basados en nociones de Topología General. En este caso haremos una introducción a algunos de estos enfoques.

4.3.1 Definición. Una ordenación topológica de un grafo acíclico G dirigido es una ordenación lineal de todos los nodos de G que conserva la unión entre vértices del grafo G original. La condición que el grafo no contenga ciclos es importante, ya que no se puede obtener ordenación topológica de grafos que contengan ciclos.Usualmente, para clarificar el concepto se suelen identificar los nodos con tareas a realizar en la que hay una precedencia a la hora de ejecutar dichas tareas. La ordenación topológica por tanto es una lista en orden lineal en que deben realizarse las tareas.Para poder encontrar la ordenación topológica del grafo G deberemos aplicar una modificación del algoritmo de búsqueda en profundidad (DFS).

Pseudocódigo La ordenación topológica no es única. Depende en qué orden

recorras los nodos del grafo en el bucle for de la función ORDENACIÓN_TOPOLÓGICA.

La nomenclatura adicional utilizada es: lista = Estructura de datos lista enlazada

ORDENACIÓN_TOPOLÓGICA(grafo G) for each vertice u ∈ V[G]do estado[u] = NO_VISITADO padre[u] = NULL tiempo =0 for each vertice u ∈ V[G]do if estado[u] = NO_VISITADO then TOPOLÓGICO-Visitar(u)

TOPOLÓGICO-Visitar(nodo u) estado[u]=VISITADO tiempo = tiempo+1 distancia[u] = tiempo for each v ∈ Adyacencia[u] do if estado[v]=NO_VISITADO then padre[v]=u TOPOLÓGICO-Visitar(v) estado[u] = TERMINADO tiempo = tiempo+1 finalización[u] = tiempo insertar (lista, u)

Al final de la ejecución del algoritmo se devuelve la lista enlazada de nodos, que corresponde con la ordenación topológica del grafo .

Ejemplo gráfico En rojo se muestran los siguientes tiempos: distancia[u] /

finalización[u]

1. Ejecutamos el algoritmo ORDENACIÓN_TOPOLÓGICA (grafo G) sobre el siguiente grafo.

2. 2. El algoritmo nos devuelve una lista enlazada con los nodos del grafo en orden decreciente en tiempo de finalización.

Grafo ordenado topológicamente. En él se pueden ver claramente las precedencias de las tareas:

Ponerse la camisa antes que el cinturón y el jersey Ponerse el pantalón antes que los zapatos y el cinturón Ponerse los calcetines antes que los zapatos

 

4.4. Puente De Konigsberg.

El problema es simplemente encontrar un trayecto, alrededor de una serie de puentes, que cruce solamente una vez cada uno de ellos. El mapa de abajo muestra la disposición de siete puentes y dos islas en la ciudad de Königsberg.

En 1736, el matemático suizo radicado en San Petersburgo Leonhard Euler publicó "Solutio Problematis ad Geometriam Situs Pertinentis", un artículo en el que resolvía el problema en el caso general. Este trabajo es considerado como el nacimiento de la Teoría de Graficos, utilizada hoy en día en una multiplicidad de aplicaciones, y también uno de las primeras apariciones de una «nueva geometría» en la que importan sólo las propiedades estructurales de un objeto y no sus medidas. A esto se refieren las palabras «geometriam situs» en el título de Euler, palabras que hoy se traduce como topología. La topología es una de las ramas más nuevas de las matemáticas. Una manera simple de describirla es aquella en la cual se señala que su orientación se centra en el estudio de ciertas propiedades de las figuras geométricas. El término topología fue usado por primera vez en 1930 por el matemático Solomon Lefschetz. Generalmente ha sido clasificada dentro de la geometría, se la llama a menudo geometría de la goma elástica, de la lámina elástica o del espacio elástico, pues se preocupa de aquellas propiedades de las figuras geométricas del espacio que no varían cuando el espacio se dobla, da la vuelta, estira o deforma de alguna manera. Las dos únicas excepciones son que el espacio no se puede romper creando una discontinuidad y que dos puntos distintos no se pueden hacer coincidir. La geometría se ocupa de propiedades como la posición o distancia absoluta y de las rectas paralelas, mientras que la topología sólo se ocupa de propiedades como la posición relativa y la forma general.

El estudio de los fundamentos de la topología no es a menudo parte de los programas de estudios de las matemáticas en las escuelas de enseñanza secundaria y, por ello, para muchos suena como el conocimiento de algo intimidante y extraño. Sin embargo, hay algunas ideas de las bases de la topología fácilmente captables e interesantes, aplicables a muchas situaciones, incluidas algunas de diversión. Una de estas áreas es la topología de redes de trayectorias de circulación, que fue desarrollada por Euler en 1735, y que es el tema central de este trabajo.

La idea de Euler fue considerar los cuatro lugares terrestres, que se deseaban comunicar (hay 4 de ellos), como puntos de destino y, a los famosos puentes, como trayectorias entre esos puntos. En consecuencia, el mapa de Königsberg –en esencia matemática– puede ser entonces reducido al siguiente diagrama, que es un ejemplo de lo que se suele llamar un gráfico:

Un gráfico, es una figura cuyas líneas o curvas (llamadas márgenes), conectan puntos o vértices. En consecuencia, la trayectoria de los puentes de Königsberg puede ser reformulada como un gráfico, en el cual los márgenes son remontados una sola vez.

Para cada uno de los vértices del gráfico, el orden de los números de cada uno de ellos corresponde al margen que le concierne. La figura de abajo muestra el gráfico del problema de los puente de Königsberg, con el orden de los números de los vértices.

Euler trató de resolver el problema de la trayectoria de los puentes de Königsberg, graficando la sustitución de áreas terrestres por vértices y los puentes por arcos (márgenes). En la figura de abajo, los puntos rojos representan las áreas terrestres de Königsberg y las curvas negras los puentes. Este problema, por supuesto que puede ser resuelto mediante un estudio exhaustivo de todas las posibles trayectorias. Pero las matemáticas se interesan en generalizar el problema y buscar una solución sencilla y válida para todos los posibles mapas de ciudades, e incluso objetos más generales.

En función de la ubicación de cada uno de los vértices y de los márgenes que los conectan, Euler no pudo entregar una solución al problema de la trayectoria de los puentes de Königsberg. Solamente podría haber una solución si los vértices pudiesen ser conectados con márgenes pares, ya que ello implicaría entrar y salir a través de los mismos por los cuales se llega. Alternativamente, dos vértices pueden estar conectadas por un número impar de márgenes y, éstos, serían el comienzo y el final de la trayectoria.

La primera observación que salta del párrafo anterior, es que el problema se puede reformular como sigue. El gráfico de la derecha tiene cuatro vértices y siete márgenes; ahora bien, ¿es posible recorrerlo entero sin pasar dos veces por el mismo margen? En el gráfico, los cuatro vértices (los puntos rojos del dibujo) representan las cuatro partes en que los ríos separan a la ciudad, y los siete márgenes (las líneas que unen los vértices) representan los puentes. En términos más familiares para los aficionados a los pasatiempos: ¿es posible realizar el dibujo del gráfico sin levantar el lápiz del papel y sin pasar dos veces por el mismo margen? (Se permite pasar dos veces por el mismo vértice).

La respuesta de Euler es considerablemente simple. Supongamos que, efectivamente, es posible realizar el dibujo sin levantar el lápiz del papel. Al realizar el dibujo, en cada vértice intermedio que atravesemos entraremos por un margen y saldremos por otro. En particular, el número de márgenes que convergen con cada vértice del gráfico, exceptuando quizás los vértices inicial y final del dibujo, ha de ser par. Si llamamos «valencia» de cada vértice al número de márgenes que convergen en él, lo dicho anteriormente significa que para que el problema tenga solución es necesario que en el gráfico haya como mucho dos

vértices de valencia impar. En el caso del gráfico de Königsberg los cuatro vértices tienen valencia impar, así que el problema no tiene solución. Demostrar que esa condición precedente es no sólo necesaria, sino también suficiente, no es difícil. Si a ello, agregamos el hecho de que en todo gráfico el número de márgenes con valencia impar es par (porque al sumar las valencias de todos los vértices estaremos contando dos veces cada margen) se llega a la conclusión de los gráficos que se pueden dibujar sin levantar el lápiz del papel y sin pasar dos veces por el mismo margen:

Si un gráfico no tiene vértices de valencia impar, entonces se puede dibujar. Además, se puede dibujar empezando desde cualquier vértice y el dibujo será «cerrado» en el sentido de que termina en el mismo vértice en el que se empezó. A estos gráficos se les llama eulerianos.

Si un gráfico tiene exactamente dos vértices de valencia impar, entonces se puede dibujar, pero siempre será necesario comenzar en uno de ellos y terminar en el otro.

Si un gráfico tiene cuatro o más vértices de valencia impar, entonces hasta ahí se llega, ya que no se puede dibujar.

 

5)  BIBLIOGRAFIA: http://es.wikipedia.org/wiki/

Algoritmo_de_Dijkstra#Pseudoc.C3.B3digo_del_algoritmo

http://www.astrocosmo.cl/anexos/anexos.htm#indice

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos

http://ls.fi.upm.es/ed2/0001/problemas/node11.html

http://docencia.udea.edu.co/regionalizacion/teoriaderedes/ representacionordenadoru1.html