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?