Teoria grafów

Teoria grafów dział w matematyce i informatyce 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.

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
• przegląd zagadnień z zakresu matematyki
• programowanie sieciowe
• analiza sieciowa