grafos estructura discreta rafael chacin urbe

1. GRAFOS:
1.1. HISTORIA:
Los 7 puentes del río Pregel en Königsberg. El origen de la teoría de
grafos se remonta al siglo XVIII con el problema de los puentes de
Königsberg, el cual consistía en encontrar un camino que recorriera
los siete puentes del río Pregel (54°42′12″N 20°30′56″E) en la ciudad
de Königsberg, actualmente Kaliningrado, de modo que se
recorrieran todos los puentespasando una sola vez por cada uno de
ellos. El trabajo de Leonhard Euler sobre el problema titulado “Solutio
problematis ad geometriam situs pertinentis” (La solución de un
problema relativo a la geometría de la posición) en 1736, es
considerado el primer resultado de la teoría de grafos. También se
considera uno de los primeros resultados topológicos en geometría
(que no depende de ningunamedida). Este ejemplo ilustra la
profunda relación entre la teoría de grafos y la topología.

Otro usó de los grafos fue al problema del caballo que se define: Un
caballo de ajedrez debe visitar todas las casillas pasando
exactamente una vez por cada una: La referencia más temprana a
este problema es del siglo IX Alexandre-Theophile Vandermonde
(1735–1796) estudio este problema, pero no encontróuna solución.

El primer algoritmo (heurístico!) fue presentado en 1823. En términos
modernos, es una heurística golosa que en cada paso se mueve al
vecino de menor grado. Este problema corresponde a encontrar un
circuito Hamiltoniano en el siguiente grafo:

Su solución fue para el caso de 8 x 8:

Luego, en 1847, Gustav Kirchhoff utilizó la teoría de grafos para el
análisis de redeseléctricas publicando sus leyes de los circuitos para
calcular el voltaje y la corriente en los circuitos eléctricos, conocidas
como leyes de Kirchhoff, considerado la primera aplicación de la
teoría de grafos a un problema de ingeniería.
En 1852 Francis Guthrie planteó el problema de los cuatro colores el
cual afirma que es posible, utilizando solamente cuatro colores,
colorear cualquier mapade países de tal forma que dos países
vecinos nunca tengan el mismo color. Este problema, que no fue
resuelto hasta un siglo después por Kenneth Appel y Wolfgang
Haken en 1976, puede ser considerado como el nacimiento de la
teoría de grafos.

Al tratar de resolverlo, los matemáticos definieron términos y
conceptos teóricos fundamentales de los grafos. El término «grafo»,
proviene de laexpresión «graphic notation» usada por primera vez
por Edward Frankland y posteriormente adoptada por Alexander
Crum Brownen 1884, y hacía referencia a la representación gráfica
de los enlaces entre los átomos de una molécula. El primer libro
sobre teoría de grafos fue escrito por Dénes Kőnig y publicado
en1936
Páginas de referencia:

http://www.academia.edu/7530808/Historia_de_grafos_Los_7_puentes_
del_r%C3%ADo_Pregel_en_K%C3%B6nigsberg
http://www.dc.uba.ar/materias/aed3/2014/2c/teorica/historia.pdf

1.2.

CONCEPTOS:
Un grafo es un conjunto de puntos y un conjunto de líneas, cada una
de las cuales une un punto con otro. Los puntos se llaman nodos o
vértices de un grafo y las líneas se llaman aristas o arcos.
Que es un nodo:
Un nodo es la unidad sobre la que seconstruye el árbol y puede
tener cero o más nodos hijos conectados a él.

Aristas:
Son las líneas con las que se unen las aristas de un grafo y con la
que se construyen también caminos y se dividen en:
-

-

-

Aristas Adyacentes:
Se dice que dos aristas son adyacentes si coinciden en el mismo
vértice.
Aristas Paralelas:
Se dice que dos aristas son paralelas si vértice inicial y elfinal son el
mismo.
Aristas Cíclicas:
Arista que parte de un vértice para entrar en el mismo.
Cruce: Son dos aristas que cruzan en un punto.
Vértices:
Son los puntos o nodos con los que esta conformado un grafo.
Llamaremos grado de un vértice al número de aristas de las que es
extremo. Se dice que un vértice es `par' o `impar' según lo sea su
grado.

-

-

Vértices Adyacentes:
si...