Teoria grafów

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

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka 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 Breadth-first search Depth-first search Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego

edytuj ten szablon

Teoria grafów to dział matematyki zajmujący się badaniem własności grafów. Rozwijanie algorytmów wyznaczających pewne właściwości grafów jest jednym z bardziej znaczących pól działania informatyki. Algorytmy te stosuje się do rozwiązywania wielu zadań praktycznych, często w dziedzinach na pozór nie związanych z grafami.

[edytuj] 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

[edytuj] Ważne algorytmy

• algorytm Bellmana-Forda
• algorytm Dijkstry
• algorytm Floyda-Warshalla
• algorytm Johnsona
• algorytm Kruskala
• algorytm Prima
• algorytm najbliższego sąsiada

[edytuj] Zobacz też

• graf
• przegląd zagadnień z zakresu matematyki
• programowanie sieciowe
• analiza sieciowa