Teoria grafów: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
→Historia: drobne merytoryczne: "preferacje (?) Eulera" > "referacie Eulera" |
→Historia: lit., ort. |
||
Linia 13:
Jednym z najsławniejszych oraz pobudzających problemów w teorii grafów jest [[Twierdzenie o czterech barwach|problem czerech kolorów]]: „Czy jest prawdziwe, że jakakolwiek mapa narysowana na płaszczyźnie może mieć pokolorowane regiony czterema kolorami, tak, aby dwa sąsiednie regiony miały różne kolory?”. Ten problem jako pierwszy przedstawił [[Francis Guthrie]] w 1852 roku i jego pierwszy zapis jest w liście [[Augustus De Morgan|De Morgana]] zaadresowanego do [[William Rowan Hamilton|Hamiltona]] tego samego roku. Wiele niepoprawnych dowodów było proponowanych, włączając te od Cayleya, Kempego oraz innych. Generalizacja tego problemu przez [[Peter Tait|Taita]], Heawooda, [[Frank Ramsey|Ramseya]] oraz Hadwigera doprowadziła do studiów na temat kolorowania grafów osadzonych na powierzchniach arbitralnych rodzajów, przeformułowanie Taita wygenerowała nową klasę problemów, „problemy faktoryzacji”, dokładnie studiowane przez Petersena oraz Kőniga. Prace Ramseya na temat kolorowania i dokładniejsze wyniki opracowane przez Turána w 1941 roku były początkiem kolejnej gałęzi teorii grafów, nazwanej „ekstremalną teorią grafów”.
Problem czterech kolorów pozostał nierozwiązany przez ponad wiek. W 1969 roku Heinrich Heesch opublikował metodę rozwiązania problemu używając komputerów<ref>{{Cytuj |autor = Heinrich Heesch |tytuł = Untersuchungen zum Vierfarbenproblem. |data = 1969}}</ref><ref>{{Cytuj |autor = Appel, K.; Haken, W. |tytuł = Every planar map is four colorable. Part II. Reducibility |data = 1977}}</ref>. Komputerowy dowód stworzony w 1976 roku przez [[Kenneth Appel|Kennetha Appela]] i Wolfganga Hakena zasadniczo wykorzystuje pojęcie „rozładowania” rozwiniętego przez Heescha. Dowód zawierał sprawdzenie własności 1936 konfiguracji przez komputer i nie został w pełni zaakceptowany z powodu swojej złożoności. Prostszy
Autonomiczny rozwój topologii od 1860 do 1930 roku zaplenił teorię grafów poprzez prace [[Marie Ennemond Camille Jordan|Jordana]], [[Kazimierz Kuratowski|Kuratowskiego]] oraz
Wprowadzenie probabilistycznych metod w teorii grafów, zwłaszcza w pracach [[Paul Erdős|Erdősa]] i [[Alfred Rényi|
== Zagadnienia teorii grafów ==
| |||