Teoria grafów: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja nieprzejrzana] |
link |
Dodanie rozdziału "Historia" |
||
| Linia 38: | Linia 38: | ||
* [[analiza sieciowa]] |
* [[analiza sieciowa]] |
||
== [[analiza sieciowa|Historia]] == |
|||
{{Dziedziny matematyki}} |
|||
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. 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]] i [[Simon Antoine Jean L’Huillier|L’Huiliera]], 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]]. Miało to duży wpływ na implikację chemii teoretycznej. 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.<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. Kolejna książka Franka Harary’ego wydana w 1969 roku została „uznana na całym świecie za kompletny podręcznik na ten temat” 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. |
|||
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. 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. |
|||
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.{{Dziedziny matematyki}} |
|||
{{Kontrola autorytatywna}} |
{{Kontrola autorytatywna}} |
||
Wersja z 14:10, 12 maj 2018
| 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.
Zagadnienia teorii grafów
- kolorowanie grafów
- problem znajdowania drogi
- problem rekonstrukcji
- zagadnienienia związane z sieciami przepływowymi, maksymalny przepływ
- zbiór dominujący
- ekstremalna teoria grafów
- liczby Ramseya
- skojarzenie
- izomorfizm grafów
- grafy losowe
- komputerowa reprezentacja grafów
- problem chińskiego listonosza
Ważne algorytmy
- algorytm Bellmana-Forda
- algorytm Dijkstry
- algorytm Floyda-Warshalla
- algorytm Johnsona
- algorytm Kruskala
- algorytm Prima
- algorytm najbliższego sąsiada
Zobacz też
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. 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 i L’Huiliera, 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. Miało to duży wpływ na implikację chemii teoretycznej. 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.
"[…] 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. Kolejna książka Franka Harary’ego wydana w 1969 roku została „uznana na całym świecie za kompletny podręcznik na ten temat” 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.
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. 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.
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.Szablon:Dziedziny matematyki