Artefactos matemáticos

fos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos:

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.

De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.

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. (Para más información véase por ejemplo el glosario de grafos de Chris Caldwell o la introducción en español de la wikipedia o la más extensa en inglés)

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

...