Contenido
Elementos, características y componentes de los grafos .............................................................................. 2
Tipos de grafos .......................................................................................................................................... 3
Representación de los Grafos........................................................................................................................ 4
Matemática ............................................................................................................................................... 5
Computacional .......................................................................................................................................... 5
Algoritmos de recorrido y búsqueda ............................................................................................................ 5
El más corto............................................................................................................................................... 5
El algoritmo de recorrido en anchura ....................................................................................................... 6
El algoritmo de recorrido en profundidad ................................................................................................ 7
Bibliography .................................................................................................................................................. 8
Elementos, características y componentes de los grafos
Aristas: Son las líneas con las que se unen las aristas de un grafo y con la que se construyen
también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a},
siendo a y b los vértices que une. Si {a, b} es una arista, a los vértices a y b se les llama sus
extremos.
Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
Cruce: Son dos aristas que cruzan en un punto.
Vértices: Son los puntos o nodos con los que está conformado un grafo. Llamaremos grado de
un vértice al número de aristas de las que es extremo. Se dice que un vértice es "par" o "impar"
según lo sea su grado.
Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos una arista
que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el
vértice adyacente.
Vértice Aislado: Es un vértice de grado cero.
Vértice Terminal: Es un vértice de grado 1.
Caminos: Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no
vacía de aristas {x, v1}, {v1, v2}, {vn, y}. En este caso x e y se llaman los extremos del camino.
El número de aristas del camino se llama la longitud del camino.
Si los vértices no se repiten el camino se dice propio o simple.
Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino
cerrado.
Llamaremos ciclo a un circuito simple.
Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es
accesible respecto a si mismo.
Tipos de grafos
Hay dos tipos básicos de grafos: grafos no dirigidos y gafos dirigidos.
Grafos dirigidos: Sea V un conjunto finito no vacío, y sea la relación binaria E ⊆ V x V. El par
ordenado (V, E) es un grafo dirigido sobre V, o dígrafo, donde V es el conjunto de vértices o
nodos y E es su conjunto de aristas. Escribimos G = (V, E) para denotar tal dígrafo. En la Figura 1
se puede ver como se representan los grafos dirigidos o dígrafos, con vértices V = {A, B, C} y
aristas E = {(B, A), (A, C), (C, A), (C, B)} (Ciencias computacionales).
Grafos no dirigidos: Cuando no importa la dirección de las aristas, la estructura G = (V, E), donde
E es ahora un conjunto de pares no ordenados sobre V, es decir el conjunto de aristas
representa una relación simétrica binaria, donde si VJ y VK son vértices cualesquiera del
conjunto de vértices V de un grafo, (VJ, VK) ∈ E −→ (VK, VJ) ∈ E. Decimos que tenemos un grafo
no dirigido. En la Figura 2 se puede ver como se representan los grafos no dirigidos, con vértices
V = {A, B, C, D} y aristas E = {(A, B), (B, C), (C, D), (D, A)} (Ciencias computacionales).
Subgrafo: Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son
subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G
es H o es isomorfo a H (dependiendo de las necesidades de la situación).
Además de los dos grafos básicos, dirigidos y no dirigidos, hay otros tipos de grafos, tales como:
a) Grafos de cadena: son un tipo de grafo híbrido formado por aristas dirigidas y no
dirigidas.
b) Grafos simples: Es un tipo de grafo el cual no incluye ciclos ni aristas paralelas.
c) Multígrafo: Son grafos con dos o más aristas que pueden conectar a un mismo vértice •
Grafos completo: Es un grafo con aristas entre cada par de vértices.
d) Grafo bipartito: Son grafos que se pueden dividir en dos subconjuntos disjuntos de
vértices, donde cada una de las aristas conecta un vértice del primer conjunto con uno
del segundo.
e) Grafo pesado: Es un grafo que tiene pesos asociados a vértices y/o aristas.
(Ciencias computacionales)
Representación de los Grafos
Matriz de adyacencia:
La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la
correspondiente fila (columna) está 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 está compuesta
sólo por ceros (BlogSpot, 2017).
Matriz de incidencia:
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 (BlogSpot, 2017).
Matemática
En matemáticas y ciencias de la computación, la teoría de grafos, también llamada teoría de
loas graficas estudia las propiedades de los grafos (también llamados graficas) Un grafo es un
conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de partes de vértices
llamados aristas (BlogSpot, 2017).
Computacional
Existen diferentes formas de almacenar grafos 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 y aunque
frecuentemente se usa una combinación de ambos.
Algoritmos de recorrido y búsqueda
Las técnicas para recorrido de grafos han sido utilizadas en muchas aplicaciones como la
solución de circuitos eléctricos, en la exploración de entornos en robótica móvil, en el control de
información en redes informáticas, entre otras [1]. Esto se debe a que todos los sistemas
mencionados pueden ser modelados como grafos. Esto también es aplicable en el caso de las
redes de distribución, donde cada nodo en la red de distribución es un nodo del grafo, y cada
línea entre los nodos de la red de distribución, es un arco en el grafo. Para este caso se
consideraron redes radiales, que son las más comunes en las redes de distribución, por lo que
en los grafos no se obtenían trayectorias cerradas. Para el recorrido de grafos se pueden
emplear técnicas heurísticas como son búsqueda en anchura o BFS y búsqueda en profundidad
o DFS. Estas técnicas de recorrido permiten efectuar los cálculos necesarios para realizar los
flujos de carga, cálculo de momentos eléctricos, regulación, etc. progresivamente.
El más corto
El problema de los caminos más cortos es el problema que consiste en encontrar un camino
entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo
constituyen es mínima. Ahora bien, podemos emplear el algoritmo de Dijkstra para estos casos,
los pasos o procedimientos a seguir para éste algoritmo son los siguientes: Teniendo un grafo
dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N
guardará al final del algoritmo las distancias desde x al resto de los nodos.
1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas
al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x
a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos
a estos vi
4. Si la distancia desde x hasta va guardada en D es mayor que la distancia desde x hasta a,
sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada.
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse
almacenándolos valores en una cola de prioridad) y volvemos al paso 3 mientras existan
nodos no marcados.
El algoritmo de recorrido en anchura
El algoritmo de recorrido en anchura o BFS, explora sistemáticamente todas las ramas o aristas
del grafo de manera que primero se visitan los nodos o vértices más cercanos a un nodo inicial.
Para la implementación de este algoritmo se utiliza globalmente un contador y un vector de
enteros para marcar los vértices ya visitados y almacenar el recorrido. El algoritmo BFS requiere
también un vector de cola auxiliar para gestionar los vértices no visitados. En muchos casos es
necesario ejecutar este algoritmo empezando en los nodos más alejados del nodo escogido
como nodo inicial (Escobar & Giraldo Suárez, 2005).
El algoritmo de recorrido en profundidad
El algoritmo de recorrido en profundidad o DFS, explora sistemáticamente las ramas o aristas
del grafo de manera que primero se visitan los nodos o vértices adyacentes a los visitados más
recientemente. De esta forma se va “profundizando” en el grafo, es decir, alejándose
progresivamente del nodo inicial. Esta estrategia admite una implementación simple en forma
recursiva, utilizando globalmente un contador y un vector de enteros para marcar los vértices ya
visitados y almacenar el orden del recorrido.
Citas
BlogSpot. (2017, Noviembre 28). Retrieved from Blogspot Web Site: [Link]
(n.d.).Ciencias computacionales. Propedeutico: Matematicas Discretas. Instituto Nacional de Astrofísica,
Tonantzintla.
Escobar, A. L., & Giraldo Suárez, E. (2005). Implementación de algoritmos de recorrido de grafos para el
cálculo de la regulación en redes de distribución radiales. Scientia Et Technica, 33-35.
Montero, G. (n.d.). Tipos de Grafos. Exploracion de Grafos. Escuela de Informatica Universidad de las
Palmas de Gran Canaria, Las Palmas de Gran Canaria.