Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.Przykładyzastosowańgrafów
17
(oznaczmyichjako1,2,3,4,5).Wtabeli1.5sąpokazaneumiejętnościkandydatów
kwalifikująceichdoobjęciaposzczególnychstanowisk.Zaproponowaćobsadęsta-
nowisk.
Tabela1.5.Ilustracjaumiejętnościkandydatów
a
b
c
d
1
X
X
-
-
2
X
-
X
-
X
3
-
X
-
X
X
4
-
-
X
5
-
-
-
Rozwiązanie
Zadaniemożnaprzedstawićzapomocągrafu,wktórymzbiórwierzchołkówjestpo-
dzielonynadwarozłącznepodzbioryV
1={a,b,c,d}orazV
2={1,2,3,4,5}.Krawę-
dziełącząkandydatazestanowiskiem,doktóregomakwalifikacje(rys.1.14).Jestto
tzw.grafdwudzielny(p.rozdz.2).Rozwiązanieproblemu,wyrażonewjęzykugra-
fów,wymagaznalezieniaczterechwierzchołkoworozłącznychkrawędzi.Przykłado-
werozwiązaniewskazująpogrubionekrawędziegrafu.Zadaniejestilustracjątzw.
problemuskojarzenia(p.rozdz.16):wnaszymprzykładzieskojarzonesąnastępujące
parywierzchołków:a-2,b-1,c-4,d-5(pogrubionekrawędzienarysunku).
Rys.1.14.Przydziałkandydatówdostanowisk
Problem1.10.Kodybinarnewykrywająceikorygującebłędy
KostkaQ
ljestgrafemniezorientowanym,którejwierzchołkiodpowiadająciągombi-
narnymodługościl,akrawędziełącząwierzchołkiodpowiadająceciągomróżniącym
sięnadokładniejednejpozycji.Przykładykostekdlal=1,2,3sąpokazanenarys.1.15.
Kostkamazastosowanienp.wkodowaniubinarnymzwykrywaniem(ewentualnie
korekcją)błędów.Jeżelinp.dlal=3,zmożliwychośmiusłówbinarnychwybierzemy
czterysłowakodoweróżniącesięnadwóchpozycjach,tootrzymamykodzmożliwo-
