ALGORITMOS DE RECORRIDO Y BÚSQUEDA

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados.

1.     El Camino Más Corto:

El algoritmo de Dijkstra resuelve el problema de encontrar los caminos más cortos a partir de un origen, en grafos pesados que no tengan pesos negativos. El algoritmo de  Dijkstra es un algoritmo voraz que opera a partir de un conjunto S de nodos cuya distancia más corta desde el origen ya es conocida. En principio, S contiene solo el nodo origen. En cada paso, se agrega algún nodo v a S, cuya distancia desde el origen es la más corta posible. Bajo la hipótesis de que los pesos son no negativos, siempre es posible encontrar un camino más corto entre el origen y v que pasas sólo a través de los nodos de S, al que llamaremos “especial” más corto a cada nodo. Una vez que S incluye todos los nodos, todos los caminos son “especiales”, así que D contendrá la distancia más corta del origen a cada vértice. Se puede utilizar un arreglo P, para ir almacenamiento los caminos más cortos.

2.     A Lo Ancho:

En este algoritmo también se utiliza la estrategia de marcas los nodos como “visitados” para detectar la culminación del recorrido, pero los nodos se recorren de una manera ligeramente distinta. Este algoritmo puede crear menos ambientes recursivos que le anterior porque visita más nodos en un mismo ambiente, pero esto depende de cómo este construido el grafo. El algoritmo se conoce como el algoritmo de BFS (Breadth-First Search).

3.     En Profundidad:

Para efectuar un recorrido en profundidad de un grafo, se selecciona cualquier nodo como punto de partida (por lo general el primer nodo del grafo) y se marcan todos los nodos del grafo como “no visitados”. El nodo inicial se marca como “visitado” y si hay un nodo adyacente a este que no haya sido “visitado”, se toma este nodo como nuevo punto de partida del recorrido. El recorrido culmina cuando todos los nodos hayan sido visitados.

REFERENCIA:

Toledo, I. (11 de Octubre de 2012). Teoria de Grafos. Obtenido de SlideShare.net: http://es.slideshare.net/isaiastoledo7/teora-de-grafos-14694334

EJEMPLO DE UN GRAFO CON MATRIZ DE ADAYACENCIA

V = {v1, v2, v3, v4, v5}

