teoría de grafos: reseña histórica algoritmos y ... · pdf fileteor a de...
If you can't read please download the document
TRANSCRIPT
Teora de grafos: Resena historicaAlgoritmos y Estructuras de Datos III
El origen: Los puentes de Konigsberg
Leonhard Euler (17071783)
El origen: Los puentes de Konigsberg
I La ciudad de Konigsberg (hoy Kaliningrado) tena en el sigloXVIII siete puentes.
I Euler (1735) planteo (y resolvio) el problema de cruzar portodos ellos exactamente una vez y volver al punto de partida.
El origen: Los puentes de Konigsberg
I L. Euler, Solutio problematis ad geometriam situs pertinentis(26 de Agosto de 1735) [E53].
El origen: Los puentes de Konigsberg
I Euler mostro que el problema no tiene solucion y dio unacondicion necesaria para el caso general.
I Carl Hierholzer (1840-1871) mostro en 1871 que estacondicion es tambien suficiente, y formalizo la demostracion.
El origen: Los puentes de Konigsberg
I Euler mostro que el problema no tiene solucion y dio unacondicion necesaria para el caso general.
I Carl Hierholzer (1840-1871) mostro en 1871 que estacondicion es tambien suficiente, y formalizo la demostracion.
El origen: Los puentes de Konigsberg
I Euler mostro que el problema no tiene solucion y dio unacondicion necesaria para el caso general.
I Carl Hierholzer (1840-1871) mostro en 1871 que estacondicion es tambien suficiente, y formalizo la demostracion.
El origen: Los puentes de Konigsberg
I Euler mostro que el problema no tiene solucion y dio unacondicion necesaria para el caso general.
I Carl Hierholzer (1840-1871) mostro en 1871 que estacondicion es tambien suficiente, y formalizo la demostracion.
El origen: Los puentes de Konigsberg
I Euler mostro que el problema no tiene solucion y dio unacondicion necesaria para el caso general.
I Carl Hierholzer (1840-1871) mostro en 1871 que estacondicion es tambien suficiente, y formalizo la demostracion.
El origen: Los puentes de Konigsberg
Segundo acto: El problema del caballo
Definicion. Un caballo de ajedrez debe visitar todas las casillaspasando exactamente una vez por cada una.
Segundo acto: El problema del caballo
I La referencia mas temprana a este problema es del siglo IX.I Alexandre-Theophile Vandermonde (17351796) estudio este
problema, pero no encontro una solucion.I A. Vandermonde, Remarques sur des problemes de situation.
Academie des Sciences (1771).
I El primer algoritmo (heurstico!) fue presentado en 1823. Enterminos modernos, es una heurstica golosa que en cada pasose mueve al vecino de menor grado.
I H. C. Warnsdorff, Des Rosselsprungs einfachste undallgemeinste Losung (1823).
Segundo acto: El problema del caballo
I La referencia mas temprana a este problema es del siglo IX.I Alexandre-Theophile Vandermonde (17351796) estudio este
problema, pero no encontro una solucion.I A. Vandermonde, Remarques sur des problemes de situation.
Academie des Sciences (1771).
I El primer algoritmo (heurstico!) fue presentado en 1823. Enterminos modernos, es una heurstica golosa que en cada pasose mueve al vecino de menor grado.
I H. C. Warnsdorff, Des Rosselsprungs einfachste undallgemeinste Losung (1823).
Segundo acto: El problema del caballo
Este problema corresponde a encontrar un circuito Hamiltonianoen el siguiente grafo:
Segundo acto: El problema del caballo
Una solucion para el caso de 8 8:
Tercer acto: Mas sobre grafos Hamiltonianos
Sir William Hamilton (18051865)
Tercer acto: Mas sobre grafos Hamiltonianos
I Hamilton (1857) invento el juego icosiano, que consiste enencontrar un camino que pase por todos los vertices de undodecaedro y que retorne al punto de partida.
Tercer acto: Mas sobre grafos Hamiltonianos
I Un recorrido con estas propiedades se llama actualmentecircuito hamiltoniano, y para este caso particular se puedeencontrar una solucion.
La partida de nacimiento: Sylvester
James Sylvester (18141897)
El termino grafo (graph) fue introducido en 1887 por Sylvester, enel contexto de analisis algebraico de estructuras moleculares.
La partida de nacimiento: Sylvester
The theory of ramification is one of pure colligation, for it takesno account of magnitude or position; geometrical lines are used,but have no more real bearing than those employed in genealogicaltables have in explaining the laws of procreation.
El desafo: La conjetura de los cuatro colores
Conjetura. Todo mapa se puede colorear usando 4 colores, demodo tal que regiones adyacentes usen colores distintos.
I Las regiones deben ser contiguas.
I Dos regiones no se consideran adyacentes si solo se intersecanen un punto.
El desafo: La conjetura de los cuatro colores
El desafo: La conjetura de los cuatro colores
El desafo: La conjetura de los cuatro colores
El desafo: La conjetura de los cuatro colores
El desafo: La conjetura de los cuatro colores
El desafo: La conjetura de los cuatro colores
El desafo: La conjetura de los cuatro colores
I August Mobius (17901868) conoca este problema, aunquees posible que no sea el mismo quien lo haya propuesto porprimera vez.
I Francis Guthrie (18311899) redescubrio la conjetura mientrascoloreaba un mapa de Inglaterra, y su hermano la comunico aAugustus De Morgan (18061871).
I A student of mine asked me to day to give him a reason for afact which I did not know was a fact and do not yet. He saysthat if a figure be any how divided and the compartmentsdifferently coloured so that figures with any portion ofcommon boundary line are differently coloured four coloursmay be wanted but not more the following is his case inwhich four colours are wanted. Query cannot a necessity forfive or more be invented.
El desafo: La conjetura de los cuatro colores
I August Mobius (17901868) conoca este problema, aunquees posible que no sea el mismo quien lo haya propuesto porprimera vez.
I Francis Guthrie (18311899) redescubrio la conjetura mientrascoloreaba un mapa de Inglaterra, y su hermano la comunico aAugustus De Morgan (18061871).
I A student of mine asked me to day to give him a reason for afact which I did not know was a fact and do not yet. He saysthat if a figure be any how divided and the compartmentsdifferently coloured so that figures with any portion ofcommon boundary line are differently coloured four coloursmay be wanted but not more the following is his case inwhich four colours are wanted. Query cannot a necessity forfive or more be invented.
El desafo: La conjetura de los cuatro colores
I August Mobius (17901868) conoca este problema, aunquees posible que no sea el mismo quien lo haya propuesto porprimera vez.
I Francis Guthrie (18311899) redescubrio la conjetura mientrascoloreaba un mapa de Inglaterra, y su hermano la comunico aAugustus De Morgan (18061871).
I A student of mine asked me to day to give him a reason for afact which I did not know was a fact and do not yet. He saysthat if a figure be any how divided and the compartmentsdifferently coloured so that figures with any portion ofcommon boundary line are differently coloured four coloursmay be wanted but not more the following is his case inwhich four colours are wanted. Query cannot a necessity forfive or more be invented.
El desafo: La conjetura de los cuatro colores
I Alfred Kempe (18491922) dio una demostracion en 1879,pero Percy Heawood (18611955) encontro en 1890 un error.Al mismo tiempo, demostro el teorema de los cinco colores.
I Oystein Ore (18991968) y Joel Stemple mostraron en 1969que la conjetura es cierta para todos los mapas de hasta 40regiones.
I Kenneth May, The origin of the four-color conjecture. Isis 56(1965) 346348 ...
El desafo: La conjetura de los cuatro colores
I Alfred Kempe (18491922) dio una demostracion en 1879,pero Percy Heawood (18611955) encontro en 1890 un error.Al mismo tiempo, demostro el teorema de los cinco colores.
I Oystein Ore (18991968) y Joel Stemple mostraron en 1969que la conjetura es cierta para todos los mapas de hasta 40regiones.
I Kenneth May, The origin of the four-color conjecture. Isis 56(1965) 346348 ...
El desafo: La conjetura de los cuatro colores
I Alfred Kempe (18491922) dio una demostracion en 1879,pero Percy Heawood (18611955) encontro en 1890 un error.Al mismo tiempo, demostro el teorema de los cinco colores.
I Oystein Ore (18991968) y Joel Stemple mostraron en 1969que la conjetura es cierta para todos los mapas de hasta 40regiones.
I Kenneth May, The origin of the four-color conjecture. Isis 56(1965) 346348 ...
El desafo: La conjetura de los cuatro colores
El desafo: La conjetura de los cuatro colores
I The conjecture has acted as a catalyst in the branch ofmathematics known as combinatorial topology and is closelyrelated to the currently fashionable field of graph theory. Morethan half a century of work by many (some say all)mathematicians has yielded proofs for special cases.
I The consensus is that the conjecture is correct but unlikelyto be proved in general. It seems destined to retain for sometime the distinction of being both the simplest and mostfascinating unsolved problem of mathematics.
El desafo: La conjetura de los cuatro colores
Appel y Haken en 2002
I La primera demostracion fue dada en 1976 por Kenneth Appel(1932) y Wolfgang Haken (1928), coronando una carrerapor la demostracion.
El desafo: La conjetura de los cuatro colores
Appel y Haken en 2002
I L