Ludzie pragną czasami się rozstawać, żeby móc tęsknić, czekać i cieszyć się z powrotem.
Korzystaj¸ac z drzew spinaj¸acych z poprzedniego zadania, znajdź zbiór cykli fundamentalnych dla grafów.
15. Zmodyfikuj algorytm przeszukiwania grafu wszerz tak, aby wyznaczał on także drzewo spinaj¸ace (złożone z tych kraw¸edzi, którymi przeszedł algorytm). Zastosuj ten algorytm do grafów z rysunków 1.1, 1.7 i 1.10.
16. Sprawdź, które grafy przedstawione na rysunkach w tym rozdziale posiadaj¸a cykl (lub drog¸e) Eulera.
17. Sprawdź, które grafy przedstawione na rysunkach w tym rozdziale posiadaj¸a cykl lub drog¸e Hamiltona.
18. Zastosuj algorytm kolorowania z nawrotami do grafu z rysunku 1.7.
19. Znajdź graf, dla którego heurystyka przedstawiona w podrozdziale o kolorowaniu grafów nie znajduje optymalnego kolorowania.
20. Narysuj hiperkostk¸e
. Wskaż w niej cykl Hamiltona. Prześledź na niej protokół
rozsyłania wiadomości.
1.17. Problemy
31
1.17
Problemy
Oto algorytm konstrukcji minimalnego drzewa spinaj¸acego
dla grafu
.
: (1) zaczynamy od zbioru wszystkich kraw¸edzi
grafu
, (2) sortujemy
kraw¸edzie
według długości, od najdłuższej do najkrótszej (3) dla każdej kraw¸edzi *
usuwamy j¸a z
, jeżeli jej usuni¸ecie nie rozspójnia grafu
.
Udowodnij poprawność tego algorytmu.
Zastosuj powyższy algorytm do grafu z rysunku 1.9a.
%
Niech
b¸edzie dowolnym grafem z wagami kraw¸edzi
, a
dowolnym minimalnym drzewem spinaj¸acym. Pokaż, że dla dowolnego wierzchołka
do
należ¸a te kraw¸edzie wychodz¸acych z , które maja najkrótsze wagi, to znaczy,
"
"
jeżeli
i
s¸a dwiema kraw¸edziami przyległymi do
takimi, że
oraz
, to
5
5
*
*
%
/
%
.
5
*