Teoria grafów

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

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