TEMA 3 Grafos

 

Vídeo de apoyo

Lect. de apoyo

3.1. Introducción

Uno de los primeros resultados de la teoría de grafos fue el que o, Leonhard Euler en el siglo xvin al resolver el problema de los puentes Kónigsberg. Este problema consiste en recorrer 7 puentes que conec porciones de tierra, bajo la condición de pasar por cada puente una vez. En la siguiente figura se muestra la forma en que están distrib; los puentes:
 

Uno de los primeros resultados de la teoría de grafos fue el que o, Leonhard Euler en el siglo xvin al resolver el problema de los puentes Kónigsberg. Este problema consiste en recorrer 7 puentes que conec porciones de tierra, bajo la condición de pasar por cada puente una vez.

Euler representó este problema por medio de una figura como la siguiera

y la llamó “grafo”. A las porciones de tierra representadas por un pmr las llamó “vértices”, a los puentes representados por líneas les dio el noi bre de “aristas” y al número de líneas que salen o entran a un vértice llamó “orden del vértice”, el cual más tarde se llamó valencia.

3.2. Partes del grafo
3.4. Representación matricial
3.5. Caminos y circuitos
3.6. Isomorfos
3.7. Gráficos planos
3.8. Aplicación de los grafos