Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.Przykładyzastosowańgrafów
7
Pary,którewymieniłyuściskdłoniłączymykrawędzią.Liczbawierzchołkówgrafujest
równa10.Najmniejszaliczbauściskówmożebyćrównazeru,anajwiększaosiem.
WierzchołekreprezentującypaniąKowalskąopatrzymyetykietą9,akażdyzpozosta-
łychwierzchołkówgrafuotrzymanumerbędącyliczbąuściskówdłoniwymienionych
przezdanąosobę.Pierwszykrokrozwiązaniajestprzedstawionynarys.1.6a.Wierz-
chołekreprezentującypaniąKowalskąwyróżnionoinnymsymbolemgraficznym.
Rys.1.6.Ilustracjaalgorytmuobliczaniauściskówdłoni
Osobaonumerze0niewymieniłażadnegouściskudłoni.Zatemosobaonume-
rze8musiaławymienićuściskizewszystkimiosobamionumerach1-7orazzpanią
Kowalską.Gościeonumerach0,8tworząwięcparęmałżeńską.Następnymgościem
onajwiększejliczbieuściskówjestosobaopatrzonaetykietą7.Niemógłonwymie-
nićpozdrowieńzosobamionumerach0,1(wyczerpanelimityuścisków),azatem
musiałuścisnąćdłonieosóbonumerach2-6,paniKowalskiejorazzgodniezpo-
przednimkrokiemgościaonumerze8(rys.1.6b).Małżonkiemtejosobyjestgość
oznaczonynumerem1.Wnastępnymkrokubudowaniamodelugrafowegowierz-
chołekonumerze6stajesięwierzchołkiemrozpatrywanym.Osobaetykietowana
tymnumeremniemogławymienićpozdrowieńzgośćmionumerach0,1,2.Musiała
uścisnąćdłonieosóbonumerach3,4,5,paniKowalskiejizgodniezpoprzednimi
krokamigościonumerach7i8(rys.1.6c).Małżonkiemtejosobyjestgośćopatrzo-
nynumerem2.Przechodzącdowierzchołkaonumerze5,wpodobnysposóbstwier-
