Z.1. Oblicz rz ˛
ad, rozmiar, krotno´s´c i stopie´n narysowanych poni˙zej grafów. Uwaga: krotno´sc
grafu to maksymalna krotno´s´c kraw˛edzi w grafie.
Z.2. Narysuj 6-wierzchołkowy pseudograf posiadaj ˛
acy 4 wierzchołki stopnia 5 i 2 wierzchołki
stopnia 3. Czy te same własno´sci mo˙ze mie´c:
a) multigraf;
b) pseudograf bez kraw˛edzi wielokrotnych;
c) graf prosty?
Z.3. Wyznacz wszystkie multigrafy, w których ka˙zdy wierzchołek v
∈ V (G) spełnia warunek:
a) deg
(v) = |N(v)|;
b) deg
(v) = |N[v]|;
c) deg
(v) ≤ |N[v]|.
Z.4. Niech k
≥ 0. Ustal, dla jakich warto´sci n istnieje chcia˙z jeden n-wierzchołkowy graf prosty
posiadaj ˛
acy dokładnie:
a) k wierzchołków izolowanych;
b) k wierzchołków wisz ˛
acych.
Z.5. Wyka˙z (np. poprzez odpowiedni rysunek), ˙ze:
a)
a) dla dowolnego parzystego n
≥ 4 istnieje n-wierzchołkowy graf, których wszystkie stopnie
a)b)
wynosz ˛
a 3;
a)
b) dla dowolnego nieparzystego n
≥ 5 istnieje graf o n + 1 wierzchołkach, spo´sród których
a)b)
dokładnie n jest stopnia 3;
a)
c) dla dowolnego n
≥ 5 istnieje graf o n wierzchołkach, których wszystkie stopnie wynosz ˛a 4.
Z.6. Niech G b˛edzie grafem prostym o co najmniej dwóch wierzchołkach. Wyka˙z, ˙ze G zawiera
co najmniej dwa wierzchołki tego samego stopnia. Czy jest to prawd ˛
a dla:
a) pseudografów;
b) multigrafów;
c) pseudografów bez multikraw˛edzi?
Z.7. Które z nast˛epuj ˛
acych ci ˛
agów s ˛
a grafowe?
a)
(5, 5, 4, 4, 3, 2, 2, 1, 1).
b)
(6, 5, 4, 3, 2, 2, 2, 2).
c)
(4, 4, 4, 4, 3, 3).
d)
(7, 6, 5, 4, 4, 3, 2, 1).
e)
(6, 6, 5, 5, 2, 2, 2, 2).
f)
(6, 6, 5, 5, 3, 3, 3, 3).
2
Z.8. Narysuj grafy o nast˛epuj ˛
acych ci ˛
agach stopni:
a)
(4, 3, 2, 2, 1).
b)
(4, 3, 3, 3, 1).
Z.9. Co mo˙zna powiedzie´c o grafie, w którym s ˛
asiedztwa dowolnych dwóch wierzchołków s ˛
a
takie same?
Z.10. Wyka˙z, ˙ze dla dowolnego grafu G
= (V, E) liczba wierzchołków o nieparzystym stopniu
jest parzysta. Czy jest to prawd ˛
a dla pseudografów?
Z.11. Przyjmuj ˛
ac, ˙ze G jest grafem prostym o n wierzchołkach i m kraw˛edziach wyka˙z, ˙ze
m
≤
n
(n−1)
2
. Dla jakich grafów zachodzi równo´s´c?
Z.12. Wyka˙z, ˙ze ci ˛
ag liczbowy d
1
, d
2
, . . . , d
n
jest ci ˛
agiem stopni pewnego pseudografu grafu wt-
edy i tylko wtedy, gdy d
1
≥ d
2
≥ ...d
n
≥ 0 i 2|
∑
n
i
=1
d
i
.
Z.13. Ustal, które z poni˙zszych stwierdze ´n jest prawdziwe.
a) Relacja s ˛
asiedztwa grafu prostego jest relacj ˛
a symetryczn ˛
a.
b) Ci ˛
ag stopni grafu prostego musi by´c ci ˛
agiem rosn ˛
acym.
c) Ci ˛
ag stopni multigrafu mo˙ze by´c ci ˛
agiem rosn ˛
acym.
d) Podgraf indukowany w niepustym grafie jest niepustym grafem.
e) Suma wyrazów ci ˛
agu grafowego musi by´c parzysta.
f) Podgraf indukowany w grafie o
δ
> 0 jest niepustym grafem.
Z.14. Niech M
(G) i A(G) b˛ed ˛
a macierzami incydentcji i s ˛
asiedztwa grafu G
(V, E). Opisz, jak
mo˙zna otrzyma´c:
(a)
a) odpowiednie macierze incydencji grafów G
\ E
0
oraz G
\V
0
, gdzie E
0
⊂ E i V
0
⊂ V ;
(a)
b) odpowiedni ˛
a macierz s ˛
asiedztwa grafu G
\V
0
, gdzie V
0
⊂ V .
Z.15. Narysuj 6-wierzchołkowy multigraf posiadaj ˛
acy 4 wierzchołki stopnia 4 i 2 wierzchołki
stopnia 1. Czy te same własno´sci mo˙ze mie´c:
a) multigraf bez p˛etli;
b) multigraf bez kraw˛edzi wielokrotnych;
c) graf prosty?
Z.16. Niech k
≥ 1 i r ≥ 2. Ustal, dla jakich warto´sci n istnieje n-wierzchołkowy graf prosty
posiadaj ˛
acy dokładnie k wierzchołków stopnia r.
Z.17. Jaka jest maksymalna i minimalna liczba kraw˛edzi n-wierzchołkowym grafie prostym posi-
adaj ˛
acym dokładnie:
a) k wierzchołków izolowanych;
b) k wierzchołków wisz ˛
acych.
Z.18. Co mo˙zna powiedzie´c o grafie G, w którym N
(u)∪N(v) = V (G) dla dowolnej pary ró˙znych
wierzchołków v
, u ∈ V (G) s ˛asiedztwa dowolnych dwóch wierzchołków s ˛a takie same.
Z.19. Dla danej rodziny
X
= {X
1
, . . . , X
n
} rodziny zbiorów graf przeci˛e´c jest to graf, którego
wierzchołki odpowiadaj ˛
a zbiorom X
i
, i
= 1, . . . , n, a dwa wierzchołki X
i
i X
j
s ˛
a s ˛
asiednie, je´sli
X
i
∩ X
j
6=
/0
. Wyka˙z, ˙ze dowolny graf prosty jest grafem przeci˛e´c dla pewnej rodziny zbiorów.
Z.20. Niech d
i
1
, . . ., d
i
n
b˛edzie ci ˛
agiem stopni n
i
-wierzchołkowego grafu G
i
dla i
= 1, 2. Czy
prawd ˛
a jest, ˙ze
(a)
a) Je˙zeli G
⊆ G
2
, to d
1
j
≤ d
2
j
dla ka˙zdego j
≤ n
1
?
(a)
b) Je˙zeli d
1
j
≤ d
2
j
dla ka˙zdego j
≤ n
1
, to G
⊆ G
2
?
3
Z.21. Narysuj wszystkie grafy ze zbiorem wierzchołków V
= {a,b,c}. Które z nich s ˛a izomor-
ficzne? Nast˛epnie narysuj wszystkie nieizomorficzne grafy o czterech wierzchołkach.
Z.22. Narysuj dwa najmniejsze (w sensie liczby wierzchołków i kraw˛edzi) nieizomorficzne grafy
o takiej samej liczbie wierzchołków i kraw˛edzi.
Z.23. Które z grafów z (Z.1) s ˛
a izmoroficzne?
Z.24. Wyka˙z, ˙ze poni˙zsze grafy nie s ˛
a izomorficzne.
Z.25. Ustal, które z poni˙zszych stwierdze ´n jest prawdziwe.
a) Grafy izomorficzne maj ˛
a identyczn ˛
a liczb˛e kraw˛edzi i wierzchołków.
b) Grafy izomorficzne maj ˛
a identyczn ˛
a liczb˛e wierzchołków wisz ˛
acych.
c) Grafy o identycznej liczbie kraw˛edzi, wierzchołków i wierzchołków wisz ˛
acych s ˛
a izomor-
c)
ficzne.
d) Ci ˛
agi stopni grafów izomorficznych s ˛
a identyczne.
e) Grafy o identycznych ci ˛
agach stopni s ˛
a izmorficzne.
f) Grafy o identycznej liczbie kraw˛edzi, wierzchołków, wierzchołków wisz ˛
acych i ci ˛
agach
f)
stopni s ˛
a izomorficzne.
Z.26. Wyka˙z, ˙ze poni˙zsze grafy s ˛
a izomorficzne.
Z.27. Które z poni˙zszych grafów (b)-(c) nie s ˛
a izomorficzne z grafem (a)? Uzasadnij odpowied´z.
Z.28. Istniej ˛
a tylko dwa nieizomorficzne grafy o ci ˛
agu stopni
(3, 3, 3, 3, 3, 3, 6). Wska˙z je.
Z.29. Wyznacz wszystkie takie grafy G, ˙ze:
a) G
\U
1
∼
= G
\U
2
dla ka˙zdej pary równolicznych zbiorów U
1
,U
2
⊆ V (G).
b) G
\ F
1
∼
= G
\ F
2
dla ka˙zdej pary równolicznych zbiorów F
1
, F
2
⊆ E(G).
Z.30. Udowodnij, ˙ze izomorfizm grafów jest relacj ˛
a równowa˙zno´sci.
Z.31. W narysowanych poni˙zej grafach zaznacz wierzchołki tworz ˛
ace:
a) najliczniejsz ˛
a klik˛e;
b) najliczniejszy zbiór niezale˙zny;
c) maksymalny (ale nie najliczniejszy) zbiór niezale˙zny.
4
Z.32. Narysuj graf kraw˛edziowy dla narysowanych poni˙zej grafów.
Z.33. Ustal, które z narysowanych powy˙zej grafów s ˛
a grafami:
a) dwudzielnymi;
b) pełnymi dwudzielnymi;
c) trójdzielnymi;
d) pełnymi trójdzielnymi;
e) kraw˛edziowymi;
f) samodopełniaj ˛
acymi si˛e.
Z.34. Oblicz stopie ´n, krotno´s´c, rz ˛
ad i rozmiar dla nast˛epuj ˛
acych grafów:
a) L
(K
n
), n > 1;
b) L
(Q
k
);
c) L
(P
n
), n > 1;
d) L
(K
r
,s
).
Z.35. Niech r
1
, r
2
, . . . , r
k
b˛edzie sko´nczonym ci ˛
agiem liczb naturalnych. Ile kraw˛edzi ma graf
K
r
1
,r
2
,...,r
k
?
Z.36. Niech n b˛edzie liczb ˛
a naturaln ˛
a, a m nieujemn ˛
a liczb ˛
a całkowit ˛
a. Wyznacz stopie ´n n-
wierzchołkowego grafu regularnego o m kraw˛edziach.
Z.37. Dla jakich liczb n istnieje chocia˙z jeden n-wierzchołkowy graf:
a) 1-regularny;
b) 2-regularny.
Z.38. Niech n b˛edzie liczb ˛
a naturaln ˛
a. Wyka˙z, ˙ze n-wierzchołkowy graf dwudzielny nie mo˙ze
posiada´c wi˛ecej ni˙z
1
4
n
2
kraw˛edzi.
Z.39. Ustal, które z poni˙zszych stwierdze ´n s ˛
a prawdziwe.
a) grafy regularne o identycznej liczbie wierzchołków i kraw˛edzi s ˛
a izomorficzne;
b) grafy dwudzielne o identycznych ci ˛
agach stopni s ˛
a izomorficzne;
c) grafy dwudzielne pełne o identycznej liczbie wierzchołków i kraw˛edzi s ˛
a izomorficzne;
d) grafy dwudzielne pełne o identycznych ci ˛
agach stopni s ˛
a izomorficzne.
Z.40. Wyka˙z, ˙ze nie istnieje taki 6-wierzchołkowy graf G, ˙ze G i G nie zawieraj ˛
a trójk ˛
atów. Czy
istnieje 5-wierzchołkowy graf o tej własno´sci?
Z.41. Niech k b˛edzie liczb ˛
a naturaln ˛
a. Wyka˙z, ˙ze je´sli graf posiada 2k wierzchołków i nie zaw-
iera trójk ˛
atów, to ma co najwy˙zej k
2
kraw˛edzi.
Z.42. Narysuj wszystkie 4- i 5-wierzchołkowe grafy samodopełniaj ˛
ace. Które z nich s ˛
a dwudzielne?
Z.43. Wyka˙z, ˙ze nie istnieje graf G taki, ˙ze graf kraw˛edziowy L
(G) jest izomorficzny do grafu
K
1
,q
, q
≥ 3.
Z.44. Wyznacz liczb˛e kraw˛edzi w grafie L
(G) w zale˙zno´sci od liczby wierzchołków i ich stopni
5
w grafie G.
Z.45. Sprawd´z, które z poni˙zszych implikacji s ˛
a prawdziwe.
a) je˙zeli G jest grafem dwudzielnym, to L
(G) jest grafem dwudzielnym;
b) je˙zeli L
(G) jest grafem dwudzielnym, to G jest grafem dwudzielnym;
c) je˙zeli G jest grafem regularnym, to L
(G) jest grafem regularnym;
d) je˙zeli L
(G) jest grafem regularnym, to G jest grafem regularnym.
Z.46. Wyka˙z, ˙ze dla dowolnego grafu 1
≤
α
(G) ≤ |V | −
δ
(G) oraz
α
(G) +
ω
(G) ≤ |V | + 1.
Z.47. Wyznacz
α
(K
r
,s
) i
α
(Q
k
).
Z.48. Czy istnieje dwudzielny graf G, dla którego
δ
(G) +
∆
(G) > |V |?
Z.49. Niech n
> 1 b˛edzie liczb ˛
a naturaln ˛
a. Znajd´z wszystkie n-wierzchołkowe grafy, w których
ka˙zdy
(n − 1)-wierzchołkowy podgraf indukowany jest grafem regularnym.
Z.50. Wyka˙z, ˙ze:
(a)
a) w niepustym regularnym grafie dwudzielnym partycje wierzchołków s ˛
a równoliczne;
(a)
b) je´sli G jest grafem dwudzielnym r-regularnym, to r
≤ |V (G)|/2.
Z.51. Wyznacz liczb˛e wierzchołków i kraw˛edzi grafu kraw˛edziowego L
(G), gdzie G jest grafem
o ci ˛
agu stopnie d
1
, . . . , d
n
.
Z.52. Skonstruuj tak ˛
a par˛e nieizomorficznych grafów G
1
, G
2
, ˙ze ich grafy kraw˛edziowe s ˛
a
izomorficzne.
Z.53. Skonstruuj taki ci ˛
ag grafów prostych
(G
n
)
n
∈N
, ˙ze n
(G
n
) = n dla ka˙zdej liczby naturalnej n
oraz
a) grafy L
(G
n
), G
n
s ˛
a izomorficzne dla n
≥ 3;
b) grafy L
(G
n
), G
n
−1
s ˛
a izomorficzne dla n
≥ 2.
Z.54. Wyka˙z, ˙ze ka˙zdy n-wierzchołkowy graf kubiczny zawiera podgraf dwudzielny posiadaj ˛
acy
co najmniej n kraw˛edzi.
Z.55. Niech k b˛edzie liczb ˛
a naturaln ˛
a. Wyka˙z, ˙ze je´sli graf posiada 2k
+ 1 wierzchołków i nie
zawiera trójk ˛
atów, to ma co najwy˙zej k
2
+ k kraw˛edzi.
Z.56. Niech G b˛edzie grafem dwudzielnym. Wyka˙z, ˙ze wierzchołki grafu G mo˙zna tak przenu-
merowa´c, aby jego macierz s ˛
asiedztwa miała posta´c
0
A
12
A
21
0
gdzie A
21
= A
T
12
.
D.57. Niech G b˛edzie grafem prostym rz˛edu 9 i załó˙zmy, ˙ze suma stopni jego wierzchołków
wynosi przynajmniej 27. Czy prawd ˛
a jest, ˙ze G posiada wierzchołek stopnia przynajmniej 4?
D.58. Niech G b˛edzie grafem prostym rozmiaru 22 i załó˙zmy, ˙ze wszystkie jego wierzchołki s ˛
a
tego samego stopnia. Jakiego rz˛edu mo˙ze by´c G?
D.59. Wyka˙z indukcyjnie, ˙ze ci ˛
ag
(n, n, n − 1,n − 1,...,2,2,1,1) jest ci ˛agiem grafowym.
D.60. Graf prosty, który jest izomorficzny ze swoim dopełnieniem nazywamy samodopełniaj ˛
a-
cym. Wyka˙z, ˙ze:
a) Liczba wierzchołków grafu samodopełniaj ˛
acego wynosi 4k lub 4k
+ 1.
b) ´Scie˙zka P
4
jest jedyn ˛
a samodopełniaj ˛
ac ˛
a si˛e ´scie˙zk ˛
a.
6
c) Wyznacz te warto´sci k, dla których cykl C
k
jest samodopełniaj ˛
acy.
D.61. Graf G jest grafem przedziałowym, je´sli jest grafem przeci˛e´c rodziny
X
, której elementy
s ˛
a odcinkami
[i, j], i ≤ j. Wyka˙z, ˙ze:
a) Indukowany podgraf grafu przedziałowego jest grafem przedziałowym.
b) Podgraf grafu przedziałowego nie musi by´c grafem przedziałowym.
D.62. Załó˙zmy, ˙ze ka˙zda kraw˛ed´z grafu prostego G nale˙zy do przynajmniej dwóch trójk ˛
atów.
Wyka˙z, ˙ze G zawiera koło W
k
(k
≥ 4) jako podgraf.
D.63. Wyka˙z, ˙ze ka˙zdy graf o m kraw˛edziach zawiera podgraf dwudzielny posiadaj ˛
acy co najm-
niej
m
2
kraw˛edzi.
Z.64. W poni˙zszych grafach wyznacz najkrótsz ˛
a spo´sród u
− v ´scie˙zek, które przechodz ˛a przez
wierzchołek w.
Z.65. Wyznacz promie ´n, ´srednic˛e, centrum, tali˛e i obwód dla narysowanych powy˙zej grafów.
Z.66. Narysuj graf prosty G o nast˛epuj ˛
acych własno´sciach lub wyka˙z, ˙ze taki graf nie istnieje.
a) rad
(G) = 2, diam(G) = 3, n = 8;
b) rad
(G) = 3, diam(G) = 3, n = 5;
c) rad
(G) = 1, diam(G) = 3, n = 7;
d) rad
(G) = 2, diam(G) > 2, n = 7.
Z.67. Wyka˙z, ˙ze je˙zeli ka˙zdy z dwóch ró˙znych cykli grafu G zawiera kraw˛ed´z e, to w G istnieje
cykl, który nie zawiera e.
Z.68. Wyka˙z, ˙ze w grafie G dla dowolnych dwóch wierzchołków x
, y, je˙zeli d(x, y) ≥ 2, to ist-
nieje wierzchołek z taki, ˙ze d
(x, z) + d(z, y) = d(x, y).
Z.69. Wyka˙z, ˙ze je˙zeli G jest niepustym grafem spójnym, to diam
(G) ≤ diam(L(G)) + 1.
Z.70. Niech G b˛edzie n-wierzchołkowym grafem spójnym stopnia
∆
> 0. Wyka˙z, ˙ze 1 ≤ diam(G) ≤
n
−
∆
+ 1.
Z.71. Wyka˙z, ˙ze je´sli G jest grafem spójnym, to rad
(G) ≤ diam(G) ≤ 2 · rad(G).
Z.72. Niech n b˛edzie liczb ˛
a naturaln ˛
a. Skonstruuj, o ile jest to mo˙zliwe, taki n-wierzchołkowy
graf G, ˙ze:
a) diam
(G) = rad(G);
b) diam
(G) = 2 · rad(G).
Z.73. Wyka˙z, ˙ze:
a) jeden z grafów G lub G jest spójny;
b) je´sli G nie jest spójny, to diam
(G) ≤ 2;
c) je˙zeli grafy G i G s ˛
a spójne i diam
(G) ≥ 3, to diam(G) ≤ 3.
Z.74. Niech G b˛edzie n-wierzchołkowym grafem spójnym stopnia
∆
. Wyka˙z, ˙ze je˙zeli rad
(G) =
2, to
∆
2
≥ n − 1, a nast˛epnie wyka˙z, ˙ze równo´s´c zachodzi dla grafów regularnych o talii 5. Czy
prawdziwa jest implikacja odwrotna?
7
Z.75. Wyka˙z, ˙ze obwód dowolnego 5-regularnego grafu wynosi przynajmniej 6.
Z.76. Niech G b˛edzie grafem o talii równej r. Wyka˙z, ˙ze rad
(G) ≥ b
r
2
c.
Z.77. Niech G b˛edzie grafem spójnym nie posiadaj ˛
acym indukowanego podgrafu izomorficznego
z P
4
lub C
3
. Wyka˙z, ˙ze G jest grafem dwudzielnym pełnym.
Z.78. Niech G
= (V, E) b˛edzie grafem prostym. Wyka˙z, ˙ze dowolna kraw˛ed´z {x,y} nale˙zy do
przynajmniej deg
(x) + deg(y) − |V | trójk ˛atów (K
3
) w grafie G.
Z.79. Niech G b˛edzie grafem prostym o
δ
(G) ≥ 3. Wyka˙z, ˙ze G posiada cykl parzystej długo´sci.
Z.80. Wyka˙z, ˙ze dla grafu o talii równej przynajmniej 4 zachodzi
|V | ≥
∆
(G) +
δ
(G).
Z.81. Wyka˙z, ˙ze w dowolnym grafie spójnym ka˙zde dwie drogi maksymalnej długo´sci maj ˛
a co
najmniej 1 wspólny wierzchołek.
Z.82. Ustal, czy istnieje taki 3-regularny graf, w którym ka˙zdy cykl jest tej samej długo´sci.
Z.83. Wyka˙z, ˙ze graf k-regularny o talii 4 ma przynajmniej 2k wierzchołków.
Z.84. Niech G b˛edzie n-wierzchołkowym grafem spójnym stopnia
∆
. Wyka˙z, ˙ze rad
(G) = 1,
wtedy i tylko wtedy, gdy
∆
= n − 1 i n > 1.
Z.85. Wyka˙z, ˙ze je´sli G jest grafem spójnym, to ´scie˙zka o realizuj ˛
aca ´srednic˛e diam
(G) zawiera
centrum.
Z.86. Wyka˙z, ˙ze je˙zeli G jest nietrywialnym grafem samodopełniaj ˛
acym, to 1
≤ diam(G) ≤ 3.
Z.87. Niech G b˛edzie n-wierzchołkowym grafem spójnym stopnia
∆
. Wyka˙z, ˙ze je˙zeli
∆
= n −2,
to rad
(G) = 2. Czy prawdziwa jest implikacja odwrotna?
Z.88. Wyka˙z, ˙ze je˙zeli spójny graf G ma ´srednic˛e równ ˛
a co najmniej 4, to graf G jest spójny i
jego ´srednica jest równa 2.
Z.89. Wyka˙z, ˙ze graf G
= (V, E) jest dwudzielny wtedy i tylko wtedy, gdy posiada zbiór nieza-
le˙zny mocy przynajmniej
1
2
|V |.
Z.90. Wyznacz spójno´s´c kraw˛edziow ˛
a i wierzchołkow ˛
a dla grafów z zadania Z.1. Nast˛epnie za-
znacz kraw˛edzie tworz ˛
ace rozci˛ecie oraz wierzchołki tworz ˛
ace separator.
Z.91. Ustal, czy istnieje 6-wierzchołkowy graf, który jest spójny oraz spełnia nast˛epuj ˛
acy warunek:
a)
κ
<
λ
<
δ
;
b)
κ
=
λ
<
δ
;
c)
κ
<
λ
=
δ
;
d)
κ
=
λ
=
δ
;
e)
κ
=
λ
− 1 =
δ
− 2;
f)
κ
=
λ
− 2 =
δ
− 3.
Z.92. Dla ka˙zdej liczby naturalnej k ustal, które grafy z zadania Z.1 posiadaj ˛
a wierzchołkowo
(kraw˛edziowo) k-spójne podgrafy.
Z.93. Wyznacz
κ
(G) i
λ
(G) dla G = P
k
,C
k
, K
k
, K
m
,n
,W
n
+1
(k
, m, n ≥ 3).
Z.94. Wyka˙z, ˙ze n-wierzchołkowy graf mo˙ze posiada´c co najwy˙zej n
− 2 przeguby. Nast˛epnie
wyznacz wszystkie n-wierzchołkowe grafy, które maj ˛
a n
− 2 przeguby.
Z.95. Wyka˙z, ˙ze n-wierzchołkowy graf mo˙ze posiada´c co najwy˙zej n
− 1 mostów. Czy n-
wierzchołkowy graf spójny mo˙ze mie´c dokładnie n
− 2 mosty?
Z.96. Znajd´z wszystkie grafy o nast˛epuj ˛
acej własno´sci:
8
a) usuni˛ecie dowolnego wierzchołka prowadzi do grafu o mniejszej liczbie składowych spójno´sci;
b) usuni˛ecie dowolnego wierzchołka prowadzi do grafu o wi˛ekszej liczbie składowych spójno´sci.
Z.97. Niech v b˛edzie przegubem w grafie G. Wyka˙z, ˙ze G
− v jest spójny.
Z.98. Wyka˙z, ˙ze graf, w którym wszystkie stopnie s ˛
a parzyste nie mo˙ze posiada ´c mostu. Nast˛ep-
nie dla dowolnego k
≥ 1 skonstruuj (2k + 1)-regularny graf posiadaj ˛acy most.
Z.99. Niech G
= (V, E) b˛edzie grafem i niech cc(G) oznacza liczb˛e spójnych komponentów
grafu G.
a) Wyka˙z, ˙ze je´sli e
∈ E, to cc(G) ≤ cc(G − e) ≤ cc(G) + 1.
b) Wyka˙z, ˙ze w ogólno´sci nie jest to prawd ˛
a dla v
∈ V , tzn. niekoniecznie musi zachodzi´c
b)
cc
(G) ≤ cc(G − v) ≤ cc(G) + 1.
c) Wyka˙z, ˙ze je´sli
λ
(G) = k > 0 i je´sli E
0
⊆ E(G) jest podzbiorem k kraw˛edzi, to
c)
cc
(G − E
0
) ≤ 2.
d) Nast˛epnie dla dowolnego k, znajd´z taki k-spójny graf G
(V, E) i podzbiór wierzchołków
d)
V
0
⊆ V , ˙ze cc(G −V
0
) > 2.
Z.100. Wyka˙z, ˙ze je´sli graf G
= (V, E) spełnia warunek |E| >
|V |−1
2
, to G jest spójny.
Z.101. Wyka˙z, ˙ze je˙zeli G
= (V, E) jest kubicznym grafem prostym, to
λ
(G) =
κ
(G)
Z.102. Niech
δ
(G) ≥ k. Wyka˙z, ˙ze je´sli G − v jest k-spójny, v ∈ V (G), to G jest równie˙z.
Z.103. Wyka˙z, ˙ze je´sli G
= (V, E) jest grafem prostym i
δ
(G) > b
|V |
2
c − 1, to G jest grafem
spójnym. Nast˛epnie znajd´z niespójny
(b
|V |
2
c − 1)-regularny graf (|V | jest parzyste).
Z.104. Podaj przykład, ˙ze nie dla ka˙zdej u
− v ´scie˙zki w 2-spójnym grafie istnieje druga nieza-
le˙zna u
− v ´scie˙zka.
Z.105. Wyka˙z, ˙ze je´sli G
= (V, E) jest spójny i wszystkie stopnie jego wierzchołków s ˛
a parzyste,
to dla ka˙zdego v
∈ V cc(G − v) ≤
1
2
deg
(v).
Z.106. Wyka˙z, ˙ze je´sli graf G
= (V, E) jest k-spójny kraw˛edziowo, to |E| ≥
k
|V |
2
.
Z.107. Wyka˙z, ˙ze:
a) Je´sli G
= (V, E) jest grafem prostym i
δ
(G) ≥ |V | − 2, to
κ
(G) =
δ
.
b) Znajd´z graf prosty G
= (V, E) taki, ˙ze
δ
(G) = |V | − 3 i
κ
(G) <
δ
.
Z.108. Wyka˙z, ˙ze:
a) Je´sli G
= (V, E) jest grafem prostym i
δ
(G) ≥
|V |
2
, to
λ
(G) =
δ
.
b) Znajd´z graf prosty G
= (V, E) taki, ˙ze
δ
(G) = b
|V |
2
c − 1 i
λ
(G) <
δ
.
Z.109. Wyka˙z, ˙ze
κ
(Q
k
) = k.
D.110. Wyka˙z, ˙ze w grafie G
= (V, E) liczba marszrut długo´sci k ł ˛
acz ˛
acych wierzchołki v
i
i v
j
równa jest
(i, j)-elementowi w macierzy A
k
, gdzie A jest macierz ˛
a s ˛
asiedztwa grafu G.
D.111. Wyka˙z, ˙ze je˙zeli graf G
= (V, E) posiada przynajmniej |V | + 4 kraw˛edzie, to posiada dwa
rozł ˛
aczne kraw˛edziowo cykle.
D.112. Wyka˙z, ˙ze dowolny 10-wierzchołkowy graf zawiera K
4
lub K
3
. Czy jest to prawd ˛
a dla
grafów o 9 i 8 wierzchołkach?
D.113. Niech G
= (V, E) b˛edzie grafem spójnym nieposiadaj ˛
acym indukowanego podgrafu iz-
moroficznego do P
4
lub C
4
. Wyka˙z, ˙ze
∆
= |V | − 1.
9
D.114. Niech G
= (V, E) b˛edzie grafem spójnym o n wierzchołkach i m kraw˛edziach. Załó˙zmy,
˙ze m
>
1
2
n
√
n
− 1. Wyka˙z, ˙ze G posiada indukowany podgraf C
3
lub C
4
.
D.115. Wyka˙z, ˙ze graf G jest 2-spójny kraw˛edziowo wtedy i tylko wtedy, gdy jego dowolne dwa
wierzchołki poł ˛
aczone s ˛
a przynajmniej dwoma rozł ˛
acznymi kraw˛edziowo ´scie˙zkami.
D.116. Graf spójny, który nie posiada przegubów nazywamy blokiem. Ka˙zdy blok o przynajm-
niej 3 wierzchołkach jest 2-spójny. Blokiem w grafie nazywamy dowolny jego podgraf b˛ed ˛
acy
maksymalnym blokiem. Zauwa˙zmy, ˙ze ka˙zdy graf jest sum ˛
a swoich bloków. Wyka˙z, ˙ze:
a) je´sli G nie posiada parzystych cykli, to ka˙zdy jego blok jest izomorficzny do K
1
, K
2
lub
a)
nieparzystego cyklu.
b) graf spójny nie b˛ed ˛
acy blokiem posiada dwa bloki B
1
, B
2
takie, ˙ze
|V (B
1
) ∩V (B
2
)| = 1.
c) liczba bloków grafie G
= (V, E) wynosi cc(G) +
∑
v
∈V
(b(v) − 1), gdzie b(v) jest liczb ˛a
c)
bloków zawieraj ˛
acych v.
Z.117. Liczb ˛
a cyklomatyczn ˛
a grafu G nazywamy najmniejsz ˛
a liczb˛e kraw˛edzi, które trzeba usun ˛
a ´c
z grafu G, aby powstał graf acykliczny. Liczb˛e cyklomatyczn ˛
a grafu G oznacza ´c b˛edziemy sym-
bolem
γ
. Oblicz liczb˛e cyklomatyczn ˛
a dla grafów z Zadania Z.1.
Z.118. Wyka˙z, ˙ze je´sli w spójnym grafie G ´srednia stopni wierzchołków jest wi˛eksza ni˙z dwa,
wówczas G posiada przynajmniej dwa cykle. Co mo˙zna powiedzie ´c o liczbie cykli, gdy (a) ´sred-
nia stopni wierzchołków jest mniejsza ni˙z dwa; (b) ´srednia stopni wierzchołków jest równa dwa?
Z.119. Wyka˙z, ˙ze ka˙zdy las posiada co najmniej
∆
li´sci. Nast˛epnie wyznacz wszystkie drzewa,
które posiadaj ˛
a dokładnie
∆
li´sci.
Z.120. Wyka˙z, ˙ze je´sli T jest drzewem, w którym wszystkie stopnie wierzchołków s ˛
a nieparzyste,
wówczas liczba kraw˛edzi drzewa T jest równie˙z nieparzysta.
Z.121. Niech d
1
≥ d
2
≥ ... ≥ d
n
b˛edzie ci ˛
agiem liczb naturalnych. Wyka˙z, ˙ze je´sli
∑
n
i
=1
d
i
=
2n
− 2, to istnieje drzewo G, dla którego (d
i
)
n
i
=1
jest ci ˛
agiem stopni.
Z.122. Wierzchołek v drzewa zwany jest rozgał˛eziaj ˛
acym, je´sli deg
(v) ≥ 3. Wyznacz liczb˛e li´sci
w drzewie w zale˙zno´sci od stopni wierzchołków rozgał˛eziaj ˛
acych.
Z.123. Wyznacz liczb˛e li´sci w n-wierzchołkowym drzewie, w którym wierzchołki nie b˛ed ˛
ace
li´s´cmi s ˛
a tego samego stopnia.
Z.124. Niech k
> 1 b˛edzie liczb ˛
a naturaln ˛
a. Wyka˙z, ˙ze ka˙zde niepuste n-wierzchołkowe drzewo
posiada co najmniej n
−
n
−2
k
−1
wierzchołków stopnia mniejszego ni˙z k.
Z.125. Wyka˙z, ˙ze je˙zeli G jest niepustym drzewem posiadaj ˛
acym k li´sci, to diam
(G) >
2n
−4
k
.
Z.126. Wyka˙z, ˙ze je˙zeli G jest drzewem, to rad
= b diam
2
c lub rad = ddiam
2
e.
Z.127. Wyka˙z, ˙ze dowolne n-wierzchołkowe drzewo o ´srednicy przynajmniej 2k
− 3 ma przyna-
jmniej n
− k ró˙znych ´scie˙zek długo´sci k.
Z.128. Niech T b˛edzie drzewem o k
+ 1 wierzchołkach. Wyka˙z, ˙ze w dowolnym grafie prostym
o
δ
≥ k istnieje podgraf izomorficzny do T .
10
Z.129. Zastosuj algorym Jordana do znalezienia centrum w poni˙zszym drzewie T .
Z.130. Zastosuj algorytm DFS do wyznaczenia normalnego drzewa spinaj ˛
acego: (a) o korzeniu
w wierzchołku x; (b) o korzeniu w wierzchołku w y.
Z.131. Zastosuj algorym Kruskala i Prima do wyznaczenia minimalnego drzewa spinaj ˛
acego w
poni˙zszych grafach.
Z.132. Zastosuj algorym Dijkstry do wyznaczenia najkrótszej s
−t ´scie˙zki w poni˙zszych grafach.
Z.133. W drzewie T ´srednia stopni wierzchołków jest równa 1
.99. Ile kraw˛edzi ma T ?
Z.134. Niech ci ˛
ag stopni w drzewie wynosi 5
, 4, 3, 2, 1, . . ., 1. Ile li´sci ma drzewo?
Z.135. Niech n
> 2 b˛edzie liczb ˛
a naturaln ˛
a. Wyznacz wszystkie n-wierzchołkowe grafy, których
ka˙zdy
(n − 1)-wierzchołkowy podgraf indukowany jest drzewem.
11
Z.136. Niech G b˛edzie grafem spójnym. Co mo˙zna powiedzie ´c o:
a) kraw˛edzi grafu G nale˙z ˛
acej do ka˙zdego drzewa spinaj ˛
acego;
b) kraw˛edzi grafu G nie nale˙z ˛
acej do ˙zadnego drzewa spinaj ˛
acego?
Z.137. Załó˙zmy, ˙ze n-wierzchołkowe drzewo
(n ≥ 2) nie posiada wierzchołków stopnia dwa i
ma dokładnie k li´sci. Wyka˙z, ˙ze k
≥ (n + 2)/2. Dla jakich drzew zachodzi równo´s´c?