Teoria grafów: Różnice pomiędzy wersjami

Z Wikipedii, wolnej encyklopedii
Przeglądaj historię interaktywnie
[wersja przejrzana][wersja przejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
Dodanie przypisów w rozdziale "Historia"
Fafik (dyskusja | edycje)
Redaktorzy
22 585 edycji
WP:SK+ToS+mSI+Bn, drobne redakcyjne
Linia 1: Linia 1:
{{Teoria grafów}}
{{Teoria grafów}}


'''Teoria grafów''' to dział [[matematyka|matematyki]] i [[Informatyka|informatyki]] zajmujący się badaniem własności [[graf (matematyka)|grafów]]. [[Informatyka]] rozwija także [[algorytm]]y wyznaczające pewne właściwości grafów. [[Algorytm]]y te stosuje się do rozwiązywania wielu zadań praktycznych, często w dziedzinach na pozór niezwiązanych z grafami.
'''Teoria grafów''' to dział [[matematyka|matematyki]] i [[Informatyka|informatyki]] zajmujący się badaniem własności [[graf (matematyka)|grafów]]. [[Informatyka]] rozwija także [[algorytm]]y 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 [[Zagadnienie mostów królewieckich|zagadnienia mostów królewieckich]] opublikowany w [[1736]] roku przez [[Leonhard Euler|Leonharda Eulera]] jest uznawany za pierwszą pracę na temat teorii grafów.
Opis [[Zagadnienie mostów królewieckich|zagadnienia mostów królewieckich]] opublikowany w [[1736]] roku przez [[Leonhard Euler|Leonharda Eulera]] jest uznawany za pierwszą pracę na temat teorii grafów.

== Historia ==
⚫
Referat naukowy napisany przez [[Leonhard Euler|Leonarda Eulera]] na temat [[Zagadnienie mostów królewieckich|Zagadnienia Siedmiu Mostów]] i opublikowany w 1736 roku jest uważany za pierwszą pracę w historii teorii grafów<ref>{{Cytuj |autor = Biggs, N.; Lloyd, E.; Wilson, R. |tytuł = Graph Theory |data = 1986}}</ref>. To pismo, tak samo jak inne, napisane przez Vandermonde’a na temat „[[Problem skoczka szachowego|problemu skoczka szachowego]]”, kontynuowane &nbsp;przez analizę ''situs'' przez [[Gottfried Wilhelm Leibniz|Leibniza]]. Wzór Eulera zahaczający o liczbę krawędzi, wierzchołków oraz ściany wypukłego wielościanu był analizowany i zgeneralizowany przez [[Augustin Louis Cauchy|Cauchy’ego]]<ref>{{Cytuj |autor = Cauchy A. L. |tytuł = Recherche sur les polyèdres – premier mémoire |data = 1813}}</ref> i [[Simon Antoine Jean L’Huillier|L’Huiliera]]<ref>{{Cytuj |autor = L’Huillier |tytuł = Mémoire sur la polyèdrométrie |data = 1812-1813}}</ref>, reprezentują rozpoczęcie gałęzi matematyki znanej jako [[topologia]].

⚫
Ponad wiek po preferacje Eulera na temat&nbsp; Zagadnienia Siedmiu Mostów i podczas gdy Listing wprowadzał koncept topologii, [[Arthur Cayley|Cayley]] był prowadzony przez zainteresowanie w szczególności analitycznymi formami równania różniczkowego i zaczął studiować podklasę grafów, znaną jako [[Drzewo (matematyka)|drzewa]]<ref>{{Cytuj |autor = Cayley A. |tytuł = On the theory of the analytical forms called trees |data = 1857}}</ref>. Miało to duży wpływ na implikację chemii teoretycznej<ref>{{Cytuj |autor = Cayley A. |tytuł = Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen |data = 1875}}</ref>. 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 &nbsp;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 [[James Joseph Sylvester|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<ref>{{Cytuj |autor = Sylvester, James Joseph |tytuł = Chemistry and Algebra |data = 1878}}</ref>.<blockquote>„[…] Every invariant and co-variant thus becomes expressible by a ''graph'' precisely identical with a [[Friedrich August Kekulé von Stradonitz|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),</blockquote> <blockquote>co można luźno przetłumaczyć jako:</blockquote><blockquote>„[…]Każda niezmienna oraz współzmienna wtedy staje się wraważalna jako graf dokładnie identyczny z [[Friedrich August Kekulé von Stradonitz|Kekuleańskim]] diagramem chemikografu. &nbsp;[…]Podaję zasadę geometrycznej multiplikacji grafów, dla przykładu do stworzenia grafu jako produktu współwariantów, których osobne grafy są podane. […]”.</blockquote>Pierwszy podręcznik dotyczący teorii grafów został napisany przez Dénes Kőniga i opublikowany w 1936 roku<ref>{{Cytuj |autor = Tutte, W.T. |tytuł = Graph Theory |data = 2001}}</ref>. Kolejna książka Franka Harary’ego wydana w 1969 roku została „uznana na całym świecie za kompletny podręcznik na ten temat”<ref>{{Cytuj |autor = Gardner, Martin |tytuł = Fractal Music, Hypercards, and more…Mathematical Recreations from Scientific American |data = 1992}}</ref> 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<ref>{{Cytuj |autor = Society for Industrial and Applied Mathematics |tytuł = The George Polya Prize |data = 2002}}</ref>.

⚫
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 dowów zważający na tylko 633 kombinacje został podany dwadzieścia lat później przez Robertsona, Seymoura, Sandersa oraz Thomasa<ref>{{Cytuj |autor = Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R. |tytuł = The four color theorem |data = 1997}}</ref>.

⚫
Autonomiczny rozwój topologii od 1860 do 1930 roku zaplenił teorię grafów poprzez prace [[Marie Ennemond Camille Jordan|Jordana]], [[Kazimierz Kuratowski|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 [[Gustav Kirchhoff|Gustava Kirchoffa]], który opublikował w 1845 roku swoje prawa Kirchoffa do kalkulacji [[Napięcie elektryczne|napięcia]] i [[Prąd elektryczny|natężenia]] prądu w [[Obwód elektryczny|obwodach elektrycznych]].

⚫
Wprowadzenie probabilistycznych metod w teorii grafów, zwłaszcza w pracach [[Paul Erdős|Erdősa]] i [[Alfred Rényi|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 ==
== Zagadnienia teorii grafów ==
Linia 10: Linia 25:
* problem znajdowania drogi
* problem znajdowania drogi
** [[minimalne drzewo rozpinające]]
** [[minimalne drzewo rozpinające]]
** [[problem najkrótszej ścieżki]] [[PERT]] [[Ścieżka krytyczna|CPM]]
** [[problem najkrótszej ścieżki]] [[PERT]] [[Ścieżka krytyczna|CPM]]
** [[problem komiwojażera]]
** [[problem komiwojażera]]
* [[problem rekonstrukcji]]
* [[problem rekonstrukcji]]
* [[sieć przepływowa|zagadnienienia związane z sieciami przepływowymi]], [[maksymalny przepływ]]
* [[sieć przepływowa|zagadnienienia związane z sieciami przepływowymi]], [[Problem maksymalnego przepływu|maksymalny przepływ]]
* [[zbiór dominujący]]
* [[zbiór dominujący]]
* [[ekstremalna teoria grafów]]
* [[ekstremalna teoria grafów]]
* [[liczby Ramseya]]
* [[Twierdzenie Ramseya|liczby Ramseya]]
* [[skojarzenie]]
* [[Skojarzenie (teoria grafów)|skojarzenie]]
* [[izomorfizm grafów]]
* [[izomorfizm grafów]]
* [[grafy losowe]]
* [[grafy losowe]]
Linia 38: Linia 53:
* [[analiza sieciowa]]
* [[analiza sieciowa]]


== Historia ==
== Przypisy ==
{{Przypisy}}
⚫
Referat naukowy napisany przez [[Leonhard Euler|Leonarda Eulera]] na temat [[Zagadnienie mostów królewieckich|Zagadnienia Siedmiu Mostów]] i opublikowany w 1736 roku jest uważany za pierwszą pracę w historii teorii grafów.<ref>{{Cytuj |autor = Biggs, N.; Lloyd, E.; Wilson, R. |tytuł = Graph Theory |data = 1986}}</ref> To pismo, tak samo jak inne, napisane przez Vandermonde’a na temat „[[Problem skoczka szachowego|problemu skoczka szachowego]]”, kontynuowane  przez analizę ''situs'' przez [[Gottfried Wilhelm Leibniz|Leibniza]]. Wzór Eulera zahaczający o liczbę krawędzi, wierzchołków oraz ściany wypukłego wielościanu był analizowany i zgeneralizowany przez [[Augustin Louis Cauchy|Cauchy’ego]]<ref>{{Cytuj |autor = Cauchy A. L. |tytuł = Recherche sur les polyèdres - premier mémoire |data = 1813}}</ref> i [[Simon Antoine Jean L’Huillier|L’Huiliera]]<ref>{{Cytuj |autor = L'Huillier |tytuł = Mémoire sur la polyèdrométrie |data = 1812-1813}}</ref>, 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, [[Arthur Cayley|Cayley]] był prowadzony przez zainteresowanie w szczególności analitycznymi formami równania różniczkowego i zaczął studiować podklasę grafów, znaną jako [[Drzewo (matematyka)|drzewa]]<ref>{{Cytuj |autor = Cayley A. |tytuł = On the theory of the analytical forms called trees |data = 1857}}</ref>. Miało to duży wpływ na implikację chemii teoretycznej<ref>{{Cytuj |autor = Cayley A. |tytuł = Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen |data = 1875}}</ref>. 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 [[James Joseph Sylvester|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<ref>{{Cytuj |autor = Sylvester, James Joseph |tytuł = Chemistry and Algebra |data = 1878}}</ref>.<blockquote>"[…] Every invariant and co-variant thus becomes expressible by a ''graph'' precisely identical with a [[Friedrich August Kekulé von Stradonitz|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), </blockquote><blockquote>co można luźno przetłumaczyć jako:</blockquote><blockquote>„[…]Każda niezmienna oraz współzmienna wtedy staje się wraważalna jako graf dokładnie identyczny z [[Friedrich August Kekulé von Stradonitz|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. […]”.</blockquote>Pierwszy podręcznik dotyczący teorii grafów został napisany przez Dénes Kőniga i opublikowany w 1936 roku<ref>{{Cytuj |autor = Tutte, W.T. |tytuł = Graph Theory |data = 2001}}</ref>. Kolejna książka Franka Harary’ego wydana w 1969 roku została „uznana na całym świecie za kompletny podręcznik na ten temat”<ref>{{Cytuj |autor = Gardner, Martin |tytuł = Fractal Music, Hypercards, and more…Mathematical Recreations from Scientific American |data = 1992}}</ref> 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.<ref>{{Cytuj |autor = Society for Industrial and Applied Mathematics |tytuł = The George Polya Prize |data = 2002}}</ref>

⚫
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 dowów zważający na tylko 633 kombinacje został podany dwadzieścia lat później przez Robertsona, Seymoura, Sandersa oraz Thomasa<ref>{{Cytuj |autor = Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R. |tytuł = The four color theorem |data = 1997}}</ref>.

⚫
Autonomiczny rozwój topologii od 1860 do 1930 roku zaplenił teorię grafów poprzez prace [[Marie Ennemond Camille Jordan|Jordana]], [[Kazimierz Kuratowski|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 [[Gustav Kirchhoff|Gustava Kirchoffa]], który opublikował w 1845 roku swoje prawa Kirchoffa do kalkulacji [[Napięcie elektryczne|napięcia]] i [[Prąd elektryczny|natężenia]] prądu w [[Obwód elektryczny|obwodach elektrycznych]].


{{Dziedziny matematyki}}
⚫
Wprowadzenie probabilistycznych metod w teorii grafów, zwłaszcza w pracach [[Paul Erdős|Erdősa]] i [[Alfred Rényi|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.{{Dziedziny matematyki}}


{{Kontrola autorytatywna}}
{{Kontrola autorytatywna}}

Wersja z 15:10, 17 maj 2018

Teoria grafów
Najważniejsze pojęcia
Wybrane klasy grafów
Algorytmy grafowe
problemy grafowe
Inne zagadnienia

Teoria grafów to 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

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

Ważne algorytmy

Zobacz też

Przypisy

  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. ↑ James Joseph Sylvester, Chemistry and Algebra, 1878.
  7. ↑ W.T. Tutte, Graph Theory, 2001.
  8. ↑ Martin Gardner, 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.

Szablon:Dziedziny matematyki

Źródło: „https://pl.wikipedia.org/w/index.php?title=Teoria_grafów&oldid=53476639”