Teoria grafów
 | Nie mylić z: Grafologia. |
Teoria grafów – dział matematyki zajmujący się badaniem własności grafów. Za pierwszą pracę na temat teorii grafów uznawany jest opis zagadnienia mostów królewieckich, opublikowany w 1736 roku przez Leonharda Eulera. Algorytmy grafowe są także przedmiotem badań informatyki[1].
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
- prawdopodobieństwo spójności grafu losowego (drzewa losowego)
- 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ż
Przypisy
- ↑ Grafów teoria, [w:] Encyklopedia PWN [dostęp 2021-07-22] .
Linki zewnętrzne
Graph theory (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].
- p
- d
- e
Działy matematyki dyskretnej
| kombinatoryka | |
|---|---|
| teoria grafów |
|
| inne |
|
- p
- d
- e
Działy matematyki
| działy ogólne |
| ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| działy czyste |
| ||||||||||||||||||
| działy stosowane |
| ||||||||||||||||||
| powiązane dyscypliny |
|
- p
- d
- e
Teoria grafów
| Najważniejsze pojęcia |
więcej... |
|---|---|
| Wybrane klasy grafów | |
| Algorytmy grafowe | |
| problemy grafowe | |
| Inne zagadnienia |
Kontrola autorytatywna (dyscyplina naukowa):
- PWN: 3907414
- Britannica: topic/graph-theory
- Universalis: theorie-des-graphes
- БРЭ: 2376760
- DSDE: grafteori
- identyfikator w Hrvatska enciklopedija: 70127