E = {(v1, v1, (v1, v3), (v2, v3), (v2, v4), (v2, v5), (v3, v4), (v4, v5), (v5, v1)}

Matriz De Adyacencia:

n = cantidad de vértices

matriz = n*n               matriz = 5*5 = 25

A = {1 1 0 0 1}

       {1 0 1 1 1}

       {0 1 0 1 0}

       {0 1 1 0 1}

       {1 1 0 1 0}

CIRCUITO DE HAMILTON

En 1856, el matemático William Hamilton presentó al mundo un puzzle (juego de mesa). El juego estaba en un dodecaedro regular cuyos 20 vértices se marcaban cada uno con el nombre de una ciudad importante en aquella época. El juego consistía en salir de una determinada ciudad y encontrar una ruta que permitiera para por todas las demás ciudades una sola vez y regresar al punto de partida. El dodecaedro era tan incómodo de manipular que Hamilton desarrollo una versión del juego en que lo reemplazaba por un grafo con 20 vértices unidos mediante 30 aristas. El grafo resultante se conoce como grafo del dodecaedro.

W. R. Hamilton (1805 – 18659) inventó (y patentó) un juego en el que se trataba de hacer un recorrido por 20 ciudades (vértices) del mundo sin pasar por ninguna más de una vez. Las ciudades estaban unidas por 30 aristas, formando el grafo de un icosaedro.

Se denomina camino Hamiltoniano en un grafo con aristas no orientados G = (V, A) a cualquier camino simple que contenga a todos los vértices de G pasando una sola vez por cada uno de ellos, pero permitiendo que el vértice final. Si el camino Hamiltaniano es cerrado, se le denomina circuito Hamiltoniano.

Se dice que un grafo es de Hamilton si existe un ciclo que recorre todos sus vértices y se lo denomina ciclo Hamiltoniano.

A pesar de la preocupación y el estudio de las matemáticos, no existe hoy en día u teorema que permita determinar si un grafo es Hamiltoniano o no. El método de ensayo y error es la única forma posible de encontrar una respuesta al problema.

CICLO HAMILTON: Es un ciclo simple que contiene todos los vértices de G.

Un ciclo Hamiltoniano es una trayectoria que empieza y termina  en el mismo.

REFERENCIAS:

Lopez, A. (19 de Mayo de 2016). Circuito de Hamilton. Obtenido de SlideShare.net: http://es.slideshare.net/AntonellaLopez7/circuito-de-hamilton

CAMINO Y CIRCUITO DE EULER

CAMINO DE EULER

Es aquel camino que recorre todos los vértices pasando por todas las ramas solamente una vez.

Una característica importante de los grafos que tienen camino de Euler es que siempre comienza y termina en vértices que tienen valencia impar. Por otro lado un grafo tiene más de dos vértices con valencia impar, entonces no puede tener un camino de Euler ya que es requisito que tenga dos y solamente dos vértices de valencia par.

CIRCUITO DE EULER

Es aquel ciclo que recorre todos los vértices pasando por todos los lados solamente una vez.

Un grafo tiene un circuito de Euler si y sólo si es conexo y todos sus vértices tienen la misma valencia par.

El siguiente algoritmo de Fleury permite determinar un circuito de Euler:

1.- Verificar que el grafo sea conexo y que todos los vértices tengan valencia par. Si no cumple con estas condiciones entonces el grafo no tiene circuito de Euler y finalizar.

2.- Si cumple con la condición anterior, seleccionar un vértice arbitrario para iniciar el recorrido.

3.- Escoger una arista a partir del vértice actual. Esa arista seleccionada no debe ser “lado puente”, a menos que no exista otra alternativa.

Lado puente es aquella arista que si se elimina, los grafos pierden la propiedad de ser conexos.

4.- Desconectar los vértices del grafo ya están desconectados ya se tiene el circuito de Euler y finalizar. De otra manera continuar con el paso 3.

REFERENCIAS:

Murillo, J. A. (s.f.). Matemáticas para la computación. México: Alfaomega Grupo Editor, S. A. de C. V., México.

EJERCICIOS

EJERCICIO 1:

Encontrar los posibles caminos empezando de la ‘a’ y terminando en la ‘e’ en donde la longitud de todo el trayecto sea el menor.

RESPUESTA:

         Trayectoria:                     Longitud:

1.-     a, b, c, d, e                            21

2.-     a, b, d, c, e                            28

3.-     a, c, b, d, e                            24

4.-     a, c, d, b, e                            26

5.-     a, d, b, c, e                            27

6.-     a, d, c, b, e                            22

EJERCICIO 2:

En un torneo, el Nieve venció a los Faisanes una vez, el Rascacielos venció al Tuna, el Nieve venció al Rascacielos dos veces, los Faisanes vencieron al Rascacielos una vez. En los ejercicios 1 al 4, use gráfica para modelar el torneo. Los equipos son los vértices. Describa el tipo de gráfica usada (no dirigida, dirigida o simple).

a) Hay una arista entre los equipos si los equipos jugaron.

b) Hay una arista entre los equipos para cada juego jugado.

c) Hay una arista del equipo ti al tj si ti venció al tj al menos una vez.

d) Hay una arista del equipo ti al equipo tj por cada victoria de ti sobre tj

RESPUESTA:

a)  

      Es un gráfica simple

      b)

      Es una gráfica no dirigida

      c)

      Es una gráfica dirigida

      d)

      Es un gráfica dirigida

EJERCICIO 3:

Determinar un circuito de Euler en el siguiente grafo.

 Paso 1:

a, c

Paso 2:

a, c, b

Paso 3:

a, c, b, e

Paso 4:

a, c, b, e, c

Paso 5:

a, c, b, e, c, f

Paso 6:

a, c, b, e, c, f, e

Paso 7:

