Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.2.Przykładyzastosowańgrafów
15
a)Przedstawićreprezentacjęproblemuwpostacimodelugrafowego.
b)Jakajestminimalnaliczbaterminówpotrzebnychdoprzeprowadzeniawszyst-
kichegzaminów?
Tabela1.4.Sesjaegzaminacyjna
1
2
3
4
5
6
7
8
X
X
1
X
X
X
X
X
X
2
X
3
X
X
X
4
X
X
X
X
X
X
X
X
5
X
X
X
6
7
X
X
X
X
X
8
Rozwiązanie
Wmodelugrafowymegzaminysąreprezentowaneprzezwierzchołki.Krawędźłączy
dwawierzchołkiodpowiadająceegzaminom,któreniemogąsięodbywaćwtymsa-
mymterminie.Graftenjestpokazanynarys.1.12.
Rozwiązaniezadaniapoleganapodzialezbioruwierzchołkówgrafunamożliwie
najmniejsząliczbępodzbiorów,takichżeelementamipodzbiorusąwierzchołkiniepo-
łączonewgrafiekrawędzią.Rozwiązanietegoproblemumożnasprowadzićdotzw.
zbiorówniezależnych(p.rozdz.15)lubkolorowaniawierzchołkówgrafu(p.rozdz.16).
Rys.1.12.Grafsesjiegzaminacyjnej
