Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.6.Zadania
31
Rozwiązanie
V={{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}.
E={{1,2},{1,3}},{{1,2},{1,4}},{{1,2},{2,3}},{{1,2},{2,4}},{{1,3},{1,4}},
{{1,3},{2,3}},{{1,3},{3,4}},{{1,4},{2,4}},{{1,4},{3,4}},{{2,3},{2,4}},{{2,3},
{3,4}},{{2,4},{3,4}}.
Rozważanygrafjestpokazanynarys.2.8.Jesttografregularnystopnia4.
Rys.2.;.Grafdwuelementowychpod-
zbiorówzbioru
Zadanie2.2
Ileconajmniejdrógnależyzbudowaćmiędzy
miastami,abymiędzykażdąparą
miastistniałopołączenie(bezpośrednielubpośrednie)?Dla
podaćprzykładco
najmniejczterechrozwiązańominimalnejliczbiedróg.
Zadanie2.3
Narysowaćgrafreprezentującywszystkiedozwoloneruchykonikaszachowegoa)na
szachownicyowymiarach3´3,b)owymiarach4´4(wierzchołkigrafureprezen-
tująpolaszachownicy,akrawędzieruchykonikapomiędzypolami).Podaćrozkład
stopniwierzchołków.
Rozwiązanie
a)Grafjestpokazanynarys.2.9a.Grafmajedenwierzchołekstopniazerowego
iosiemwierzchołkówstopniadrugiego.
b)Grafjestpokazanynarys.2.9b.Grafmaczterywierzchołkistopniadrugiego,
osiemwierzchołkówstopniatrzeciegoiczterywierzchołkistopniaczwartego.
