Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
6
1.Defnicjagrafuiprzykładyzastosowań
Problem1.1.Grafznajomości
●
1.2.Przykładyzastosowańgrafów
Wtrzypiętrowymbudynkumieszkalnymnakażdympoziomiesądwamieszkania.
Mieszkawnichosiemrodzin:naparterzeKowalscy(K)iWiśniewscy(W),napierw-
szympiętrzeZarembowie(Z)iNowakowie(N),nadrugimAdamscy(A)iMichalscy
(M),anatrzecimBiernaccy(B)iSłowikowie(S).Przyjmujemy,żerodzinymieszka-
jącenatymsamympiętrzeznająsięnawzajemiznająrodzinymieszkającenawyż-
szychpiętrach.Mającdodyspozycjitęinformację,narysujemytzw.grafznajomości
(rys.1.5).Wtymgrafiewierzchołkamisąrodziny,akrawędziepokazują,żerodziny
znająsięnawzajem.
Rys.1.5.Grafznajomości
Problem1.2[1.5].Uściskidłoni
PaństwoKowalscyzaprosiliczteryparymałżeńskienaspotkaniewichdomu.Kiedy
gościeprzybywali,niektórzyznichnapowitaniewymieniliuściskidłonizjużobec-
nymi.Oczywiścieniktniewymieniałuściskudłonizeswoimwspółmałżonkiemani
dwukrotnieztąsamąosobą.Kiedywszyscygościeprzybyli,paniKowalskazapytała
każdegozgości,ileuściskówdłoniwymienił.Wodpowiedzikażdyzzapytanych
podałinnąliczbę.IleuściskówdłoniwymieniłpanKowalski?
Rozwiązanie
Pytaniedotegozadanianiemapozorniegłębszegozwiązkulogicznegozjegotreścią.
Pokażemy,wjakisposóbmodelgrafowyułatwirozwiązanietegoproblemukombinato-
rycznego.Osobybiorąceudziałwprzyjęciusąreprezentowaneprzezwierzchołkigrafu.
