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 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
  • 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
• dominowanie
• 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