a, c, b, e, c, f, e, d

Paso 8:

a, c, b, e, c, f, e, d, b

Paso 9:

a, c, b, e, c, f, e, d, b, a

EJERCICIO 4:

Determinar, si es posible, un circuito de Hamilton en el siguiente grafo.

RESPUESTA:

EJERCICIO 5:

Determinar el siguiente grafo.

a) ¿Tiene un camino de Euler?

b) ¿Tiene un circuito de Euler?

c) ¿Tiene un circuito de Hamilton?

d) Obtener:

     - El conjunto de vértices (V)

     - Conjunto de aristas (A)

     - Conjunto de lazos (L)

     - Conjunto de lazos paralelos (P)

e) Obtener la matriz de adyacencia

RESPUESTA:

a) No tiene camino de Euler porque un vértice tiene 3 ramas impares, y por lo tanto, no puede regresar por una arista para ir pasando por cada una.

b) No tiene circuito de Euler porque hay que pasar varias veces por un vértice, y el circuito de Euler dice que el ciclo debe recorrer todos los vértices pasando por todos los lados solamente una vez.

c) No tiene circuito de Hamilton porque pasaría por un vértice varias veces.

d)
     - El conjunto de vértices (V)

          V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

     

     - Conjunto de aristas (A)

         A = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, ñ, o, p, q}

     - Conjunto de lazos (L)

         L = {f, p}

     - Conjunto de lazos paralelos (P)

         P = {q, e}

e) Obtener la matriz de adyacencia:

n = 10

matriz = 10*10 = 100

A = {0 1 1 0 1 1 0 0 0 0}

       {1 0 0 0 0 1 0 0 0 0}

       {1 0 1 0 0 0 0 1 0 0}

       {0 0 0 0 0 0 0 1 0 1}

       {1 0 0 0 0 1 0 1 0 0}

       {1 1 0 0 1 0 1 0 0 0}

       {0 0 0 0 0 1 0 0 1 1}

       {0 0 1 1 1 0 0 0 1 0}

       {0 0 0 0 0 0 1 1 0 1}

       {0 0 0 1 0 0 1 0 1 1}

CARACTERISTICAS DE LOS GRAFOS

GRAFO:

Un grafo (G) es un diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L).

VÉRTICES:

Se indican por medio de un pequeño círculo y se les asigna un número o letra.

LADOS (RAMAS O ARISTAS):

Son las líneas que unen un vértice con otro y se les asigna una letra, número o combinación de ambos.

LADOS PARALELOS:

Son aquellas aristas que tienen relación con un mismo par de vértices.

LAZO:

Es aquella arista que sale de un vértice y regresa al mismo vértice.

GRAFO CONEXO:

Es aquel en el que para cualquier par de vértices w, x, distintos entre sí, existe un trayecto para ir de w a x.

En el grafo conexo (conectado) siempre existe un camino para ir de un vértice a otro, sin embargo en el grafo no conexo existen vértices que no están conectados y, por lo tanto, no se puede acceder a ellos.

VALENCIA DE UN VÉRTICE

Es el número de lados que salen o entran a un vértice.

MATRIZ DE ADYACENCIA:

Es aquella que muestra de la forma más rustica cómo está compuesto un grafo, esto es que dónde se coloque un uno se representa como una arista que una los dos nodos y con cero donde no hay unión.

NOTA: Se puede obtener el Grafo a partir de la matriz de Adyacencia.

REFERENCIAS:

Murillo, J. A. (s.f.). Matemáticas para la computación. México: Alfaomega Grupo Editor, S. A. de C. V., México.

Chirinos, N. (14 de Noviembre de 2010). Teoria de Grafos. Conceptos básicos. Obtenido de SlideShare.net: http://es.slideshare.net/naborchirinos/conceptos-teoria-de-grafos-5778778

TIPOS DE GRAFOS

GRAFICA NO DIRIGIDA:

Son aquellos en los cuales los lados no están orientados (no son flechas). Cada lado se representa entre paréntesis, separando sus vértices por comas, y teniendo en cuenta (vi, vj) = (vj, vi)

