- Un conjunto V de puntos llamados vértices o nodos.
- Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados.
En un grafo simple entre dos nodos sólo hay un arco. Si hay más de un arco hablamos de un multigrafo. Si los arcos se pueden recorrer en una en una dirección concreta pero no en la contraria lo llamamos grafo dirigido o dígrafo y los arcos son entonces aristas, si los arcos salen y llegan al mismo punto formando un bucle el grafo resultante se llama pseudografo.
A pesar de que un grafo parece una estructura muy elemental, hay muchísimas propiedades de los grafos cuyo estudio ha dado lugar a una completa teoría matemática.
Fue Leonhard Euler quien ideó los grafos como una manera muy potente y elegante de resolver el problema de los puentes de Königsberg.
Königsberg (hoy Kaliningrado en Rusia) era en tiempos de Euler (siglo XVIII) una ciudad prusiana cruzada por siete puentes. Durante la época se suscitó la cuestión no resuelta de si era posible recorrer toda la ciudad cruzando cada uno de los puentes una y sólo una vez. Si hacemos una representación esquemática de la ciudad vemos que los puentes unen cuatro porciones de tierra. La búsqueda por prueba y error no conduce a ningún resultado.
Euler realizó una abstracción del problema representando mediante puntos las cuatro porciones de terreno y dibujando un arco entre cada dos puntos por cada puente. Llamó orden de cada vértice al numero de arcos que se reunían en el y se percató que el orden de cada vértice visitado en un recorrido sin saltos ha de ser par (sale un enlace y entra otro) excepto para dos puntos del grafo: aquellos donde se inicia y donde se acaba el recorrido, que han de tener orden impar.
Si el vértice donde se inicia y se acaba son el mismo entonces todos los vértices han de ser de orden par.
En el problema de Königsberg el orden de todos los nodos es 3, esto es impar, por lo que quedó claro que no existía solución para el problema. No había un camino que recorriese todos los puentes pasando una sola vez por cada uno de ellos.
El interés de este ejemplo es que además de dar lugar a una teoría matemática muy potente los grafos se dibujan y resultan muy intuitivos, especialmente cuando los vértices son pocos. Ejemplos de grafos que todos conocemos son los organigramas que explicitan la estructura formal de la empresa, los árboles genealógicos o la circuitería de los chips electrónicos.
Se usan regularmente para resolver problemas en la eficiencia del transporte, en sociología, electrónica y electricidad, detección de fraude y en general en aquellos campos en los que la conectividad es importante.
Programa Java .zip
