Introduccion a La Teoria De Grafos

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 = { n1, n2, n3,n4,n5, n6, n7,n8 } , A = { {n1, n2}}, {n1, n5},{n2, n3},{n3, n4} , {n4, n7}, {n2, n6},{n6, n2} } Outline del contenido


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 a1(n2, n6) , a2(n2, n6) son dos aritas para unir los nodos n2 y n6. 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 (n1, n2). Valencias