Problemy i algorytmy grafowe
Co to jest algorytm ?
Algorytm jest to 'przepis' postępowania, który dla właściwych danych wejściowych 'produkuje' żądane dane wyjściowe zwane wynikiem działania algorytmu. Algorytm można traktować więc jako sposób rozwiązania konkretnego problemu. Zwróćmy uwagę na fakt, że algorytmem jest na przykład przepis kucharski. Rozważmy następujący problem kulinarny:
Przykładowy problem i algorytm
Dane wejściowe : 1 kilogram ziemniaków
Szukane (dane wyjściowe): ugotowany 1 kilogram ziemniaków
Algorytm:
1. Obierz ziemniaki.
2. Wrzuć do gotującej wody.
3. Gotuj przez 20 minut.
4. Odcedź ziemniaki.
Algorytm taki mógłby stanowić podstawę do napisania oprogramowania
dla robota kuchennego gotującego ziemniaki.
Co to jest algorytm grafowy ?
Problemem 'grafowym' nazywamy problem,
który można rozwiązać używając pojęcia grafu.
Algorytm rozwiązujący pewien problem 'grafowy' nazywamy algorytmem
grafowym.
Oto kilka przykładów ważniejszych problemów grafowych.
- Problem kojarzenia małżenstw.
- Problem znajdowania najkrótszej drogi.
- Problem chińskiego listonosza.
- Problem komiwojażera.
- Problem niezawodności sieci.
- Zastosowanie liczby chromatycznej grafu.
- Zastosowanie indeksu chromatycznego grafu.
- Zastosowanie grubości grafu.
[ Początek strony ] [ MiNIWykłady ]