Teoria grafów: Różnice pomiędzy wersjami
Wygląd
[wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m Robot dodał tr:Çizge Kuramı i poprawił tl:Teoriya ng grapa |
m r2.7.1) (Robot poprawił tl:Teoriya ng grapo |
||
Linia 88: | Linia 88: | ||
[[fi:Graafiteoria]] |
[[fi:Graafiteoria]] |
||
[[sv:Grafteori]] |
[[sv:Grafteori]] |
||
[[tl:Teoriya ng |
[[tl:Teoriya ng grapo]] |
||
[[th:ทฤษฎีกราฟ]] |
[[th:ทฤษฎีกราฟ]] |
||
[[tg:Назарияи графҳо]] |
[[tg:Назарияи графҳо]] |
Wersja z 17:58, 6 paź 2011
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 nie zwią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
- dominowanie
- 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