Teoria grafów


Teoria grafów w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Teoria grafów – - dział matematyki zajmujący się badaniem własności grafów. Opis zagadnienia mostów królewieckich opublikowany w 1736 roku przez Leonharda Eulera jest uznawany za pierwszą pracę na temat teorii grafów. Algorytmy grafowe są także przedmiotem badań informatyki.

Spis treści

Historia | 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 referacie 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ód 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 Whitneya. 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ényiego 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 kod

Ważne algorytmy | edytuj kod

Zobacz też | edytuj kod

Przypisy | edytuj kod

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