Fundamentos de la teoría de grafos y su representación
1. Concepto e introducción
La teoría de grafos (Graph Theory) es una rama de las matemáticas discretas y es el estudio de los grafos (Graph).
Un grafo es una estructura matemática utilizada para modelar relaciones por pares entre objetos. Está compuesto por "nodos" o "vértices" (Vertex) y por las "aristas" (Edge) que conectan estos vértices.
Es importante señalar que el conjunto de vértices de un grafo no puede estar vacío, pero el conjunto de aristas sí puede estarlo. Un grafo puede ser no dirigido, lo que significa que las aristas no necesitan distinguir dirección al conectar los vértices. De lo contrario, se dice que el grafo es dirigido. La figura izquierda siguiente es una estructura típica de grafo no dirigido, mientras que la derecha es un grafo dirigido. Todos los grafos presentados en este capítulo son no dirigidos.
Clasificación de grafos: grafos no ponderados y grafos ponderados. Si las aristas que conectan nodos tienen un valor numérico asociado, se trata de un grafo ponderado; de lo contrario, es un grafo no ponderado.
Conectividad de un grafo:En la teoría de grafos, un grafo conexo se basa en el concepto de conectividad. En un grafo no dirigido G, si hay un camino que conecta el vértice i con el vértice j (y por supuesto también de j a i), entonces se dice que i y j están conectados. Si G es un grafo dirigido, entonces todas las aristas en el camino que conecta i y j deben tener la misma dirección. Si dos puntos cualesquiera del grafo están conectados, entonces se dice que el grafo es conexo. Si este grafo es dirigido, se denomina fuertemente conexo (nota: se requiere que haya caminos en ambos sentidos). La conectividad es una propiedad fundamental de los grafos.
Grafo completo:Un grafo completo es un grafo no dirigido simple en el que exactamente una arista conecta a cada par de vértices distintos.
Lazo (auto-bucle):El punto inicial y el punto final de una arista son el mismo vértice.
Aristas paralelas:Existen múltiples aristas que conectan dos vértices.
2. Descripción de aplicación
Los grafos se pueden utilizar para modelar muchos tipos de relaciones y procesos en sistemas físicos, biológicos, sociales y de información. Muchos problemas prácticos pueden representarse mediante grafos. Por lo tanto, la teoría de grafos se ha convertido en una poderosa herramienta matemática en numerosas disciplinas como la investigación operativa, la cibernética, la teoría de la información, la teoría de redes, la teoría de juegos, la física, la química, la biología, las ciencias sociales, la lingüística y las ciencias de la computación. Al enfatizar su aplicación en sistemas del mundo real, a veces se define una red como un grafo en el que las relaciones entre atributos (por ejemplo, nombres) se representan en forma de nodos y/o aristas.
3. Formas de representación de grafos
Matriz de adyacencia:1 significa que están conectados, 0 significa que no están conectados.
Lista de adyacencia:Solo se expresa la información de los vértices adyacentes a un vértice.
La lista de adyacencia es adecuada para representar grafos dispersos (Sparse Graph).
La matriz de adyacencia es adecuada para representar grafos densos (Dense Graph).
Código de ejemplo en Java
Descarga del paquete de código fuente:Download
(1) Matriz de adyacencia
Código del archivo src/ejemplo/graph/DenseGraph.java:
/**
* Matriz de adyacencia
*/
public class DenseGraph {
// Número de nodos
private int n;
// Número de aristas
private int m;
// Si es un grafo dirigido
private boolean directed;
// Datos específicos del grafo
private boolean[][] g;
// Constructor
public DenseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g se inicializa como una matriz booleana de n*n, cada g[i][j] es false, indicando que no hay ninguna arista
// false es el valor predeterminado de las variables de tipo boolean
g = new boolean[n][n];
}
// Devuelve el número de nodos
public int V(){ return n;}
// Devuelve el número de aristas
public int E(){ return m;}
// Añade una arista al grafo
public void addEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
if( hasEdge( v , w ) )
return;
g[v][w] = true;
if( !directed )
g[w][v] = true;
m ++;
}
// Verifica si hay una arista de v a w en el grafo
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
return g[v][w];
}
}
(2) Lista de adyacencia
Código del archivo src/ejemplo/graph/SparseGraph.java:
import java.util.Vector;
/**
* Lista de adyacencia
*/
public class SparseGraph {
// Número de nodos
private int n;
// Número de aristas
private int m;
// Si es un grafo dirigido
private boolean directed;
// Datos específicos del grafo
private Vector<Integer>[] g;
// Constructor
public SparseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g se inicializa como n vectores vacíos, lo que significa que cada g[i] está vacío, es decir, no hay ninguna arista
g = (Vector<Integer>[])new Vector[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Integer>();
}
// Devuelve el número de nodos
public int V(){ return n;}
// Devuelve el número de aristas
public int E(){ return m;}
// Añade una arista al grafo
public void addEdge( int v, int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
g[v].add(w);
if( v != w && !directed )
g[w].add(v);
m ++;
}
// Verifica si hay una arista de v a w en el grafo
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v].elementAt(i) == w )
return true;
return false;
}
}