Teoría de grafos: Diferenzas entre revisións

A orixe da teoría dos grafos remóntase ao século XVIII co [[Problema de los puentes de Königsberg|problema das pontes de Königsberg]], que consistía en atopar un camiño que percorrese as sete pontes do [[Río Pregolya|río Pregel]] ({{Coordenadas|54|42|12|N|20|30|56|E|region:RU_source:nlwiki}}  / , ) na cidade de Königsberg, actualmente [[Kaliningrado]], de modo que se percorresen todas as pontes pasando unha soa vez por cada unha delas. O traballo de [[Leonhard Euler]] sobre o problema titulado ''Solutio problematis ad geometriam situs pertinentis''<ref>{{Cita publicación periódica|apelidos=Euler, L.|título=Solutio problematis ad geometriam situs pertinentis|url=http://math.dartmouth.edu/~euler/docs/originals/E053.pdf|revista=Commentarii Academiae Scientiarum Imperialis Petropolitanae|ID=128-140}}</ref> (''A solución dun problema relativo á xeometría da posición'') en [[1736]], é considerado o primeiro resultado da teoría dos grafos. Tamén se considera un dos primeiros resultados topolóxicos. Este exemplo ilustra a profunda relación entre a teoría de grafos e a [[topoloxía]].

En 1852 [[Francis Guthrie]] expuxo o [[Teorema das catro cores|problema das catro cores]], que afirma que é posible, utilizando soamente catro cores, colorear calquera mapa de países de tal forma que dous países veciños nunca teñan a mesma cor. Este problema, que non foi resolto até un século despois por [[Kenneth Appel]] e [[Wolfgang Haken]] en [[1976]], pode ser considerado como o nacemento da teoría dos grafos. Ao tratar de resolvelo, os matemáticos definiron vocábulos e conceptos teóricos fundamentais dos grafos.

En 1857, [[Arthur Cayley]] estudou e resolveu o problema de enumeración dos [[Isomería|isómeros]], compostos químicos con idéntica composición (fórmula) pero diferente [[Estructura molecular|estrutura molecular.]]. Para iso representou cada [[Composto químico|composto]], nese caso [[Hidrocarburo|hidrocarburos saturados]] CnH2nC_nH_2n+2, mediante un grafo onde os vértices representan [[Átomo|átomosátomo]]s e as arestas a existencia de [[Enlace químico|enlaces químicos]].

O primeiro libro sobre teoría de grafos foi escrito por [[Dénes Kőnig]] e publicado en 1936.<ref>Modelo{{cita desbotadolibro|apelidos=Tutte|nome=W.T.|ligazón-autor=W. UseT. unTutte|título=Graph dos [[Modelo:Modelos de citasTheory|modeloseditorial=Cambridge deUniversity citas]] no lugar deste marcadorPress|year=2001|isbn=978-0-521-79489-3|páxina=30|url=http://books.google.com/books?id=uTGhooU37h4C&pg=PA30}}.</ref>