Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.6.Zadania
33
c)Musibyćspełnionywarunek:n
k=(k+1)n-2q;0.Dlategozestawudanych
otrzymujemyn
k=-1itakiegografuniedasięskonstruować.
Zadanie2.5
Podaćprzykładygrafówzwyczajnychomożliwienajmniejszejliczbiewierzchołków
takich,że
a)
d)
;
;
e)
b)
;
c)
;
Rozwiązanie
Każdązrówności(a)-(e)możnaprzedstawićjako:
Wykorzystującrówność(2.1),możemynapisać:
2(n+k)=2qÞq=n+k.
a)k=-1Þq=0.
Jesttografniezawierającyżadnejkrawędzi.Minimalnaliczbawierzchołków:
.
b)k=0Þq=n.
Liczbakrawędziiliczbawierzchołkówsąidentyczne-grafjestcyklem.Mini-
malnaliczbawierzchołkówn=3.
c)k=1Þq=n+1.
Liczbakrawędzijestojedenwiększaodliczbywierzchołków-grafjestcyklem
zjednąkrawędziąnprzekątną”.Minimalnaliczbawierzchołkówton=4.
d)k=2Þq=n+2.
MinimalnymgrafemspełniającympowyższywarunekjestgrafK
4.
e)k=3Þq=n+3.
Dlan=5otrzymujemyq=8.Mamy:q(K
4)=6,q(K
5)=10.Stądrozwiązanie
otrzymamy,usuwającdwiekrawędziezK
5.
Grafyzwyczajneonajmniejszejliczbiewierzchołkówiliczbiekrawędzipoda-
nychwrozwiązaniach(a)-(e)sąprzedstawionenarys.2.11.
