Teoria grafów

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Niniejszy artykuł jest częścią cyklu teoria grafów.




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem marszrutyzacji
problem kojarzenia małżeństw


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


Teoria grafów – dział matematyki i informatyki zajmujący się badaniem własności grafów. Informatyka rozwija także algorytmy wyznaczające pewne właściwości grafów. Algorytmy te stosuje się do rozwiązywania wielu zadań praktycznych, często w dziedzinach na pozór niezwiązanych z grafami.

Opis zagadnienia mostów królewieckich opublikowany w 1736 roku przez Leonharda Eulera jest uznawany za pierwszą pracę na temat teorii grafów.

Historia[edytuj | edytuj kod]

Referat naukowy napisany przez Leonarda Eulera na temat Zagadnienia Siedmiu Mostów i opublikowany w 1736 roku jest uważany za pierwszą pracę w historii teorii grafów[1]. To pismo, tak samo jak inne, napisane przez Vandermonde’a na temat „problemu skoczka szachowego”, kontynuowane  przez analizę situs przez Leibniza. Wzór Eulera zahaczający o liczbę krawędzi, wierzchołków oraz ściany wypukłego wielościanu był analizowany i zgeneralizowany przez Cauchy’ego[2] i L’Huiliera[3], reprezentują rozpoczęcie gałęzi matematyki znanej jako topologia.

Ponad wiek po preferacje Eulera na temat  Zagadnienia Siedmiu Mostów i podczas gdy Listing wprowadzał koncept topologii, Cayley był prowadzony przez zainteresowanie w szczególności analitycznymi formami równania różniczkowego i zaczął studiować podklasę grafów, znaną jako drzewa[4]. Miało to duży wpływ na implikację chemii teoretycznej[5]. Technika, której używał, dotyczyła głównie wyliczenia grafów o konkretnych własnościach. Wyliczenia teorii grafów wzrosły dzięki wynikom Calyley’a i fundamentalne wyniki zostały opublikowane przez  Pólya między 1935 a 1937 rokiem. Zostały zgeneralizowane przez De Bruijina w 1959 roku. Calyley połączył swoje wyniki na drzewach z ówczesnymi studiami chemicznej kompozycji. Zmieszanie pomysłów z matematyki z tymi z chemii rozpoczęły to, co stało się częścią standardowej terminologii teorii grafów.

W szczególności, wyrażenie „graf” zostało wprowadzone przez Sylvestera w pracy opublikowanej w 1878 roku w dzienniku nazwanym Nature, gdzie pokazał analogię między „niezmienną kwantową” a „współwariantami” algebry i diagramów molekularnych[6].

„[…] Every invariant and co-variant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph. […] I give a rule for the geometrical multiplication of graphs, i.e. for constructing a graph to the product of in- or co-variants whose separate graphs are given. […]” (kursywą zaznaczono oryginalne wyrażenia),

co można luźno przetłumaczyć jako:

„[…]Każda niezmienna oraz współzmienna wtedy staje się wraważalna jako graf dokładnie identyczny z Kekuleańskim diagramem chemikografu.  […]Podaję zasadę geometrycznej multiplikacji grafów, dla przykładu do stworzenia grafu jako produktu współwariantów, których osobne grafy są podane. […]”.

Pierwszy podręcznik dotyczący teorii grafów został napisany przez Dénes Kőniga i opublikowany w 1936 roku[7]. Kolejna książka Franka Harary’ego wydana w 1969 roku została „uznana na całym świecie za kompletny podręcznik na ten temat”[8] i pozwoliła matematykom, chemikom, inżynierom elektrycznym oraz naukowcom społecznym porozumieć się ze sobą. Harary podarował wszystkie datki na zafundowanie Nagrody Pólya[9].

Jednym z najsławniejszych oraz pobudzających problemów w teorii grafów jest 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 De Morgana zaadresowanego do Hamiltona tego samego roku. Wiele niepoprawnych dowodów było proponowanych, włączając te od Cayleya, Kempego oraz innych. Generalizacja tego problemu przez Taita, Heawooda, 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[10][11]. Komputerowy dowód stworzony w 1976 roku przez 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 dowów zważający na tylko 633 kombinacje został podany dwadzieścia lat później przez Robertsona, Seymoura, Sandersa oraz Thomasa[12].

Autonomiczny rozwój topologii od 1860 do 1930 roku zaplenił teorię grafów poprzez prace Jordana, Kuratowskiego oraz Whitney’a. Kolejny ważny czynnik zwykłego rozwoju teorii grafów oraz topologii wyróżnił się od użycia nowoczesnej algebry. Pierwszy przykład użycia pochodzi z pracy Gustava Kirchoffa, który opublikował w 1845 roku swoje prawa Kirchoffa do kalkulacji napięcia i natężenia prądu w obwodach elektrycznych.

Wprowadzenie probabilistycznych metod w teorii grafów, zwłaszcza w pracach Erdősa i Rényi’ego na asymptotycznym prawdopodobieństwie łączności grafu, zainicjowało do kolejnej gałęzi, znanej jako teoria losowych grafów, która była owocnym źródłem wyników teoretycznych grafów.

Zagadnienia teorii grafów[edytuj | edytuj kod]

Ważne algorytmy[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. N. Biggs, E. Lloyd, R. Wilson, Graph Theory, 1986.
  2. Cauchy A. L., Recherche sur les polyèdres – premier mémoire, 1813.
  3. L’Huillier, Mémoire sur la polyèdrométrie, 1812–1813.
  4. Cayley A., On the theory of the analytical forms called trees, 1857.
  5. Cayley A., Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen, 1875.
  6. Sylvester, James Joseph, Chemistry and Algebra, 1878.
  7. Tutte, W.T., Graph Theory, 2001.
  8. Gardner, Martin, Fractal Music, Hypercards, and more…Mathematical Recreations from Scientific American, 1992.
  9. Society for Industrial and Applied Mathematics, The George Polya Prize, 2002.
  10. Heinrich Heesch, Untersuchungen zum Vierfarbenproblem., 1969.
  11. K. Appel, W. Haken, Every planar map is four colorable. Part II. Reducibility, 1977.
  12. N. Robertson i inni, The four color theorem, 1997.