Teoria grafów

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
  • twierdzenie o czterech barwach
• problem znajdowania drogi
  • minimalne drzewo rozpinające
  • problem najkrótszej ścieżki PERT CPM
  • problem komiwojażera
• 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ż

• graf
• programowanie sieciowe
• analiza sieciowa

Przypisy

Linki zewnętrzne

• Graph theory (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].