Teoría de Grafos

5.1 elementos, características y componentes de los grafos.

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

 

A partir de esta figura se definen los siguientes elementos:

Vértices (nodos) : Se indican por medio de un pequeño círculo y se les asigna un número o letra. En el grafo anterior los vértices son V= {a, b, c, d}.

Lados (ramas o aristas): Son las líneas que unen un vértice con otro y se les asigna una letra, un numero o una combinación de ambos. En el grafo anterior los lados son: L= {1, 2, 3, 4, 5, 6}.

Lados paralelos: Son aquellas aristas que tienen relación con un mismo par de vértices. En el grafo anterior los lados paralelos son: P = {2,3}.

Lazo: Es aquella arista que sale de un vértice y regresa al mismo vértice. En el grafo anterior se tiene el lazo: A= {6}

Valencia de un vértice
Es el número de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:
Valencia (a)=2
Valencia (b)=4
Valencia (c)=2
Valencia (d)=3
Hay que observar como en el caso del vértice del lazo solo se considera una vez, entrada o salida pero no ambos. (Equipo9, 2014)

5.1.1 Tipos de grafos

GRAFOS SIMPLES.
Son aquellos grafos que no tienen lazos ni lados paralelos.

La valencia en cada uno de los vértices de los grafos completos es (n – 1), y el número de lados está dado por la expresión

                     Núm. De lados = n(n – 1)

                                                     2
en donde n es el número de vértices del grafo.

Grafo conexo

Un grafo G es conexo si y solo si existe un camino simple para cualesquiera dos de sus nodos. Se dice que un grafo G es completo si cada nodo u de G es adyacente a todos los demás nodos de G claramente, un grafo así es conexo, un grafo completo de n nodos tendrá n (n-1)/2 aristas.

 

Grafo Dirigido

Un grafo dirigido G, también llamado digrafo, es lo mismo que un multigrafo, solo que cada arista e de G tiene una dirección asignada o, en otras palabras, cada arista e está identificada por un par ordenado (u, v) de nodos G en vez del par desordenado [u.v].

Un grafo dirigido (V, A) consta de un conjunto V de vértices y de un conjunto A de aristas, que son pares ordenados de elementos de V. Utilizamos el par ordenado 〈〉para indicar que es una arista dirigida del vértice u al vértice v. (upload, s.f.)

COMPLEMENTO DE UN GRAFO (G‘)
Es el grafo que le falta al grafo G, de forma que entre ambos formas de grafo completo de n vértices. Este grafo no tiene lazos ni ramas paralelas.

GRAFO BIPARTIDO
es el grafo que está compuesta por dos conjuntos de vértices, A ={a₁,a_2, a₃…, a_n} y B = {b₁,b₂,…, b_m} en donde los elementos del conjunto B, pero entre los vértices de un mismo conjunto no existe arista que los una.

Una forma muy sencilla de saber si un grafo es bipartido es aplicar el hecho de que nunca tiene un ciclo de longitud impar, además de que debe cumplir con la característica mencionada anteriormente.

GRAFO BIPARTIDO COMPLETO ( K_{n , m})
Es el grafo que esta compuesto por dos conjuntos de vértices, uno de ellos A ={a₁,a_2, a₃…, a_n} Y otro B= {b₁,b₂,…, b_m), y en el cada vértice de A esta unido con todo los vértices de B, pero entre los vértices de un mismo conjunto no existe arista que los una. El grafo bipartido completo se indica como  k_{n, m}. (petul, 2011)

5.2 Representación de los grafos.

5.2.1 REPRESENTACIÓN MATEMÁTICA DE LOS GRAFOS.

Representación Matemática De Los Grafos 

Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en todas las áreas de Ingeniería. Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd. 

5.2.2 REPRESENTACIÓN COMPUTACIONAL DE LOS GRAFOS.

Representación Comunicacional De Los Grafos 

Existen diferentes formas de representar un grafo (simple), además de la geométrica y muchos métodos para almacenarlos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria. Estructura de lista, lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas. Lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra. Lista de grados - También llamada secuencia de grados o sucesión gráfica de un grafo no-dirigido es una secuencia de números, que corresponde a los grados de los vértices del grafo. Estructuras matriciales Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño, donde es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces el elemento es 1, de lo contrario, es 0. Matriz de incidencia - El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado). (Ortegón, s.f.)

