Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
8
1.Defnicjagrafuiprzykładyzastosowań
dzamy,żeosobaetykietowanatymnumeremniemogławymienićuściskuzgośćmi
onumerach0,1,2,3.Natomiastwymieniłauściskizosobąonumerze4,panią
Kowalskąorazzgodniezpoprzednimikrokamizgośćmionumerach6,7,8.Tęsy-
tuacjęprzedstawiagrafnarys.1.6d.Małżonkiemosobyoetykiecie5jestgośćopa-
trzonynumerem3.Tymkrokiemzakończyliśmyprocedurę,gdyżstopieńkażdego
wierzchołkabudowanegografujestrównyjegonumerowi.Małżonkiempani
Kowalskiejmożebyćtylkoosobaoetykiecie4,apanKowalskiwymieniłcztery
uściskidłoni.
Problem1.3.Systemostrzeganiapomiędzyzamkami
Wśredniowieczudoobronyterytoriumsłużyłsystemzamkówobronnych.Wprzy-
padkuzbliżaniasięnieprzyjacielazamkiprzesyłałysobienawzajemostrzeżenia.
Przypuśćmy,żerozpatrywaneterytoriumjestkwadratemoboku50km.Znajdujesię
nanim7zamków:trzydużeiczterymałe.Informacjezdużychzamkówmogąbyć
przesyłanenaodległośćniewiększąniż20km,azmałychdo14km.Przyjmijmy
jedenzwierzchołkówkwadratuzapoczątekukładówwspółrzędnych.Lokalizacja
poszczególnychzamkówjestopisanawtabeli1.1podającejwspółrzędne(x,y)zamku.
Chcemynarysowaćgrafobrazującysystemkomunikacji.
Tabela1.1.Współrzędnepołożeniazamków
Typ
Współrzędne
Zamek
(14,16)
duży
A
(34,14)
duży
B
(25,35)
duży
C
(25,10)
mały
d
(12,35)
mały
e
(37,37)
mały
f
(24,25)
mały
g
Systemobronnybyłpomyślanytak,abyinformacjawysłanazdowolnegozamku
mogłabyćprzekazanadowszystkichpozostałych.Czytenwarunekjestspełniony?
Podczaszłejpogodyzasięgprzesyłuinformacjizkażdegozamkumalejeo10%.Czy
nadalinformacjawysłanazdowolnegozamkumożebyćprzekazanadowszystkich
pozostałychzamków?Gdyjedenzzamków(dowolny)wskutekawariiniebędzie
mógłprzesyłaćinformacji,czysystemostrzeżeńbędzienadaldziałałpoprawniepo-
międzypozostałymizamkami?
Rozwiązanie
Wtabeli1.2przedstawionoodległościzamków.Pogrubionymdrukiemzaznaczono
odległościmniejszeodzasięguprzesyłuinformacji,zakładając,żeelementwiersz
przesyłainformacjędoelementukolumny.
Grafsiecikomunikacjizamkówjestprzedstawionynarys.1.7a.Poprzezinspek-
cjęgrafustwierdzamy,żezkażdegowierzchołkagrafuistniejeścieżkazorientowana
dodowolnegoinnego(grafjestsilniespójny,p.rozdz.5).
