Otwórz menu główne

Zmiany

Dodane 6077 bajtów, 1 rok temu
Dodanie rozdziału "Historia"
* [[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}}