Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.Przykładyzastosowańgrafów
13
szymcelemjestprzeprawazlewegobrzegurzekinaprawy.Zakładającporządek
elementów:(wilk,koza,kapusta,kupiec),możnapodać16słówbinarnych,np.LPLL
-wilk,kapustaikupiecsąnalewymbrzegurzeki,akozanaprawym.Zwarunków
zadaniawynika,żeniektórespośródtychwektorówsąkombinacjamizabronionymi,
np.zabronionajestkombinacjaLLLP,gdyżoznaczato,żewilk,kozaikapustasąna
tymsamym(lewym)brzegurzeki-kozamożezjeśćkapustę,awilkkozę.Podobnie
niedopuszczalnajestkombinacjaPPLL,gdyżwilkikozapozostająnatymsamym
brzegu.Listakombinacjizabronionychobejmujesześćprzypadków:LLLP,PLLP,
PPLL,LPPL,LLPP,PPPL.
Skonstruujmyetykietowanygrafniezorientowanybędącymodelemproblemu.
Wierzchołkiodpowiadajądziesięciudozwolonymkombinacjom,czyliniezabronio-
nympołożeniomwszystkichobiektówwdanejchwiliwzględemrzeki.Sąto:LLLL,
PLLL,PPLP,LPPP,LPLL,LPLP,LLPL,PLPL,PLPP,PPPP.Krawędźwgrafiewystę-
puje,kiedyzgodniezwarunkamizadaniadopuszczalnejestprzejścieodjednejkom-
binacjidodrugiej.Tabela1.3pokazuje,zaznaczonesymbolemn1”,przejściemiędzy
takimikombinacjami.Zwarunkówzadaniawynika,żeelementtablicyjestrównyn1”
wtedy,gdynastępujezmiananaostatniejpozycjiwektora(kupieczawszemusisię
znajdowaćwłódce),anapierwszychtrzechpozycjachwektoramożenastąpićzmiana
naniewięcejniżjednejpozycji(ograniczeniepojemnościłódkidokupcaijednego
zpozostałychobiektów),np.dozwolonejestprzejścieodkombinacjiPPLPdoPLLL
(iviceversa),gdyżoznacza,żenadrugibrzegrzekiprzeprawiasiękupiecikoza.
Tabela1.3jestprzykłademtzw.macierzysąsiedztwagrafu(p.rozdz.9).
Grafodpowiadającytabeli1.3jestprzedstawionynarys.1.11.Jesttografważony,
gdyżzkażdąkrawędziązwiązanajestwagarównakosztowiprzejściazjednego
wierzchołkadodrugiego-kosztowiprzeprawyprzezrzekę.
Tabela1.3.Dopuszczalnezmianystanówdoproblemu1.6
LLLL
PPLP
LPPP
PLPL
PLPP
LPLP
LLPL
LPLL
PLLL
PPPP
LLLL
0
0
0
0
0
1
0
0
0
0
PLLL
0
0
1
0
0
0
0
0
1
0
PPLP
0
1
0
0
1
0
0
0
0
0
LPPP
0
0
0
0
1
0
1
0
0
0
LPLL
0
0
1
0
0
1
1
0
0
0
LPLP
0
0
0
1
1
0
0
0
0
0
LLPL
0
0
0
1
0
0
0
0
1
0
PLPL
0
0
0
0
0
0
0
0
1
1
PLPP
0
1
0
0
0
0
1
1
0
0
PPPP
0
0
0
0
0
0
0
1
0
0