La gráfica (o grafos no dirigidos) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tal que cada arista e € pertenece se asocia con un par no ordenado de vértices. Si existe una arista única e asociada con los vértices v y w se escribe e = (v, w) o e = (w, v). En este contexto (v, w) en una gráfica no dirigida y no es un par ordenado.

GRAFICA DIRIGIDA:

Son aquellos en los cuales los lados están orientados (flechas). Cada lado se representa entre ángulos, separando sus vértices por comas y teniendo en cuenta <vi, vj> = <vj, vi>. En grafos dirigidos, para cada lado <a, b>, a, el cual es el vértice origen, se conoce como la cola del lado y b, el cual es el vértice destino, se conoce como cabeza del lado.

Un gráfica dirigida (o dígráfica)  G consisten en un conjunto V vértices (o nodos) y u conjunto de vértices. Si hay una arista (o arcos) tales que cada arista e € está asociada con un par ordenado de vértices. Si hay una arista única e asociada con el par ordenado (v, w) de vértces, se escribe e = (v, w) que denota una arista v a w.

GRAFO SIMPLE:

Es un par G = (V; E) donde V es un conjunto _nito no vació de elementos llamados vértices y E es un conjunto de pares no ordenados de elementos distintos de V llamados aristas.

GRAFO COMPLETO DE n VÉRTICES (Kn):

Es el grafo en donde cada vértice está relacionado con todos los demás, sin lazos ni lados paralelos. Se indica como Kn, en donde n es el número de vértices del grafo.

GRAFO COMPLETO:

Un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.

Un grafo completo de n vértices tiene n(n-1) / 2 aristas, y se nota Kn. Es un grafo regular con todos sus vértices de grado n-1. Ningún grafo completo tiene lazos y está conectado totalmente, por ende, la única forma de hacer disconexo el grafo con una eliminación de vértices es aplicarla a todos.

GRAFOS BIPARTIDOS:

Es un grafo cuyos vértices se pueden separar en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen un vértices de un conjunto con vértices de columnas (o filas) diferentes.

Los dos conjuntos U y V pueden ser pensados como un coloreo del grafo con dos colores: si pintamos los vértices en U azul y los vértices de V de verde obtenemos un grafo de dos colores donde cada arista tiene un vértice azul y el otro verde. Por otro lado, si un gráfico no tiene la propiedad de que se puede colorear con dos colores no es bipartito.

Un grafo bipartito suele con la partición de los vértices en U y V suele denotarse G = (U, V, E). Si |U| = |V|, esto es, si los dos subconjuntos tiene la misma cantidad de elementos, decimos que el grafo bipartito G es balanceado.

GRAFOS PLANOS:

Un grafo es plano si, y solo si, no contiene ningún subgrafo isomorfo a K5 ni a K3, 3, ni a subdivisiones de ellos.

Un grafo o es plano si no puede ser dibujado sobre un plano sin que sus aristas se intersequen. Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos.

GRAFOS CONEXOS:

En matemáticas y ciencias de la computación es aquel grafo que entre cualquier par de sus vértices existe un Camino (Grafo) que los une.

GRAFOS PONDERADOS:

Un grafo ponderado con pesos es un grafo G(V, E), en el que a cada arista se le asigna un valor real no negativo o peso. Sobre el conjunto de aristas se introduce una función peso. El peso de un subgrafo de un grafo ponderado es la suma de los pesos de todas sus aristas.

REFERENCIAS:

Chirinos, N. (14 de Noviembre de 2010). Teoria de Grafos. Conceptos básicos. Obtenido de SlideShare.net: http://es.slideshare.net/naborchirinos/conceptos-teoria-de-grafos-5778778

Murillo, J. A. (s.f.). Matemáticas para la computación. México: Alfaomega Grupo Editor, S. A. de C. V., México.

Toledo, I. (11 de Octubre de 2012). Teoria de Grafos. Obtenido de SlideShare.net: http://es.slideshare.net/isaiastoledo7/teora-de-grafos-14694334