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.
Zagadnienia teorii grafów zagadnienie mostów królewieckich lemat o uściskach dłoni kolorowanie grafów kolorowanie krawędzi grafu kolorowanie wierzchołków grafu twierdzenie o czterech barwach liczby Ramseya 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 skojarzenie twierdzenie Halla o kojarzeniu małżeństw 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 , Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].