5.3 Algoritmo de recorrido y búsqueda.

5.3.1 El camino más corto

Algoritmo de Floyd-Warshall

En informática, el algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy,  es un algoritmo de análisis sobre grafos para encontrar el camino mínimo entre grafos. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución.

1. Permite calcular la distancia mínima entre 2 puntos de 1 grafo.
2. Cada nodo se representa por:
3. Pasos:

1. Asignar el valor 0 al nodo origen
2. Mediante un proceso iterativo se le asignará a cada nodo Xi un valor n igual a la longitud del camino más corto que exista desde el nodo origen al nodo Xj. 

Algoritmo Dijkstra:

El 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 con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

1.- Dado un V0, Dijkstra busca un conjunto D con

• Las menores distancias de V0 al resto de vértices

  2.- Al inicio, solo conocemos

• Las distancias de los adyacentes
• D es inicializada a  
•  Factor de peso para los adyacentes, Infinito ∞ para los no adyacentes

3.- D va ser mejorado sucesivamente

• Escogiendo el vértice Vk no elegido antes
• Que tenga la distancia mas corta V0, Vk
• Probamos si pasando por Vk
• Se puede obtener distancias mas cortas de las que tenemos
• Para cada Vértice restante del grafo. (Matematicas discretas, s.f.)

5.3.2 A lo ancho

Busqueda por anchura (BFS - Breadth First Search).
Es un algoritmo para recorrer o buscar un elemento en un grafo. Intuitivamente se comienza por la raíz y se exploran todos los vecinos de ese nodo. Para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta recorrer todos.
Definición rápida de algoritmo de profundidad
La búsqueda en profundidad, llamada Depth First Search en inglés, es un algoritmo usado para recorrer o buscar elementos en un árbol o un grafo y pertenece al grupo de las búsquedas no informadas (sin heurísticas). Su procedimiento consiste en visitar todos los nodos de forma ordenada pero no uniforme en un camino concreto, dejando caminos sin visitar en su proceso. Una vez llega al final del camino vuelve atrás hasta que encuentra una bifurcación que no ha explorado, y repite el proceso hasta acabar el árbol. (carrillo, 2014)

5.3.3 En profundidad

Muchos algoritmos de grafos necesitan visitar de un modo sistemático todos los vértices de un grafo. En la búsqueda en profundidad se avanza de vértice en vértice, marcando cada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún vértice. Cuando se alcanza un vértice cuyos vecinos han sido marcados, se retrocede al anterior vértice visitado y se avanza desde éste.

(docencia, s.f.)

Referencias

carrillo, l. f. (11 de marzo de 2014). Prezi. Obtenido de Prezi: https://prezi.com/nch2fc3drxtg/busqueda-por-anchura/

docencia. (s.f.). Obtenido de docencia: http://docencia.udea.edu.co/regionalizacion/teoriaderedes/informaci%F3n/C3_Profundidad.pdf

Equipo9. (23 de noviembre de 2014). Obtenido de Equipo9: http://9relaciones.blogspot.mx/2014/11/teoria-de-grafos.html#1

Matematicas discretas. (s.f.). Obtenido de Matematicas discretas: https://sites.google.com/site/matematicasmoralesgalindo/6-3-algoritmos-de-recorrido-y-busqueda/6-3-1-algoritmos-de-recorrido-y-busqueda-el-camino-mas-corto

Ortegón, A. D. (s.f.). Matematicas Discretas. Obtenido de Matematicas Discretas: http://mate-discretasj2.blogspot.mx/p/blog-page.html

petul, G. (jueves de diciembre de 2011). Teoria de Grafos. Obtenido de Teoria de Grafos: http://teoriadegrafos-isc.blogspot.mx/2011/12/tipos-de-grafos-simples-completos.html

upload. (s.f.). Obtenido de upload: https://upload.wikimedia.org/wikipedia/commons/5/5f/Introducci%C3%B3n_a_la_Teor%C3%ADa_de_Grafos.pdf