Tema 3.1

Problema de los Puentes de Könisberg

Definición: Un grafo G = (N,A) consta de un conjunto de nodos N y un conjunto de aristas A, en donde a cada arista es un par no ordenado de nodos. Una arista en general se representa por {a,b}.

Una forma de represtar grafos es mediante círculos para los nodos, conectados por líneas para las aristas.

Ejemplo: G = { n₁, n₂, n₃,n₄,n₅, n₆, n₇,n₈ } , A = { {n₁, n₂}}, {n₁, n₅},{n₂, n₃},{n₃,

Notación: Una arista es un conjunto, pero puede haber dos aristas que conecte los mismos nodos, por lo que se le puede anteponer un nombre, por ejemplo a₁(n₂, n₆) , a₂(n₂, n₆) son dos aritas para unir los nodos n₂ y n₆. También puede ser que en un arista importe el orden de los nodos por lo que podemos en este caso utilizar la notación de par ordenado (n₁, n₂). Valencias