Teoria de grafos

Solo disponible en BuenasTareas
  • Páginas : 3 (535 palabras )
  • Descarga(s) : 0
  • Publicado : 16 de febrero de 2012
Leer documento completo
Vista previa del texto
HISTORIA

La teoría de grafos pueden situarse en una época y un lugar definidos: el problema de los siete puentes de KÖNIGSBERG, resuelto en 1736 por Leonard Euler (1707- 1783). En 1752 apareció elTeorema Euler para Grafos planos, (este resultado fue presentado originalmente en términos de poliedros).

En 1847, Gustav Kirchhoff (1824- 1887) analizó un tipo espacial de grafo llamado árbol.(Un árbol es un grafo no dirigido sin lazos, conexo y sin ciclos.) Kirchhoff utilizó este concepto en ciertas aplicaciones de redes eléctricas, al formular su extensión de las leyes de Ohm para flujoseléctricos. Diez años más tarde, Arthur Cayley (1821- 1895) desarrolló el mismo tipo de grafos para contar los distintos isómeros de hidrocarburos saturados [pic] n [pic] Z.

En este periodoaparecieron también otras dos ideas más importantes. La conjetura de los cuatro colores fue investigada por primera vez alrededor de 1850 por Francis Guthrie (1831 – 1899). En el caso de los multígrafos,Kenneth Appel y Wolfgang Haken resolvieron mediante un complejo análisis computacional en 1976.

La segunda idea importante fue el ciclo hamiltoranio, llamado así en honor de sir William Rowan Hamilton(1805-1865), quien en 1859 usó la idea para formular un acertijo que usa las aristas de un dodecaedro regular.(no es muy difícil de hallar una solución para este problema, pero los matemáticos siguenbuscando las condiciones necesarias y suficientes para caracterizar los grefos no dirigidos que poseen un camino o ciclo hamiltonario.)

La caracterización de los grafos planos no dirigidos fueresuelta por el matemático polaco Kasimir Kuratowski (1896- 1980) en 1930. En 1936 aparece el primer libro sobre teoría de grafos, escrito por el matemático húngaro Denés König (1884 – 1944), destacadoinvestigador en este tema. Desde entonces, ha habido gran actividad en el área, especialmente durante las últimas cuatro décadas, con ayuda del computador. Entre muchos investigadores contemporáneos...
tracking img