Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
12
1.Defnicjagrafuiprzykładyzastosowań
liczbykolorówwierzchołkomgrafutak,abykażdedwawierzchołkipołączonekra-
wędziąmiałyróżnekolory.Zauważmy,żewierzchołkikażdejzpar{v
1,v
4},{v
2,v
5},
oraz{v
3,v
6}mogąbyćpokolorowanetymsamymkolorem.Problemwymagawięc
3szczelinczasowychzprzydziałemstacjidoszczelinpokazanymnarys.1.10c.
Rys.1.10.a)Grafsieciradiowej;b)grafkonfliktówradiowych;c)przydziałszczelinczaso-
wych
Przykładsiecijestnatyleprosty,żemożebyćrozwiązanymetodąprzeglądugra-
fu.Bardziejzaawansowanerozważaniadotyczącekolorowaniagrafówmożnazna-
leźćwrozdziale16.
Problem1.6.Zagadkaowilku,kozieikapuście
Tenprzykładjestrozszerzonąwersjąznanejzagadkiowilku,kozieikapuście.
Pewienkupiecszedłnatargsprzedaćkozęikapustę.Dlaochronyzabrałzesobą
oswojonegowilka.Wpewnymmomenciecałaczwórka(kupiec,wilk,kozaikapusta)
dotarłanadrzekę.Przybrzegustałałódka.Byłaonatakmała,żenarazmógłsiętam
zmieścićtylkokupiecijednozwierzęalbokapusta.Kupiecwiedział,żepozostawiony
bezopiekiwilknajpewniejpożrekozę,którazkoleichętniezjadłabycałąkapustę.
Dodatkowokażdaprzeprawaprzezrzekęwymagauiszczeniaopłaty.Opłatywy-
noszą:c
w=8(wilk),c
k=5(koza),c
p=1(kapusta),c
u=1(kupiec).Przykażdejprze-
prawiewłódcemusibyćkupiec.Jakpowinienpostąpićkupiec,abybezpiecznieprze-
wieźćwilka,kozęikapustęnadrugibrzeg,minimalizującprzytymkosztprzeprawy?
Rozwiązanie
Mamyczteryobiekty:wilk,koza,kapustaikupiec.Każdyzobiektówmożeprzeby-
waćwdanejchwilinalewymbrzegurzeki-Llubprawym-P.Przyjmujemy,żena-
