Conceptos Fundamentales y Algoritmos Clave en la Teoría de Grafos
Enviado por Programa Chuletas y clasificado en Matemáticas
Escrito el en 
español con un tamaño de 19,31 KB
Fundamentos de la Teoría de Grafos
Un grafo 
es 
un conjunto formado por 
vértices y un conjunto de arcos o aristas (edges en inglés) que son un conjunto de duplas 
.
Definiciones Básicas
Grafo Dirigido
Un grafo es dirigido si hay un arco de 
a 
pero no de
a
para algún 
. Es decir, si los arcos “tienen flechas”.
Adyacencia
Un vértice
es adyacente de
si 
.
Camino
Existe un camino de 
a 
si 
con todos los
. Un camino es simple si no se repite ningún vértice en el trayecto de ese camino.
Longitud de un Camino
La longitud de un camino es el número de arcos que hay que tomar para llegar al último vértice desde el primero.
Ciclo
Un ciclo es un camino de
a
. Un ciclo es simple si no se repite ningún vértice excepto el primero y el último.
Propiedades y Tipos de Grafos
Grafo Conexo
Un grafo es conexo si existe un camino entre cada par de nodos.
Grafo Completo
Un grafo es completo si existe un arco entre cada par de nodos.
Grado de un Nodo
El grado de un nodo es el número de arcos que entran o salen del nodo. De esta definición surgen dos conceptos:
- Grado de entrada: El número de arcos que van hacia el nodo en cuestión.
- Grado de salida: El número de arcos que salen del nodo en cuestión.
Grafo Ponderado
Un grafo ponderado implica asignar un valor (peso) a cada arco del grafo.
Subgrafo
Un grafo 
es subgrafo de otro grafo 
si 
y 
.
Recorridos en Grafos
Nota sobre la Lista de Adyacencia
Un inconveniente de la lista de adyacencia es que resulta difícil medir el grado de entrada de un nodo.
Definición de Recorrido
Un recorrido es una manera sistemática de visitar todos los nodos del grafo. Hay dos tipos principales de recorrido:
- Recorrido en Anchura (BFS): Utiliza una
COLA. - Recorrido en Profundidad (DFS): Utiliza una
PILA.
Algoritmos de Recorrido
Algoritmo de Recorrido en Anchura (BFS)
Recibimos un grafo y elegimos un vértice que llamaremos inicial.
- Meter el vértice inicial en “visitados”.
- Encolar el vértice inicial.
- Repetir los pasos 4) a 6) hasta vaciar la cola.
- Imprimir el primero de la cola, al que llamamos
, y desencolarlo. - Encolar adyacentes de
no visitados.
- Meter adyacentes de
en visitados.
Algoritmo de Recorrido en Profundidad (DFS)
Recibimos un grafo y elegimos un vértice que llamaremos inicial.
- Meter el vértice inicial en “visitados”.
- Apilar el vértice inicial.
- Repetir los pasos 4) a 6) hasta vaciar la pila.
- Imprimir la cima de la pila, al que llamamos
, y desapilarlo.
- Apilar adyacentes de
no visitados.
- Meter adyacentes de
en visitados.
Algoritmo de Dijkstra y Ordenación Topológica
Esquema del Algoritmo de Dijkstra
Aplicamos el siguiente código:
Void Dijkstra (tabla T){
Vertices V, W;
While (algún vértice no visitado){
V = vértice no visitado con
más pequeña
T[V].visitado = 1;
For (cada W adyacente de V){
If (T[V].d + peso
(Nota: El fragmento de código del algoritmo de Dijkstra parece incompleto en el documento original).
Ordenación Topológica
Una ordenación topológica en un grafo necesariamente dirigido y acíclico (DAG) es una ordenación de los nodos del grafo que cumple lo siguiente:
Si hay un camino de 
a 
, entonces en el orden se cumple que
aparece antes que
.