Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
18
1.Defnicjagrafuiprzykładyzastosowań
Rys.1.15.KostkiQ
ldlal=1,2,3
ściąwykrywaniabłędupojedynczegobitu.Przykłademtakiegowyborusąsłowakodo-
we000,011,101,110.Jeżeliwskutekbłęduodbierzemynp.słowokodowe001,tobę-
dziemypewni,żeniejesttosłowoznaszegokodu.Zauważmy,żewrozpatrywanym
przykładziejakosłowakodowewybraliśmyzgrafutewierzchołki,któreniesąpołączo-
nekrawędzią(jesttotzw.niezależnyzbiórwierzchołków-p.rozdz.16).Omawiany
przykładmożnarozszerzyćnasłowabinarneowiększejliczbiebitówróżniącesięna
więcejniżjednejpozycjiiwtedynaszemożliwościwykrywaniaikorygowaniabłędów
sięzwiększą.Cenąjestwzględnaredukcjaliczbyważnychsłówkodowych.
Problem1.11.Preferencjerynkowekonsumentów–turnieje
Wbadaniachpreferencjirynkowychkonsumentówstosujesięmetodęporównywania
parami.Przypuśćmy,żechcemyuszeregowaćszamponydowłosównapodstawieba-
daniarynku.Wybranejgrupieosóbkażdorazowodajemydoporównaniadwaszam-
pony-wygrywającymjesttenszampon,któryuzyskawięcejgłosów.Procedurępo-
wtarzamyażdowyczerpaniawszystkichmożliwychparszamponów.Takątechnikę
nazywamyturniejem.Narysowaćgrafpreferencjikonsumentów.
Rozwiązanie
Grafmodelującybadanierynkowejestgrafemzorientowanymoliczbiewierzchoł-
kówrównejliczbiebadanychszamponówitakiejliczbiekrawędzi,jakliczbapar,
któremożnautworzyćzelementówzbioruolicznościn,tj.
.Dlakażdejpary
wierzchołkówkrawędźjestskierowanaodwierzchołkaoznaczającegoszampon,któ-
ryspotkałsięzwiększymuznaniemrespondentówdowierzchołkaoznaczającego
szamponwybranyprzezmniejsząliczbębadanych.Przykładowygrafpreferencji
konsumentówdlan=6jestpokazanynarys.1.16.
