Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
14
1.Defnicjagrafuiprzykładyzastosowań
Rys.1.11.Grafdozagadkiowilku,kozieikapuście
NaszymcelemjestprzejścieodstanuLLLLdostanuPPPP,minimalizująckoszty
przeprawy(p.rozdz.5-poszukiwanienajtańszejścieżki).Jakwidaćnarys.1.11,są
dwarozwiązaniazagadkioidentycznymkoszcie:15+10+11+15+18+10+15
=94.
Dlagórnejścieżkiharmonogramprzewozówjestnastępujący:
Naprawybrzegprzepływająkupiecikoza.Nalewympozostająwilkikapusta.
Koszt-15.
Kupiecprzeprawiasięnalewybrzeg.Koszt-10.
Kupiecprzewozikapustęnaprawybrzeg.Naprawymbrzegusąkoza,kapusta
ikupiec.Koszt-11.
Kupiecwracanalewybrzegzabierająckozę.Koszt-15.
Kupiecprzewozinaprawybrzegwilka.Koszt-18.Naprawymbrzegusą:wilk,
kapusta,kupiec.
Kupiecsamotniewracanalewybrzeg.Koszt-10.Nalewymbrzegusą:koza
ikupiec,anaprawymwilkikapusta.
Kupiecprzewozikozęnaprawybrzeg.Koszt-15.Naprawymbrzeguznajdują
sięwszyscypasażerowie,cokończyprzeprawęprzezrzekę.
Harmonogramprzewozówjestdośćskomplikowany.Rozwiązanietejzagadki
dobrzeilustruje,jakteoriagrafówpomagabudowaćmodeleskomplikowanychpro-
blemówkombinatorycznychidostarczanarzędzidoichrozwiązywania.
Problem1.7.Rozkładsesjiegzaminacyjnej
Należyprzygotowaćrozkładsesjiegzaminacyjnejdlaośmiuprzedmiotów(oznaczo-
nychnumerami{1,2,…,8}).Egzaminzdwóchprzedmiotówniemożesięodbywać
wtymsamymterminie,jeżelichociażjedenstudentuczęszczanaobydwaprzedmio-
ty.Wtabeli1.4pokazanokonfliktyegzaminacyjne,tzn.paryegzaminów,którenie
mogąodbywaćsięwtymsamymterminie.
