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)
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.
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.
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.
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 ={a1,a2, a3…, an} y B = {b1,b2,…, bm} en donde los elementos del conjunto B, pero entre los vértices de un mismo conjunto no existe arista que los una.
es el grafo que está compuesta por dos conjuntos de vértices, A ={a1,a2, a3…, an} y B = {b1,b2,…, bm} 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 ( Kn , m)
Es el grafo que esta compuesto por dos conjuntos de vértices, uno de ellos A ={a1,a2, a3…, an} Y otro B= {b1,b2,…, bm), 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 kn, m. (petul, 2011)
Es el grafo que esta compuesto por dos conjuntos de vértices, uno de ellos A ={a1,a2, a3…, an} Y otro B= {b1,b2,…, bm), 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 kn, 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.
- Permite calcular la distancia mínima entre 2 puntos de 1 grafo.
- Cada nodo se representa por:
- Pasos:
- Asignar el valor 0 al nodo origen
- 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)
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
