KOMBINATORYKA

OFICJALNA ĝCIĄGAWKA z MATEMATYKI DYSKRETNEJ cz. 1

relacja równowaĪnoĞci jest zwrotna, przechodnia i symetryczna; relacja porządku jest zwrotna, przechodnia i antysymetryczna;

dla |X| = n :

2

2

n

= liczba wszystkich relacji binarnych;

¦

=

¿

¾

½

¯

®

­

=

n

k

n

k

n

B

0

= liczba wszystkich relacji równowaĪnoĞci w X

relacji równowaĪnoĞci E w zbiorze X wzajemnie jednoznacznie odpowiada podział zbioru X na bloki X|E

=

{ a|E : a

∈

X };

a|E

=

{ b

∈

X : aEb } - klasa abstrakcji elementu a ;

(X,

%

) – zbiór uporządkowany: x, y

∈

X są porównywalne, jeĞli x

%

y lub y

%

x ; x

%

y

⇔

x

%

y

∧

x

≠

y ;

dla s, t

∈

X zachodzi s

%

t i nie istnieje taki element u

∈

X , Īe s

%

u i u

%

t , to s jest bezpoĞrednim poprzednikiem t,

a t – bezpoĞrednim nastĊpnikiem s ;
x

o

∈

X jest elementem maksymalnym w (X,

%

), jeĞli w zbiorze X nie istnieje element x

≠

x

o

, dla którego x

o

%

x ;

x

o

∈

X jest elementem minimalnym w (X,

%

), jeĞli w zbiorze X nie istnieje element x

≠

x

o

, dla którego x

%

x

o

;

x

o

∈

X jest elementem najwiĊkszym w (X,

%

), jeĞli dla kaĪdego x

∈

X zachodzi zaleĪnoĞü x

%

x

o

;

x

o

∈

X jest elementem najmniejszym w (X,

%

), jeĞli dla kaĪdego x

∈

X zachodzi zaleĪnoĞü x

o

%

x ;

x

o

∈

X jest ograniczeniem dolnym zbioru A

⊆

X , jeĞli dla kaĪdego x

∈

A zachodzi zaleĪnoĞü x

o

%

x ;

x

o

∈

X jest ograniczeniem górnym zbioru A

⊆

X , jeĞli dla kaĪdego x

∈

A zachodzi zaleĪnoĞü x

%

x

o

;

sup A – kres górny zbioru A = element najmniejszy w zbiorze ograniczeĔ górnych zbioru A (jeĞli istnieje) ;
inf A – kresem dolnym zbioru A = element najwiĊkszy w zbiorze ograniczeĔ dolnych zbioru A (jeĞli istnieje) ;
podzbiór L

⊆

X , w którym kaĪde dwa elementy x, y

∈

L są porównywalne = łaĔcuch w (X,

%

) ;

podzbiór A

⊆

X , w którym Īadne dwa róĪne elementy x, y

∈

L nie są porównywalne = antyłaĔcuch w (X,

%

) ;

maksymalna licznoĞü antyłaĔcucha jest równa minimalnej liczbie łaĔcuchów pokrywających zbiór X, a maksymalna licznoĞü łaĔcucha
jest równa minimalnej liczbie antyłaĔcuchów pokrywających zbiór X ;
funkcja f : X

→

Y jest relacją binarną f

⊆

X

×

Y taką, Īe dla kaĪdego x

∈

X istnieje dokładnie jedna para postaci (x, y

=

f (x))

∈

f ;

dla | X |

=

n i | Y |

=

m: | Fun(X, Y) |

=

m

n

, | Inj(X, Y) |

=

m

n

(dla n

≤

m ), | Sur(X, Y) |

=

¿

¾

½

¯

®

­

⋅

=

m

n

m

s

m

n

!

,

, | Bij(X, Y) |

=

n

n

=

n! ,

liczba rozmieszczeĔ uporządkowanych = m

n

; Bij(X, Y)

≠ ∅

Ÿ| X |

=

| Y |

;

jeĪeli zachodzi | X | > r

⋅

| Y | dla r > 0 , to dla f

∈

Fun(X, Y) warunek | f

−

1

({y}) | > r jest spełniony dla co najmniej jednego y

∈

Y ;

permutacja zbioru X = bijekcja p : X

→

X ; | Bij(X, X) |

=

n! ;

typ permutacji

n

n

λλλλ

λλλλ

λλλλ

...

2

1

2

1

, gdzie

λ

i

oznacza liczbĊ cykli o długoĞci i ;

inwersją permutacji p

∈

S

n

= para (p(i), p( j)), gdzie p(i)

>

p( j) dla i

<

j

≤

n; I( p) = liczbĊ inwersji;

)

(

)

(

)

sgn(

p

I

p

1

−

=

;

permutacji jest typu

n

n

λλλλ

λλλλ

λλλλ

...

2

1

2

1

, to jej znak

¬

¼

¦

−

=

=

2

1

2

1

n

j

j

f

λλλλ

)

(

)

sgn(

; znak cyklu o długoĞci k jest równy (

−

1)

k

−

1

;

sgn( p s)

=

sgn( p)

⋅

sgn(s); transpozycja = cykl o długoĞci 2; transpozycja sąsiednia = [i, i

+

1] ;

i – niezmiennik permutacji, jeĞli p(i)

=

i ; Inv(p) = liczba niezmienników; nieporządek, gdy Inv(p)

=

0; | D

n

|

=

¦

=

−

n

i

i

i

n

0

1

!

)

(

!

;

|

(X) |

=

2

n

; | { Y

∈

(X) : | Y |

=

k } |

=

k

k

n

n

n

k

n

k

n

k

n

k

n

k

⋅

⋅

⋅

+

−

−

=

−

=

=

¸¸

¹

·

¨¨

©

§

...

)

(

...

)

(

)!

(

!

!

!

2

1

1

1

;

¸¸

¹

·

¨¨

©

§

−

−

+

¸¸

¹

·

¨¨

©

§

−

=

¸¸

¹

·

¨¨

©

§

1

1

1

k

n

k

n

k

n

;

!

...

!

!

!

...

m

m

k

k

k

n

k

k

k

n

⋅

⋅

⋅

=

¸¸

¹

·

¨¨

©

§

2

1

2

1

; | A |

=

< k

∗

x

1

, ..., k

∗

x

n

> : liczba podzbiorów k-elementowych =

¸¸

¹

·

¨¨

©

§

−

+

=

k

k

n

k

n

k

1

!

;

rozwiązaĔ równania x

1

+

x

2

+

...

+

x

n

=

k jest

¸¸

¹

·

¨¨

©

§

−

+

=

k

k

n

k

n

k

1

!

; |

Π

k

(X) |

=

¿

¾

½

¯

®

­

k

n

,

¿

¾

½

¯

®

­

k

n

=

¿

¾

½

¯

®

­

−

−

1

1

k

n

+

k

¿

¾

½

¯

®

­

−

k

n 1

, |

Π

(X)|

=

¦

=

¿

¾

½

¯

®

­

=

n

k

n

k

n

B

0



ππππ

ππππ

∈

×

=

A

A

A

E

)

(

; P(n)

=

¦

=

n

k

k

n

P

1

)

,

(

, P(n, k)

=

P(n

−

1, k

−

1)

+

P(n

−

k, k), P(n, k)

=

¦

=

−

k

i

i

k

n

P

0

)

,

(

, P

k

(n)

=

¦

=

k

i

i

n

P

1

)

,

(

;

| A

∪

B |

=

| A |

+

| B |

−

| A

∩

B | , | A

∪

B

∪

C |

=

| A |

+

| B |

+

| C |

−

| A

∩

B |

−

| A

∩

C |

−

| B

∩

C |

+

| A

∩

B

∩

C | ,

¦

¦

⊆

=

−

=

∩

∩

∩

−

=

}

,...,

{

}

,...,

,

{

|

...

|

)

(

n

p

p

p

p

p

p

n

i

i

n

i

i

i

i

A

A

A

A

1

1

1

1

2

1

2

1

1



;

¦

∞

=

=

0

i

i

i

z

a

z

A )

(

- funkcja tworząca dla ciągu (a

i

)

=

(a

0

, a

1

, a

2

, ..., a

i

, ... )

(jedyna Ğciągawka, którą wolno mieü na egzaminie, ale nie wolno jej uĪywaü na kolokwium poprawkowym)

TEORIA GRAFÓW

OFICJALNA ĝCIĄGAWKA z MATEMATYKI DYSKRETNEJ cz. 2

2

)

1

(

2

−

=

¸¸

¹

·

¨¨

©

§

n

n

n

;

2

)!

1

(

−

n

; n

n

−

2

;

E

i

d

V

i

2

)

(

=

¦

∈

;

A

i

d

i

d

V

i

V

i

=

=

¦

¦

∈

+

∈

−

)

(

)

(

; (n

−

1)! ;

d(i) = | V(i) |, gdzie V(i) = { j

∈

V : {i, j}

∈

E }; d

M

(i) = | V

M

(i) |, gdzie V

M

(i) = { j

∈

M : {i, j}

∈

E };

d

+

(i) = | V

+

(i) |, gdzie V

+

(i) = { j

∈

V : (i, j)

∈

A }; d

−

(i) = | V

−

(i) |, gdzie V

−

(i) = { j

∈

V : (j, i)

∈

A };

)

(i

d

M

+

= |

)

(i

V

M

+

|, gdzie

)

(i

V

M

+

= { j

∈

M : (i, j)

∈

A };

)

(i

d

M

−

= |

)

(i

V

M

−

|, gdzie

)

(i

V

M

−

= { j

∈

M : {j, i}

∈

A };

I(G) = [ a

ij

]

i =1, ..., n , j =1, ..., m

, gdzie

¯

®

­

∈

=

przypadku

przeciwnym

w

0

jesli

1

j

ij

e

i

a

;

I(D) = [ a

ij

]

i =1, ..., n , j =1, ..., m

, gdzie

°

¯

°

®

­

=

=

−

=

przypadku

przeciwnym

w

0

)

,

(

jesli

1

)

,

(

jesli

1

k

i

a

i

k

a

a

j

j

ij

;

B(G) = [ b

ij

]

i =1, ..., n , j =1, ..., n

, gdzie

¯

®

­

∈

=

=

przypadku

przeciwnym

w

0

}

,

{

jesli

1

E

j

i

b

b

ji

ij

;

B(D) = [ b

ij

]

i =1, ..., n , j =1, ..., n

, gdzie

¯

®

­

∈

=

przypadku

przeciwnym

w

0

)

,

(

jesli

1

A

j

i

b

ij

;

2

)

1

)(

(

)

(

+

−

−

≤

≤

−

k

n

k

n

m

k

n

; n – m + f = k + 1; m

≤

3n – 6; m

≤

2n – 4;

d(v) + d(w)

≥

n; d(v)

≥

2

n

; m

≥

2

2

)

2

)(

1

(

+

−

−

n

n

;

∀

i <

2

n

: a

i

≤

i Ÿ a

n

−

i

≥

n – i ;

1

2

)

(

)

(

−

≥

+

n

w

d

v

d

;

2

)

(

n

v

d

≥

+

i

2

)

(

n

v

d

≥

−

;

C =

1

e

C

⊗

2

e

C

⊗

...

⊗

k

e

C , gdzie

{

}

k

e

e ...,

,

1

= C \ T ;

κ

(G)

≤

λ

(G);

¦

¦

−

+

∈

∈

−

=

)

(

)

(

)

,

(

)

,

(

)

(

s

V

u

s

V

u

s

u

f

u

s

f

f

W

; P

U

= A

∩

( U

×

( V \ U) ) = { (u, v)

∈

A : u

∈

U, v

∈

V \ U };

f (U, V \ U) =

¦

∈

U

P

v

u

v

u

f

)

,

(

)

,

(

; W(f ) = f (U, V \ U)

−

f (V \ U, U); C(P

U

) =

¦

∈

U

P

v

u

v

u

c

)

,

(

)

,

(

; W(f )

≤

C(P

U

);

α

(G) +

τ

(G) = | V |;

ν

(G) +

ρ

(G) = | V |;

ν

(G)

≤

τ

(G);

α

(G)

≤

ρ

(G);

∀

S

⊆

V

1

: | N(S) |

≥

| S | ;

4

1

2

2

1

)

(

+

+

≤

m

G

χ

;

(jedyna Ğciągawka, którą wolno mieü na egzaminie, ale nie wolno jej uĪywaü na kolokwium poprawkowym)

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 1 / 14

REPETYTORIUM Z KOMBINATORYKI

Relacja binarna

R

⊆

X

×

Y

Relacja binarna w zbiorze X:

R

⊆

X

×

X

MoĪe byü okreĞlona za pomocą:

zdania logicznego

xRy

⇔

¬ ¼ ª º

y

x

=

,

zbioru par uporządkowanych

{(x, y), (x, x), ...},

grafu relacji

tablicy relacji

x

y

z ...

x

1

0

1

y

0

1

0

z

1

1

0

...

Cechy relacji binarnej w zbiorze X:

•

zwrotna,

jeĞli

∀

x

∈

X : xRx

•

przechodnia,

jeĞli

∀

x, y, z

∈

X : ( xRy

∧

yRz ) Ÿ xRz

•

symetryczna,

jeĞli

∀

x, y

∈

X : xRy Ÿ yRx

•

antysymetryczna, jeĞli

∀

x, y

∈

X : ( xRy

∧

yRx ) Ÿ x

=

y

Relacja równowaĪnoĞci jest zwrotna, przechodnia i symetryczna.

Relacja porządku jest zwrotna, przechodnia i antysymetryczna.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 2 / 14

ƒ Dla zbioru skoĔczonego | X |

=

n :

liczba wszystkich relacji binarnych w X wynosi

2

2

n

,

liczba wszystkich zwrotnych relacji w X wynosi

)

(

1

2

−

n

n

,

liczba wszystkich symetrycznych relacji w X wynosi

2

1

2

)

(

+

n

n

,

liczba wszystkich antysymetrycznych relacji w X wynosi

2

1

3

2

)

(

−

⋅

n

n

n

,

liczba wszystkich relacji równowaĪnoĞci w X wynosi B

n

(liczby Bella),

¦

=

¿

¾

½

¯

®

­

=

n

k

n

k

n

B

0

;

i

n

i

n

B

i

n

B

⋅

¸¸

¹

·

¨¨

©

§

=

¦

=

+

0

1

KaĪdej relacji równowaĪnoĞci E w zbiorze X moĪna wzajemnie

jednoznacznie przyporządkowaü podział zbioru X na bloki:

X|E

=

{ a|E : a

∈

X } ,

gdzie pojedynczy blok a|E

=

{ b

∈

X : aEb } nazywany jest

klasą abstrakcji elementu a.

JeĪeli G jest grupą permutacji zbioru X, to szczególna rolĊ odgrywa

relacja indukowana w zbiorze X przez grupĊ G (oznaczana R

G

).

Relacja indukowana R

G

jest relacją równowaĪnoĞci.

KaĪdą z klas abstrakcji relacji indukowanej R

G

nazywamy orbitą

działania grupy G. Symbol o(G) oznacza liczbĊ orbit.

Zbiór orbit działania jest podziałem zbioru X na o(G) bloków.

¦

∈

=

G

p

p

Inv

G

G

o

)

(

)

(

1

,

gdzie Inv(p) jest liczbą niezmienników permutacji p

∈

G.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 3 / 14

Relacja porządku

%

wraz ze zbiorem , w którym została

zdefiniowana tworzy zbiór uporządkowany (X,

%

).

Dwa elementy x, y

∈

X nazywamy porównywalnymi, jeĞli x

%

y

lub y

%

x , w przeciwnym przypadku są one nieporównywalne.

JeĞli kaĪde dwa elementy x, y

∈

X są porównywalne, to parĊ (X,

%

)

nazywamy zbiorem liniowo uporządkowanym.

W zbiorze uporządkowanym (X,

%

) wprowadzamy „ostrą” relacjĊ

x

%

y

⇔

x

%

y

∧

x

≠

y

JeĪeli dla dwóch elementów s, t

∈

X zachodzi s

%

t i nie istnieje taki

element u

∈

X , Īe s

%

u i u

%

t , to s nazywamy bezpoĞrednim

poprzednikiem t, a t – bezpoĞrednim nastĊpnikiem s.

Wygodnym i czytelnym sposobem

przedstawienia zbioru uporządkowanego (X,

%

)

jest tzw. diagram Hassego, na którym łączymy

odcinkami tylko bezpoĞrednie poprzedniki z ich

nastĊpnikami i nastĊpniki umieszczamy

powyĪej poprzedników.

Np.:

100

50

25

70

12

6

3

2

10

5

Element x

o

∈

X nazywamy elementem maksymalnym w zbiorze

czĊĞciowo uporządkowanym (X,

%

), jeĞli w zbiorze X nie istnieje

element x

≠

x

o

, dla którego x

o

%

x .

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 4 / 14

Element x

o

∈

X nazywamy elementem minimalnym w zbiorze

czĊĞciowo uporządkowanym (X,

%

), jeĞli w zbiorze X nie istnieje

element x

≠

x

o

, dla którego x

%

x

o

.

Element x

o

∈

X nazywamy elementem najwiĊkszym w zbiorze

czĊĞciowo uporządkowanym (X,

%

), jeĞli dla kaĪdego x

∈

X zachodzi

zaleĪnoĞü x

%

x

o

.

Element x

o

∈

X nazywamy elementem najmniejszym w zbiorze

czĊĞciowo uporządkowanym (X,

%

), jeĞli dla kaĪdego x

∈

X zachodzi

zaleĪnoĞü x

o

%

x .

W zbiorze czĊĞciowo uporządkowanym istnieje co najwyĪej jeden

element najwiĊkszy i co najwyĪej jeden element najmniejszy.

Przy tym element najwiĊkszy jest elementem maksymalnym, a element

najmniejszy jest elementem minimalnym.

JeĞli (X,

%

) jest zbiorem liniowo uporządkowanym oraz X jest

zbiorem skoĔczonym i niepustym, to w (X,

%

) istnieją elementy

najwiĊkszy i najmniejszy.

Element x

o

∈

X nazywamy ograniczeniem dolnym zbioru A

⊆

X ,

jeĞli dla kaĪdego x

∈

A zachodzi zaleĪnoĞü x

o

%

x .

Element x

o

∈

X nazywamy ograniczeniem górnym zbioru A

⊆

X ,

jeĞli dla kaĪdego x

∈

A zachodzi zaleĪnoĞü x

%

x

o

.

JeĞli zbiór ograniczeĔ górnych zbioru A ma element najmniejszy, to

nazywamy go kresem górnym zbioru A i oznaczamy sup A .

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 5 / 14

JeĞli zbiór ograniczeĔ dolnych zbioru A ma element najwiĊkszy, to

nazywamy go kresem dolnym zbioru A i oznaczamy inf A .

Pokryciem zbioru X nazywamy taką rodzinĊ jego podzbiorów

{ Y

1

, Y

2

, ..., Y

k

} (Y

i

⊆

X), dla której zachodzi X

=

Y

1

∪

Y

2

∪

...

∪

Y

k

.

Mówimy, Īe rodzina { Y

1

, Y

2

, ..., Y

k

} pokrywa zbiór X.

ŁaĔcuchem z zbiorze uporządkowanym (X,

%

) nazywamy taki

podzbiór L

⊆

X , w którym kaĪde dwa elementy x, y

∈

L są

porównywalne, tzn. zawsze zachodzi x

%

y lub y

%

x .

AntyłaĔcuchem z zbiorze uporządkowanym (X,

%

) nazywamy taki

podzbiór A

⊆

X , w którym Īadne dwa róĪne elementy x, y

∈

L nie są

porównywalne, tzn. zawsze zachodzi x

%

y

⇔

x

=

y .

W kaĪdym skoĔczonym zbiorze czĊĞciowo uporządkowanym (X,

%

)

maksymalna licznoĞü antyłaĔcucha jest równa minimalnej liczbie

łaĔcuchów pokrywających zbiór X, a maksymalna licznoĞü łaĔcucha

jest równa minimalnej liczbie antyłaĔcuchów pokrywających zbiór X.

Funkcja

f : X

→

→

→

→

Y

jest relacją binarną f

⊆

X

×

Y taką, Īe dla kaĪdego x

∈

X istnieje

dokładnie jedna para postaci ( x, y

=

f (x) )

∈

f

Funkcja f jest injekcją (funkcją róĪnowartoĞciową, „1

−

1”), jeĞli

∀

x, y

∈

X x

≠

y Ÿ f (x)

≠

f (y)

Funkcja f jest surjekcją (funkcją „na”), jeĞli

∀

y

∈

Y

∃

x

∈

X f (x)

=

y

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 6 / 14

Funkcja f jest bijekcją , jeĞli jest jednoczeĞnie injekcją i surjekcją.

Fun(X, Y) oznacza zbiór wszystkich funkcji z X w Y,

Inj(X, Y) oznacza zbiór wszystkich injekcji z X w Y,

Sur(X, Y) oznacza zbiór wszystkich surjakcji z X na Y,

Bij(X, Y) oznacza zbiór wszystkich bijekcji z X w Y,

Bij(X, Y)

=

Sur(X, Y)

∩

Inj(X, Y)

ƒ Dla zbiorów skoĔczonych | X |

=

n i | Y |

=

m:

| Fun(X, Y) |

=

m

n

| Inj(X, Y) |

=

m

n

(dla n

≤

m )

| Sur(X, Y) |

=

¿

¾

½

¯

®

­

⋅

=

m

n

m

s

m

n

!

,

=

¦

−

=

−

¸¸

¹

·

¨¨

©

§

−

1

0

1

m

i

n

i

i

m

i

m

)

(

)

(

| Bij(X, Y) |

=

n

n

=

n!

Zasada równolicznoĞci pozwala rozstrzygaü o liczbie elementów

jednego zbioru na podstawie liczby elementów drugiego po

skonstruowaniu bijekcji pomiĊdzy tymi zbiorami.

JeĪeli Bij(X, Y)

≠ ∅

, to | X |

=

| Y |

=

n

Rozmieszczeniem uporządkowanym nazywamy wskazanie pewnej

funkcji f : X

→

Y wraz z okreĞleniem uporządkowaĔ we wszystkich

zbiorach f

−

1

({y}) dla y

∈

Y .

Liczba wszystkich rozmieszczeĔ uporządkowanych wynosi m

n

.

Przy zliczaniu funkcji f : X

→

Y stosujemy czĊsto zasadĊ mnoĪenia:

jeĪeli X

=

X

1

∪

X

2

i Y

=

Y

1

∪

Y

2

oraz spełnione są warunki X

1

∩

X

2

= ∅

, f ( X

1

)

⊆

Y

1

i f ( X

2

)

⊆

Y

2

,

to

| Fun(X, Y) |

=

| Fun(X

1

, Y

1

) |

⋅

| Fun(X

2

, Y

2

) | ;

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 7 / 14

jeĪeli ponadto Y

1

∩

Y

2

= ∅

,

to

| Inj(X, Y) |

=

| Inj(X

1

, Y

1

) |

⋅

| Inj(X

2

, Y

2

) | .

JeĪeli na zbiorze X zdefiniowano funkcjĊ f w zbiór Y , to obowiązuje

takĪe zasada szufladkowa:

jeĪeli dla zbiorów X i Y zachodzi | X | > r

⋅

| Y | dla r > 0 , to

dla kaĪdej funkcji f

∈

Fun(X, Y) warunek | f

−

1

({y}) | > r jest spełniony

dla co najmniej jednego y

∈

Y .

Permutacją zbioru X nazywamy bijekcjĊ p : X

→

X

| Bij(X, X) |

=

n!

S

n

oznacza zbiór wszystkich permutacji zbioru {1, 2, ..., n}.

Zbiór S

n

wraz z operacja składania permutacji tworzy grupĊ.

Operacja składania permutacji jest łączna, ale nie jest przemienna.

W zbiorze S

n

istnieje element neutralny operacji składania e

(permutacja identycznoĞciowa) i dla kaĪdego p

∈

S

n

istnieje element

odwrotny p

−

1

∈

S

n

(permutacja odwrotna).

Permutacja p moĪe byü okreĞlona za pomocą:

tablicy

¸¸

¹

·

¨¨

©

§

=

4

1

2

3

5

5

4

3

2

1

p

,

grafu

1

4

5

2

3

.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 8 / 14

KaĪdą permutacjĊ p

∈

S

n

moĪna przedstawiü w postaci złoĪenia

rozłącznych cykli:

p

=

[ 1, 5, 4 ] [ 2, 3 ]

KaĪdą permutacjĊ p

∈

S

n

moĪna scharakteryzowaü przez podanie jej

typu:

n

n

λλλλ

λλλλ

λλλλ

...

2

1

2

1

, gdzie

λλλλ

i

oznacza liczbĊ cykli o długoĞci i .

ParĊ (a

i

, a

j

), gdzie p(i )

=

a

i

i p( j )

=

a

j

dla i

<

j

≤

n, nazywamy

inwersją permutacji p

∈

S

n

, jeĞli a

i

>

a

j

.

I( p) oznacza liczbĊ wszystkich inwersji w permutacji p

∈

S

n

.

Znakiem permutacji p

∈

S

n

nazywamy liczbĊ

)

(

)

(

)

sgn(

p

I

p

1

−

=

.

Dla permutacji typu

n

n

λλλλ

λλλλ

λλλλ

...

2

1

2

1

jej znak

¬

¼

¦

−

=

=

2

1

2

1

n

j

j

f

λλλλ

)

(

)

sgn(

.

Znak cyklu o długoĞci k jest równy (

−

1)

k

−

1

.

Dla permutacji p, s

∈

S

n

zachodzi równoĞü sgn( p s)

=

sgn( p)

⋅

sgn(s).

Transpozycją nazywamy cykl o długoĞci 2.

Transpozycją sąsiednią nazywamy cykl postaci [i, i

+

1].

KaĪdą permutacjĊ p

∈

S

n

moĪna przedstawiü w postaci złoĪenia

I( p) transpozycji sąsiednich, np. p

=

[2, 3] [3, 4] [4, 5] [1, 2].

KaĪda transpozycja ma znak równy –1.

Element i

∈

{1, 2, ..., n} nazywamy niezmiennikiem permutacji

p

∈

S

n

, jeĞli p(i)

=

i.

Inv(p) oznacza liczbĊ niezmienników permutacji p.

Nieporządkiem nazywamy taką permutacjĊ p

∈

S

n

,

dla której Inv(p)

=

0.

D

n

oznacza zbiór wszystkich nieporządków w zbiorze S

n

.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 9 / 14

| D

n

|

=

¦

=

−

n

i

i

i

n

0

1

!

)

(

!

Rodzina podzbiorów zbioru X:

(X)

=

{ Y : Y

⊆

X}

KaĪdy podzbiór Y

∈

(X) moĪe byü jednoznacznie okreĞlony przez

swój wektor charakterystyczny

ξ

( Y )

=

( b

1

, b

2

, ..., b

n

)

∈

{0, 1}

n

według wzoru:

b

x

Y

x

Y

i

i

i

=

∈
∉

­

®

¯

1

0

jeĞli

jeĞli

,

dla X

=

{ x

1

, ..., x

n

}.

|

(X) |

=

2

n

Wektory charakterystyczne są wygodnym narzĊdziem do generowania

wszystkich elementów rodziny (X) .

Podzbiory k-elementowe zbioru X ( | X |

=

n ):

| { Y

∈

(X) : | Y |

=

k } |

=

k

k

n

n

n

k

n

k

n

k

n

k

n

k

⋅

⋅

⋅

+

−

−

=

−

=

=

¸¸

¹

·

¨¨

©

§

...

)

(

...

)

(

)!

(

!

!

!

2

1

1

1

n

k

n

n

k

§
©

¨

·
¹

¸

=

−

§
©

¨

·
¹

¸ ,

n

k

n

k

n

k

§
©

¨

·
¹

¸

=

−

§
©

¨

·
¹

¸

+

−
−

§
©

¨

·
¹

¸

1

1

1

,

n

i

i

n

n

§
©

¨

·
¹

¸

=

=

¦

0

2 ,

n

i

i

n

i

n

n

§
©

¨

·
¹

¸

=

=

−

¦

0

1

2

,

Rozbiciem zbioru X na m podzbiorów o zadanych liczbach

elementów k

1

, k

2

, ..., k

m

nazywamy taką rodzinĊ rozłącznych zbiorów

{ X

1

, X

2

, ..., X

m

}, dla której spełnione są warunki:

m

X

X

X

X

∪

∪

∪

=

...

2

1

,

∅

=

∩

j

i

X

X

dla 1

≤

i

<

j

≤

m i

i

i

k

X

=

.

Liczba wszystkich rozbiü zbioru X wynosi:

!

...

!

!

!

...

m

m

k

k

k

n

k

k

k

n

⋅

⋅

⋅

=

¸¸

¹

·

¨¨

©

§

2

1

2

1

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 10 / 14

Zbiór z powtórzeniami

A

=

< k

1

∗

x

1

, ..., k

n

∗

x

n

>

okreĞlony jest przez podanie wektora krotnoĞci (k

1

, ..., k

n

) dla zbioru

bazowego X

=

{ x

1

, ..., x

n

}.

Liczba elementów w zbiorze z powtórzeniami A wynosi

| A |

=

k

1

+

...

+

k

n

Liczba wszystkich podzbiorów zbioru z powtórzeniami A wynosi

( k

1

+

1)

⋅

( k

2

+

1)

⋅

...

⋅

( k

n

+

1)

Liczba k-elementowych podzbiorów zbioru z powtórzeniami

< k

∗

x

1

, ..., k

∗

x

n

> (szczególny przypadek k

i

=

k) wynosi

¸

¹

·

¨

©

§

−

+

=

k

k

n

k

n

k

1

!

Funkcja tworząca dla ciągu liczb podzbiorów k-elementowych

zbioru z powtórzeniami A ma postaü

A(x)

=

¦

=

A

k

k

k

x

c

0

=

(1

+

x

+

...

+

1

k

x )

⋅

...

⋅

(1

+

x

+

...

+

n

k

x

) ;

c

k

jest liczbą podzbiorów k-elementowych zbioru z powtórzeniami A.

Liczba całkowitych nieujemnych rozwiązaĔ liniowego równania

diofantycznego x

1

+

x

2

+

...

+

x

n

=

k dla całkowitego i nieujemnego

k wynosi

¸¸

¹

·

¨¨

©

§

−

+

=

k

k

n

k

n

k

1

!

Podziałem zbioru X ( | X |

=

n ) na k bloków nazywamy taką

rodzinĊ niepustych zbiorów

π

=

{ A

1

, ..., A

k

} , dla której zachodzi

X

=

A

1

∪

...

∪

A

k

, A

i

∩

A

j

= ∅

dla 1

≤

i

<

j

≤

k oraz A

i

≠ ∅

.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 11 / 14

Π

k

(X) oznacza zbiór wszystkich podziałów zbioru X na k bloków.

Π

(X) oznacza zbiór wszystkich podziałów zbioru X.

|

Π

k

(X) |

=

¿

¾

½

¯

®

­

k

n

(liczby Stirlinga 2 rodzaju)

¿

¾

½

¯

®

­

k

n

=

¿

¾

½

¯

®

­

−

−

1

1

k

n

+

k

¿

¾

½

¯

®

­

−

k

n 1

, dla 0 < k < n

¿

¾

½

¯

®

­

n

n

=

1,

¿

¾

½

¯

®

­

0

n

=

0 dla n

≥

0;

¿

¾

½

¯

®

­

1

n

=

1, dla n > 0

¦

¦

−

=

−

=

⋅

−

−

−

=

−

¸¸

¹

·

¨¨

©

§

−

=

¿

¾

½

¯

®

­

1

0

1

0

1

1

1

m

i

n

i

m

i

n

i

i

i

m

i

m

i

m

i

m

m

m

n

!

)!

(

)

(

)

(

)

(

)

(

!

¦

¦

=

−

=

⋅

¿

¾

½

¯

®

­

⋅

−

=

⋅

¿

¾

½

¯

®

­

=

n

k

k

k

n

n

k

k

n

m

k

n

m

k

n

m

0

0

1)

(

zachodzi dla m, n

∈

|

Π

(X)|

=

¦

=

¿

¾

½

¯

®

­

=

n

k

n

k

n

B

0

(liczby Bella)

i

n

i

n

B

i

n

B

⋅

¸¸

¹

·

¨¨

©

§

=

¦

=

+

0

1

KaĪdemu podziałowi

π

∈ Π

(X) moĪna jednoznacznie przyporząd-

kowaü relacjĊ równowaĪnoĞci E(

π

) w zbiorze X , definiując ją jako



π

π

∈

×

=

A

A

A

E

)

(

tzn. dwa elementy x, y

∈

X są w relacji E(

π

), czyli x E(

π

) y

wtedy i tylko wtedy, kiedy x i y naleĪą do tego samego bloku podziału.

Podziałem liczby n na k składników ( n, k

∈

{ 1, 2, ... } ) nazywamy

taki skoĔczony ciąg całkowity a

1

, a

2

, ..., a

k

, dla którego zachodzi

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 12 / 14

n

=

a

1

+

...

+

a

k

i a

1

≥

a

2

≥

...

≥

a

k

> 0

P(n, k) oznacza liczbĊ podziałów liczby n na k składników.

P(n)

=

¦

=

n

k

k

n

P

1

)

,

(

oznacza liczbĊ wszystkich podziałów liczby n.

P

k

(n) oznacza liczbĊ podziałów liczby n o najwiĊkszym składniku

równym k.

P(n, k)

=

P

k

(n) ,

dla k

≤

n

P(n, k)

=

P(n

−

1, k

−

1)

+

P(n

−

k, k) dla n

≥

k > 0

P(0, 0)

=

P(0)

=

1

P(n, k)

=

¦

=

−

k

i

i

k

n

P

0

)

,

(

i P

k

(n)

=

¦

=

k

i

i

n

P

1

)

,

(

dla n

≥

k > 0

Zasada włączania-wyłączania to sposób wyznaczania liczby

elementów w sumie mnogoĞciowej skoĔczonej liczby zbiorów

(niekoniecznie rozłącznych):

| A

∪

B |

=

| A |

+

| B |

−

| A

∩

B |

| A

∪

B

∪

C |

=

=

| A |

+

| B |

+

| C |

−

| A

∩

B |

−

| A

∩

C |

−

| B

∩

C |

+

| A

∩

B

∩

C |

¦

¦

⊆

=

−

=

∩

∩

∩

−

=

}

,...,

{

}

,...,

,

{

|

...

|

)

(

n

p

p

p

p

p

p

n

i

i

n

i

i

i

i

A

A

A

A

1

1

1

1

2

1

2

1

1



Funkcją tworzącą dla ciągu liczbowego (a

i

)

=

(a

0

, a

1

, a

2

, ..., a

i

, ... )

nazywamy szereg potĊgowy

¦

∞

=

=

0

i

i

i

z

a

z

A )

(

dla zmiennej zespolonej z.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 13 / 14

Funkcje tworzące wybranych ciągów:

Ciąg

Funkcja tworząca

(1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 0, ...),

¸¸

¹

·

¨¨

©

§

=

i

a

i

8

(1

+

z)

8

(0, ..., 0, 1, 0, ...., 0, ... ), a

n

=

1 i a

i

=

0 dla i

≠

n

z

n

(1, 1, ..., 1, ... ), a

i

=

1 dla i

=

0, 1, ...

z

−

1

1

(c

0

, c

1

, c

2

, ..., c

i

, ... ), a

i

=

c

i

dla i

=

0, 1, ...

z

c

⋅

−

1

1

Operacjom na ciągach odpowiadają operacje na funkcjach tworzących:

Operacja na ciągu

Operacja na funkcjach

tworzących

mnoĪenie przez liczbĊ:

(a

i

)

→

(c

⋅

a

i

)

A(z)

→

c

⋅

A(z)

dodawanie ciągów:

(a

i

), (b

i

)

→

(a

i

+

b

i

)

A(z), B(z)

→

A(z)

+

B(z)

przesuniĊcie w prawo o m pozycji:

(a

i

)

→

(0, ..., 0, a

0

, a

1

, a

2

, ..., a

i

, ... )

(a

i

=

0 dla i

=

0, 1, ..., m

−

1)

A(z)

→

z

m

⋅

A(z)

Za pomocą funkcji tworzącej moĪna otrzymaü nierekurencyjny wzór

na kolejny wyraz ciągu Fibonacciego.

Wzór rekurencyjny:

F

i

=

F

i

−

1

+

F

i

−

2

+

i

=

1

dla i

=

0, 1, 2, 3, ... (F

i

=

0 dla i < 0)

Równanie dla funkcji tworzącej:

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 14 / 14

F(z)

=

z

2

⋅

F(z)

+

z

⋅

F(z)

+

z

Funkcja tworząca:

¦

∞

=

=

−

−

=

0

2

1

i

i

i

z

F

z

z

z

z

F

)

(

Wzór na kolejne wyrazy ciągu:

»

»
¼

º

«

«
¬

ª

¸¸

¹

·

¨¨

©

§

−

−

¸¸

¹

·

¨¨

©

§

+

=

i

i

i

F

2

5

1

2

5

1

5

1

dla i

=

0, 1, 2, ...

Za pomocą funkcji tworzącej moĪna rozwiązaü rekurencyjne równanie

dla złoĪonoĞci rekurencyjnego algorytmu dla problemu wieĪ Hanoi.

Wzór rekurencyjny:

T

i

=

2

⋅

T

i

−

1

+

1

−

i

=

0 dla i

=

0, 1, 2, ... (T

i

=

0 dla i < 0)

Równanie dla funkcji tworzącej:

T(z)

=

2 z

⋅

T(z)

+

z

−

1

1

−

1

Funkcja tworząca:

)

)(

(

)

(

z

z

z

z

T

2

1

1

−

−

=

Wzór na zaleĪnoĞü liczby ruchów od liczby krąĪków:

T

i

=

2

i

– 1 dla i

=

0, 1, 2, ...

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 1 / 14

REPETYTORIUM Z GRAFÓW i SIECI

Graf = para uporządkowana dwóch zbiorów

Graf nieskierowany

Graf skierowany

G = (V, E), wierzchołki i krawĊdzie,

E

⊆

{

{i, j} : i

≠

j i i, j

∈

V

};

D = (V, A), wierzchołki i łuki,

A

⊆

V

×

V ;

incydencja, sąsiedztwo, zaleĪnoĞü

d(v)

−

stopieĔ wierzchołka v

d(v)

= 0 −

wierzchołek izolowany,

d(v)

= 1 −

liĞü

d(v) = d

+

(v) + d

−

(v)

−

stopieĔ wierzchołka v :

d

+

(v)

−

stopieĔ wyjĞciowy v ,

d

−

(v)

−

stopieĔ wejĞciowy v

Pochodny graf G(D) = ( V, E

D

) dla grafu skierowanego D = (V, A):

{ i, j }

∈

E

D

⇔

( i, j )

∈

A

∨

( j, i )

∈

A dla i

≠

j

Graf pełny (dla | V | = n):

E =

{

{i, j} : i

≠

j i i, j

∈

V

};

| E | =

2

)

1

(

2

−

=

¸

¹

·

¨

©

§

n

n

n

; ozn.

n

K

A = V

×

V ;

| A | =

2

n

Dopełnienie grafu:

G = (V, E ) :

E =

{

{i, j}: i, j

∈

V, i

≠

j, {i, j}

∉

E

}

D = (V, A) :

A = V

×

V \ A

Graf krawĊdziowy:

L(G) = (E, L(E)) :

{e

1

, e

2

}

∈

L(E)

⇔

e

1

i e

2

są zaleĪne

L(D) = (A, L(A)) :

(a

1

, a

2

)

∈

L(A)

⇔

a

1

i a

2

są zaleĪne

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 2 / 14

Związki pomiĊdzy stopniami wierzch. i liczbą krawĊdzi (łuków):

E

i

d

V

i

2

)

(

=

¦

∈

A

i

d

V

i

2

)

(

=

¦

∈

,

A

i

d

i

d

V

i

V

i

=

=

¦

¦

∈

+

∈

−

)

(

)

(

Macierzowy opis grafu (dla | V | = n i | E | = m lub | A | = m):

•

Macierz incydencji

I(G) =

m

j

n

i

ij

s

,...,

1

,...,

1

]

[

=

=

¯

®

­

∈

=

przyp.

przec.

w

0

jesli

1

j

ij

e

i

s

I(D) =

m

j

n

i

ij

s

,...,

1

,...,

1

]

[

=

=

°

¯

°

®

­

=

=

−

=

przyp.

przec.

w

0

)

,

(

jesli

1

)

,

(

jesli

1

k

i

a

i

k

a

s

j

j

ij

•

Macierz sąsiedztwa

B(G) =

n

j

n

i

ij

b

,...,

1

,...,

1

]

[

=

=

¯

®

­

∈

=

=

przyp.

przec.

w

0

}

,

{

jesli

1

E

j

i

b

b

ji

ij

B(D) =

n

j

n

i

ij

b

,...,

1

,...,

1

]

[

=

=

¯

®

­

∈

=

przyp.

przec.

w

0

)

,

(

jesli

1

A

j

i

b

ij

Izomorfizm grafów:

G

G

′

≅

∃

V

V

f

′

→



−

1

1

:

taka, Īe

∀

i, j

∈

V zachodzi

{i, j}

∈

E

⇔

{ f (i), f (j)}

∈

E

′

D

D

′

≅

∃

V

V

f

′

→



−

1

1

:

taka, Īe

∀

i, j

∈

V zachodzi

(i, j)

∈

A

⇔

(

f (i), f (j)

)

∈

A

′

Graf dwudzielny:

G = (V

1

∪

V

2

, E), V

1

∩

V

2

=

∅

wierzchołki w kaĪdym ze zbiorów V

1

i V

2

są parami niezaleĪne.

Graf dwudzielny pełny: oznaczenie

s

r

K

,

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 3 / 14

Graf planarny:

graf jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu

homeomorficznego z K

5

lub K

3, 3

(grafami homeomorficznymi z danym grafem nazywamy takie grafy,

które moĪna z niego otrzymaü przez podział krawĊdzi dodatkowymi

wierzchołkami stopnia 2)

Droga w grafie:

naprzemienny ciąg wierzchołków

i krawĊdzi grafu

( v

0

, e

1

, v

1

, e

2

, ..., v

t

−

1

, e

t

, v

t

),

spełniający warunek

e

i

= {v

i

−

1

, v

i

} dla i = 1, ..., t

naprzemienny ciąg wierzchołków

i łuków grafu

( v

0

, a

1

, v

1

, a

2

, ..., v

t

−

1

, a

t

, v

t

),

spełniający warunek

a

i

= ( v

i

−

1

, v

i

) dla i = 1, ..., t

Droga prosta:

Ī

adna krawĊdĨ siĊ nie powtarza

Ī

aden łuk siĊ nie powtarza

Droga elementarna:

Ī

aden wierzchołek siĊ nie powtarza.

Cykl w grafie:

droga zamkniĊtą, dla której v

0

= v

t

i t

>

0

Istnienie drogi i cyklu w grafie G o minimalnym stopniu wierzchołka

δ

(G):

•

w grafie G istnieje droga elementarna o długoĞci co najmniej

δ

(G),

•

dla

δ

(G)

≥

2 istnieje w grafie G cykl elementarny o długoĞci co

najmniej

δ

(G)+1.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 4 / 14

Graf spójny:

dla kaĪdej pary wierzchołków u

i v istnieje w nim droga z u do v

pochodny graf nieskierowny

jest spójny

Graf silnie spójny:

dla kaĪdej pary wierzchołków u

i v istnieje w nim droga z u do v

Składowa spójna grafu:

podgraf danego grafu, który jest spójny i nie jest podgrafem innego

grafu spójnego.

Związek liczby krawĊdzi (m), wierzchołków (n) i składowych

spójnych (k) w grafie:

2

)

1

)(

(

)

(

+

−

−

≤

≤

−

k

n

k

n

m

k

n

Warunek konieczny i dostateczny dwudzielnoĞci grafu:

dla n

≥

2 graf jest dwudzielny wtedy i tylko wtedy, kiedy nie zawiera

cyklu o nieparzystej długoĞci.

Związek z liczbą Ğcian (f ) w grafie planarnym:

n – m + f = k + 1

Warunki konieczne planarnoĞci grafu:

•

jeĞli graf jest planarny i n

≥

3, to m

≤

3n – 6 ,

•

jeĞli graf dwudzielny jest planarny i n

≥

3, to m

≤

2n – 4 ,

•

jeĞli graf jest planarny, to musi zawieraü co najmniej jeden

wierzchołek o stopniu mniejszym niĪ 6.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 5 / 14

Metody przeszukiwania grafu:

•

przeszukiwanie grafu w głąb z „zamykaniem” wierzchołków,

•

przeszukiwanie grafu wszerz z usuwaniem „nowoĞci”

wierzchołków.

Droga Eulera w grafie:

droga prosta, która zawiera

wszystkie krawĊdzie grafu

droga prosta, która zawiera

wszystkie łuki grafu

Cykl Eulera w grafie:

zamkniĊta droga Eulera

Warunek konieczny i dostateczny istnienia cyklu Eulera:

graf jest spójny i dla kaĪdego

wierzchołka jego stopieĔ d(v) jest

liczbą parzystą

graf jest spójny i dla kaĪdego

wierzchołka zachodzi

d

+

(v) = d

−

(v)

Warunek konieczny i dostateczny istnienia drogi Eulera:

graf jest spójny i dla nie wiĊcej

niĪ dwóch wierzchołków ich

stopieĔ jest liczbą nieparzystą

graf jest spójny i albo dla kaĪdego

wierzchołka zachodzi

d

+

(v) = d

−

(v), albo dla dokładnie

dwóch wierzchołków v

1

i v

2

ten

warunek nie zachodzi, ale

spełniona jest dla nich równoĞü

d

+

(v

1

)–d

−

(v

1

)=d

−

(v

2

)–d

+

(v

2

)=1

Mosty są wykorzystywane w algorytmie Fleury’ego.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 6 / 14

Droga Hamiltona w grafie:

droga elementarna, która zawiera wszystkie wierzchołki grafu

Cykl Hamiltona w grafie:

zamkniĊtą droga Hamiltona o długoĞci

V

Liczba cykli Hamiltona w grafie pełnym dla n

≥

3:

2

)!

1

(

−

n

(n

−

1)!

Warunki dostateczne istnienia cyklu Hamiltona:

•

jeĞli n

≥

3 i dla kaĪdej pary

niezaleĪnych wierzchołków v

i w zachodzi d(v) + d(w)

≥

n,

to graf ma cykl Hamiltona;

•

jeĞli n

≥

3 i dla kaĪdego

wierzchołka zachodzi d(v)

≥

2

n

,

to graf ma cykl Hamiltona;

•

jesli n

≥

3 i graf ma co

najmniej

2

2

)

2

)(

1

(

+

−

−

n

n

krawĊdzi, to ma on cykl

Hamiltona;

•

jeĞli n

≥

2, graf jest silnie

spójny i bez pĊtli oraz dla

kaĪdej pary niezaleĪnych

wierzchołków v i w zachodzi

1

2

)

(

)

(

−

≥

+

n

w

d

v

d

, to graf ma

cykl Hamiltona;

•

jeĞli n

≥

2, graf jest bez pĊtli

i dla kaĪdego wierzchołka

zachodzi

2

)

(

n

v

d

≥

+

oraz

2

)

(

n

v

d

≥

−

, to graf ma cykl

Hamiltona;

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 7 / 14

•

jeĞli istnieje ciąg (a

1

, a

2

, ..., a

n

),

w którym zachodzi

a

i

≤

i Ÿ a

n

−

i

≥

n – i dla i <

2

n

,

i dla którego sekwencja

wstĊpująca stopni

wierzchołków grafu spełnia

warunek d

i

(G)

≥

a

i

, to graf ma

cykl Hamiltona.

•

jeĞli graf jest silnie spójnym

turniejem, to ma cykl

Hamiltona (kaĪdy turniej ma

drogĊ Hamiltona).

Drzewo:

•

graf spójny bez cykli elementarnych,

•

graf o n

−

1 krawĊdziach bez cykli elementarnych,

•

graf spójny o n

−

1 krawĊdziach,

•

graf spójny, którego kaĪda krawĊdĨ jest mostem,

•

graf, którego kaĪde dwa wierzchołki są połączone dokładnie jedną

drogą,

•

graf bez cykli elementarnych, w którym dołączenie nowej krawĊdzi

tworzy dokładnie jeden cykl elementarny.

Las:

•

graf bez cykli elementarnych

Drzewo rozpinające grafu G = (V, E):

•

drzewo G

T

= (V, T) takie, Īe T

⊆

E

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 8 / 14

Liczba drzew rozpinających w grafie pełnym

n

K (dla n

≥

2):

2

−

n

n

Kod Prüfera.

(Rozpinające) drzewa przeglądu grafu w głąb i wszerz.

Dla G

T

= (V, T), które jest drzewem rozpinającym grafu G = (V, E):

•

T – zbiór gałĊzi,

•

E \ T – zbiór ciĊciw,

• Ω

= {

e

C : e

∈

E \ T} – zbiór cykli fundamentalnych.

Przedstawienie cyklu prostego w grafie spójnym G = (V, E):

dla dowolnego drzewa rozpinającego G

T

= (V, T) kaĪdy cykl prosty C

w grafie G moĪna jednoznacznie przedstawiü jako róĪnicĊ symetryczną

cykli fundamentalnych:

C =

1

e

C

⊗

2

e

C

⊗

...

⊗

k

e

C ,

gdzie

{

}

k

e

e ...,

,

1

= C \ T jest zbiorem ciĊciw wzglĊdem drzewa G

T

.

SpójnoĞü krawĊdziowa

λλλλ

(G) grafu spójnego G (dla n

≥

2) to

najmniejsza moc zbioru rozspajającego ten graf;

graf jest k-spójny krawĊdziowo, jeĞli

λ

(G)

≥

k.

SpójnoĞü wierzchołkowa

κκκκ

(G) grafu spójnego G (dla n

≥

2) to

najmniejsza moc zbioru rozdzielającego ten graf;

graf jest k-spójny (wierzchołkowo), jeĞli

κ

(G)

≥

k.

κ

(G)

≤

λ

(G)

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 9 / 14

Związki liczby dróg łączących dwa dane wierzchołki grafu z liczbą

elementów w zbiorach rozspajających i rozdzielających te wierzch.:

•

maksymalna liczba dróg krawĊdziowo rozłącznych, łączących

dwa róĪne wierzchołki v i w w grafie spójnym, jest równa

minimalnej liczbie krawĊdzi w zbiorze rozspajającym v i w,

•

maksymalna liczba dróg wierzchołkowo rozłącznych, łączących

dwa róĪne wierzchołki niesąsiednie v i w w grafie spójnym, jest

równa minimalnej liczbie wierzchołków w zbiorze

rozdzielającym v i w.

Związki liczby dróg łączących pary róĪnych wierzchołków w grafie z

odpornoĞcią grafu na utratĊ spójnoĞci:

•

graf jest k-spójny krawĊdziowo wtedy i tylko wtedy, gdy kaĪda

para róĪnych jego wierzchołków jest połączona co najmniej k

drogami krawĊdziowo rozłącznymi,

•

graf o co najmniej k

+

1 wierzchołkach jest k-spójny

(wierzchołkowo) wtedy i tylko wtedy, gdy kaĪda para róĪnych

jego wierzchołków jest połączona co najmniej k drogami

wierzchołkowo rozłącznymi.

Uogólnione związki liczby dróg łączących dwa zbiory wierzchołków

z liczbą wierzchołków rozdzielających te zbiory:

•

uogólnieniem pojĊcia zbioru rozdzielającego jest S-T separator,

•

uogólnieniem pojĊcia zbioru dróg wierzchołkowo rozłącznych

jest S-T konektor,

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 10 / 14

•

jeĪeli w grafie skierowanym D = (V, A) wybrano dwa podzbiory

S, T

⊆

V oraz wyznaczono minimalną moc S-T separatora równą

s, to istnieje S-T konektor Q = (V

Q

, A

Q

) grafu D o mocy s.

Związki liczby dróg łączących dwa dane wierzchołki grafu

skierowanego z liczbą elementów w zbiorach rozspajających i

rozdzielających te wierzchołki:

•

jeĪeli w grafie skierowanym D = (V, A) wybrano dwa róĪne

wierzchołki v i w, takie Īe (v, w)

∉

A, to minimalna moc zbioru

rozdzielającego wierzchołki v i w jest równa maksymalnej

liczbie dróg wierzchołkowo rozłącznych z v do w;

•

jeĪeli w grafie skierowanym D = (V, A) wybrano dwa róĪne

wierzchołki v i w, to minimalna moc zbioru rozspajającego

wierzchołki v i w jest równa maksymalnej liczbie dróg łukowo

rozłącznych z v do w.

Związki liczby dróg łączących pary róĪnych wierzchołków w grafie

skierowanym z odpornoĞcią grafu na utratĊ spójnoĞci:

•

graf skierowany jest k-spójny wierzchołkowo, jeĞli dla kaĪdych

dwóch róĪnych jego wierzchołków v i w istnieje co najmniej k

dróg wierzchołkowo rozłącznych z v do w;

•

graf skierowany jest k-spójny łukowo, jeĞli dla kaĪdych dwóch

róĪnych jego wierzchołków v i w istnieje co najmniej k dróg

łukowo rozłącznych z v do w.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 11 / 14

Sieü = graf skierowany z wyróĪnionymi dwoma wierzchołkami

(Ĩródło i ujĞcie) + przepustowoĞci wszystkich łuków

Przepływ w sieci ze Ĩródła do ujĞcia = wartoĞci przepływów przez

wszystkie łuki, mieszczące siĊ w granicach przepustowoĞci i

spełniające warunek zachowania przepływu we wszystkich

wierzchołkach poza Ĩródłem i ujĞciem.

WartoĞü przepływu przez sieü = bilans wypływu i wpływu do Ĩródła

= bilans wpływu i wypływu z ujĞcia.

Przekrój sieci = zbiór łuków wychodzących z zadanego zbioru

wierzchołków.

Przepływ przez przekrój = suma przepływów przez łuki przekroju.

PrzepustowoĞü przekroju = suma przepustowoĞci łuków przekroju.

Minimalny przekrój sieci = przekrój zadany zbiorem wierzchołków

zawierającym Ĩródło, którego przepustowoĞü jest minimalna.

Związek przepustowoĞci minimalnego przekroju z maksymalnym

przepływem przez sieü:

•

w kaĪdej sieci maksymalna wartoĞü przepływu ze Ĩródła do

ujĞcia jest równa przepustowoĞci minimalnego przekroju

pomiĊdzy Ĩródłem i ujĞciem.

Podstawa wyznaczania maksymalnego przepływu:

•

przepływ w sieci jest maksymalny wtedy i tylko wtedy, kiedy nie

istnieje dla niego ĞcieĪka powiĊkszająca ze Ĩródła do ujĞcia.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 12 / 14

Skojarzenie w grafie = podzbiór krawĊdzi, które są parami niezaleĪne.

Zbiór wewnĊtrznie stabilny wierzchołków = podzbiór

wierzchołków, które są parami niezaleĪne.

Podstawa wyznaczania skojarzenia maksymalnej mocy:

•

skojarzenie w grafie ma maksymalną moc wtedy i tylko wtedy,

kiedy ten graf nie zawiera drogi powiĊkszającej wzglĊdem tego

skojarzenia.

Pokrycie krawĊdziowe grafu = taki podzbiór jego krawĊdzi, Īe kaĪdy

wierzchołek grafu jest incydentny z co najmniej jedną krawĊdzią z

tego podzbioru.

Pokrycie wierzchołkowe grafu = taki podzbiór jego wierzchołków, Īe

kaĪda krawĊdĨ grafu jest incydentna z co najmniej jednym

wierzchołkiem z tego podzbioru.

Związki pomiĊdzy mocami skojarzenia, zbioru wewnĊtrznie

stabilnego wierzchołków i mocami pokryü:

•

maksymalna moc zbioru wewnĊtrznie stabilnego wierzchołków i

minimalna moc pokrycia wierzchołkowego sumują siĊ do liczby

wierzchołków w grafie,

•

maksymalna moc skojarzenia i minimalna moc pokrycia

krawĊdziowego takĪe sumują siĊ do liczby wierzchołków w

grafie,

•

maksymalna moc skojarzenia nie przekracza minimalnej mocy

pokrycia wierzchołkowego,

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 13 / 14

•

maksymalna moc zbioru wewnĊtrzne stabilnego wierzchołków

nie przekracza minimalnej mocy pokrycia krawĊdziowego,

•

jeĞli graf jest dwudzielny, to maksymalna moc skojarzenia jest

równa minimalnej mocy pokrycia wierzchołkowego.

Skojarzenie doskonałe = takie skojarzenie, wzglĊdem którego

wszystkie wierzchołki tego grafu są nasycone.

Warunek konieczny i dostateczny istnienia skojarzenia

doskonałego:

•

graf G = (V, E) ma skojarzenie doskonałe wtedy i tylko wtedy,

kiedy liczba składowych spójnych o nieparzystej liczbie

wierzchołków w podgrafie grafu G, indukowanym przez

podzbiór wierzchołków V \ S, nie przekracza liczby

wierzchołków w zbiorze S dla kaĪdego wyboru S

⊆

V.

Skojarzenie pełne wzglĊdem zbioru V

1

(lub V

2

) w grafie

dwudzielnym G = (V

1

∪

V

2

, E) = takie skojarzenie, wzglĊdem którego

wszystkie wierzchołki v

∈

V

1

(lub v

∈

V

2

) są nasycone.

Warunek konieczny i dostateczny istnienia skojarzenia pełnego

wzglĊdem V

1

:

•

w grafie dwudzielnym istnieje skojarzenie pełne wzglĊdem

zbioru V

1

wtedy i tylko wtedy, kiedy zbiór takich wierzchołków

v

2

∈

V

2

, dla których istnieje w zbiorze S

⊆

V

1

co najmniej jeden

wierzchołek sąsiedni, liczy co najmniej tyle samo elementów co

zbiór S dla kaĪdego wyboru S

⊆

V

1

.

WYĩSZA SZKOŁA INFORMATYKI STOSOWANEJ I ZARZĄDZANIA WIT

REPETYTORIUM (2)

J.Sikorski

Strona 14 / 14

Graf jest k-barwny, jeĞli moĪna prawidłowo pokolorowaü jego

wierzchołki, tzn. kaĪdemu wierzchołkowi moĪna przyporządkowaü

jeden z k kolorów w taki sposób, Īe wierzchołki sąsiednie mają róĪne

kolory.

Liczba chromatyczna grafu

χ

(G) = najmniejsza liczba naturalna k,

dla której graf ten jest k-barwny.

Ile barw potrzeba do prawidłowego pokolorowania grafu?

•

kaĪdy graf planarny jest czterobarwny,

•

kaĪdy graf planarny, który nie zawiera podgrafu izomorficznego

z K

3

, jest trzybarwny,

•

graf jest dwubarwny wtedy i tylko wtedy, kiedy nie zawiera

cykli o nieparzystej długoĞci,

•

kaĪde drzewo jest dwubarwne,

•

kaĪdy graf dwudzielny jest dwubarwny,

•

graf pełny

n

K jest n-barwny.

1 / 12

ZEBRANE ZADANIA DOMOWE Z KOMBINATORYKI

Zadanie 1

Wyznacz wartoĞü wyraĪenia

¦

=

»

¼

»

«

¬

«

=

−

=

7

1

0

mod

)

1

(

)

(

k

k

n

k

n

n

F

, dla n = 7.

Zadanie 2
Wyznacz wartoĞü wyraĪenia (

−

6) mod 4.

Zadanie 3
Wyznacz wartoĞü wyraĪenia 6 mod (

−

4).

Zadanie 4
W zbiorze

X = {1, 2, 3, 4, 5} zdefiniowano relacje binarne za pomocą tabel:

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 1 1 1 0 1

1 1 0 1 0 1

1 1 0 0 1 1

1 1 0 1 0 1

1 1 0 0 0 0

2 0 1 1 0 0

2 0 1 0 1 0

2 0 1 0 1 1

2 0 1 1 1 0

2 1 1 0 0 1

3 1 1 1 0 0

3 1 0 1 0 1

3 0 0 0 0 0

3 1 0 1 0 1

3 0 1 1 0 1

4 0 0 0 1 0

4 0 1 0 1 0

4 1 1 0 1 1

4 0 1 1 1 0

4 0 0 0 1 0

5 1 0 0 0 1 , 5 1 0 1 0 1 , 5 1 1 0 1 1 , 5 1 0 1 0 1 , 5 0 1 0 0 1 .

Zbadaj dla kaĪdej z nich, czy zdefiniowana relacja jest zwrotna, przechodnia, symetryczna, antysymetryczna.
Narysuj graf dla kaĪdej z relacji.

Zadanie 5
W zbiorze

X = {1, 2, 3, 4, 5} zdefiniowano relacje binarne za pomocą tabel:

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 1 1 1 0 1

1 1 1 1 0 1

1 1 0 0 1 0

1 0 0 0 0 0

2 0 1 1 0 0

2 0 0 1 1 1

2 1 1 1 1 0

2 1 0 0 0 0

3 0 0 1 0 1

3 0 0 1 0 0

3 0 0 1 0 0

3 0 0 1 1 0

4 0 1 0 1 0

4 0 0 1 0 0

4 0 0 1 1 1

4 0 0 0 1 1

5 0 0 0 0 1 , 5 0 0 0 0 1 , 5 0 0 0 0 1 , 5 0 0 0 0 0 .

Dopełnij kaĪdą z tablic relacji minimalną liczbą jedynek tak, aby stała siĊ ona tablicą relacji porządku w
zbiorze

X. Uzasadniaj dodanie kaĪdej jedynki.

Zadanie 6
W zbiorze

X = {1, 2, 3, 4, 5} zdefiniowano relacje binarne za pomocą tabel:

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 1 0 0 0 1

1 1 1 0 1 1

1 1 0 0 0 0

2 0 1 0 1 0

2 1 1 0 1 0

2 0 1 1 0 0

3 0 0 1 1 0

3 0 0 1 0 0

3 0 1 1 1 0

4 0 1 1 1 0

4 0 1 0 1 1

4 0 0 1 1 0

5 1 0 0 0 1 , 5 1 1 0 1 1 , 5 0 0 0 0 1 .

Dopełnij kaĪdą z tablic relacji minimalną liczbą jedynek tak, aby stała siĊ ona tablicą relacji równowaĪnoĞci
w zbiorze

X. Uzasadniaj dodanie kaĪdej jedynki.

Zadanie 7
Ile róĪnych relacji moĪna zdefiniowaü w iloczynie kartezjaĔskim

A

×

B, jeĞli |A| = m i |B| = n?

Ile moĪna zdefiniowaü relacji zwrotnych, a ile symetrycznych?
Relacja

R jest okreĞlona w zbiorze liczb rzeczywistych R : xRy

⇔

| x + y |

≤

1.

Zbadaj, czy relacja

R jest zwrotna, przechodnia, symetryczna, antysymetryczna i czy jest funkcją.

Odpowiedzi dokładnie uzasadnij! Zaznacz w układzie współrzĊdnych kartezjaĔskich zbiór punktów, których
współrzĊdne tworzą pary w podanej relacji

R.

Zadanie 8
Ile róĪnych nazw składających siĊ z 3 znaków moĪna utworzyü z 10 cyfr arabskich i 26 liter alfabetu
łaciĔskiego, jeĞli nazwa musi zaczynaü siĊ literą?

2 / 12

Zadanie 9
Ile liczb naturalnych z przedziału otwartego (100, 1000) moĪna zapisaü cyframi nieparzystymi?

Zadanie 10
Ile liczb naturalnych 5 cyfrowych nie mniejszych od 10000 składa siĊ z cyfr {0, 2, 4, 6}?

Zadanie 11
Numer rejestracyjny składa siĊ z 3 liter wybieranych ze zbioru {W, A, R, S, Z} i nastĊpujących po nich 2
cyfr wybieranych ze zbioru {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. W numerze rejestracyjnym cyfry mogą siĊ
powtarzaü, ale litery nie. Ile róĪnych numerów rejestracyjnych moĪna utworzyü według powyĪszych reguł?

Zadanie 12
Ile róĪnych kodów składających siĊ z 5 znaków moĪna utworzyü z 10 cyfr arabskich i 26 wielkich liter
alfabetu łaciĔskiego, jeĞli kod musi zaczynaü siĊ dwiema róĪnymi cyframi i koĔczyü literą oraz jeĞli na
trzeciej i czwartej pozycji moĪe byü zarówno cyfra jak i litera, ale nie moĪe powtórzyü siĊ ta sama litera?

Zadanie 13
Mamy do dyspozycji zbiór znaków składający siĊ z 26 liter i 10 cyfr oraz tablicĊ 3

×

3 o 9 polach.

Na ile sposobów moĪna wypełniü tablicĊ znakami, jeĞli muszą byü spełnione dwa warunki:

•

jeden z wierszy zawiera wyłącznie cyfry, a dwa pozostałe wyłącznie litery,

•

w kaĪdym wierszu wszystkie znaki są róĪne.

Zadanie 14
Na ile sposobów moĪna przydzieliü 5 ponumerowanych procesów do wykonania 3 ponumerowanym
procesorom, jeĞli procesy są wykonywane przez procesor zawsze w całoĞci i naleĪy okreĞliü kolejnoĞü
wykonywania procesów dla procesora, któremu przydzielono wiĊcej niĪ jeden proces.

Zadanie 15
Plan produkcji wymaga podania stanowiska montaĪowego dla kaĪdego urządzenia i wskazania kolejnoĞci
montowania urządzeĔ na kaĪdym ze stanowisk. Których planów produkcji jest wiĊcej i ile razy: planów
montowania 4 urządzeĔ na 6 stanowiskach, czy planów montowania 6 urządzeĔ na 4 stanowiskach.

Zadanie 16
Dla dwóch permutacji

¸¸

¹

·

¨¨

©

§

=

5

4

11

10

8

12

7

9

14

3

2

6

1

13

14

13

12

11

10

9

8

7

6

5

4

3

2

1

f

i

¸¸

¹

·

¨¨

©

§

=

3

2

10

9

12

8

7

11

5

6

1

14

13

4

14

13

12

11

10

9

8

7

6

5

4

3

2

1

g

rozłóĪ na rozłączne cykle permutacjĊ

h = f

−

1

g

−

1

, wyznacz typ i znak tej permutacji.

Zadanie 17
Dla dwóch permutacji

¸¸

¹

·

¨¨

©

§

=

9

1

17

4

2

10

16

5

14

13

15

11

12

6

7

3

8

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

f

i

¸¸

¹

·

¨¨

©

§

=

12

9

1

11

8

17

2

13

4

3

16

10

14

5

6

15

7

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

g

rozłóĪ na rozłączne cykle permutacjĊ

( )

1

−

=

g

f

h

, wyznacz typ i znak sgn(

h) tej permutacji.

Zadanie 18
OkreĞl znak permutacji

f

−

1

, jeĞli wiadomo, Īe permutacja

f jest typu 1

2

2

3

3

1

4

2

.

Dokładnie uzasadnij odpowiedĨ.

Zadanie 19
Na ile sposobów moĪna wykleiü na Ğcianie kwadrat mając do dyspozycji 25 róĪnokolorowych kafelków?

3 / 12

Zadanie 20
Ile jest permutacji f zbioru siedmioelementowego, dla których f (4) = 4 ?

Zadanie 21
Na ile sposobów moĪna ułoĪyü litery { a, b, c, d, e, f } w ciąg, tak aby litery { a, b } były obok siebie.

Zadanie 22
Dla podanych 3 podzbiorów zbioru X = {a, b, c, d, e, f, g, h} wyznacz wektory charakterystyczne

ξ

(Ai)

i podaj jakie liczby dziesiĊtne z zakresu 0

÷

255 mogą reprezentowaü te podzbiory:

A

1

= {b, d, h}, A

2

= {a, c, e, h}, A

3

= {d, e, f }.

Zadanie 23
Jakie podzbiory zbioru X = {a, b, c, d, e, f, g} są wskazywane przez liczby 24, 37 i 71?
Podaj wektory charakterystyczne dla tych podzbiorów.

Zadanie 24
Wypisz wszystkie podzbiory zbioru {a, b, c, d}, wraz z ich wektorami charakterystycznymi, w kolejnoĞci
zadanej kodem Graya.

Zadanie 25
Do pracy zgłosiło siĊ 16 tłumaczy znających jĊzyki rosyjski, hiszpaĔski lub angielski: 12 z nich znało jĊzyk
rosyjski, 15 znało hiszpaĔski, a jĊzyk angielski znało tyle samo tłumaczy, co rosyjski i hiszpaĔski
jednoczeĞnie. Ilu z nich znało jĊzyki hiszpaĔski i angielski, ale nie znało rosyjskiego, jeĞli wiadomo, Īe 8
znało rosyjski i angielski?

Zadanie 26
Do pracy zgłosiło siĊ 22 tłumaczy: 13 z nich znało jĊzyk francuski, 14 znało włoski, jĊzyk niemiecki znało
tyle samo tłumaczy, co francuski i włoski jednoczeĞnie, 6 z tłumaczy znało francuski i niemiecki a 4 z
tłumaczy znało jĊzyki włoski i niemiecki, ale nie znało francuskiego.
Ilu tłumaczy nie znało ani jednego z wymienionych jĊzyków?

Zadanie 27

Oblicz ile wynosi współczynnik liczbowy przy wyrazie x

4

⋅

y

3

w rozwiniĊciu dwumianu

(

)

7

2 y

x

−

.

Zadanie 28

Ile jest najkrótszych dróg na podanym planie miasta:

A

B

C

,

które prowadzą z punktu

A

do

B

, ale nie przechodzą przez punkt

C

?

PosłuĪ siĊ współczynnikami dwumianowymi.

Zadanie 29

Ile jest najkrótszych dróg na podanym planie miasta:

A

B

C

D

, które prowadzą z punktu A do B i

przechodzą przez oba punkty C i D? PosłuĪ siĊ współczynnikami dwumianowymi.

Zadanie 30

Ile jest najkrótszych dróg na podanym planie miasta:

A

B

,

które prowadzą z punktu A do B? PosłuĪ siĊ współczynnikami dwumianowymi.

Zadanie 31
Ile róĪnych liczb 7 cyfrowych moĪna utworzyü, zapisując w dowolnej kolejnoĞci 7 cyfr 8, 8, 8, 8, 5, 5 i 2 ?

4 / 12

Zadanie 32
ŁaĔcuch RNA to sekwencja zasad amonowych czterech rodzajów oznaczanych symbolami C, G, U i A. Ile
łaĔcuchów moĪe powstaü jako sekwencja 12 zasad, jeĞli wiadomo, Īe kaĪdy z nich składa siĊ z 4 zasad C,
3 zasad G, 3 zasad U i 2 zasad A, oraz zaczyna siĊ sekwencją CCA, a koĔczy GUC?

Zadanie 33
Wyznacz liczbĊ nieujemnych rozwiązaĔ całkowitoliczbowych dla równania
x

1

+ x

2

+ x

3

+ x

4

+ x

5

=

12, w których x

3

=

2.

Zadanie 34
Wyznacz dla równania x

1

+ x

2

+ x

3

+ x

4

+ x

5

= 19 liczbĊ nieujemnych rozwiązaĔ całkowitoliczbowych, w

których x

1

≥

2, x

2

≥

1, x

3

= 2, x

4

≥

3, x

5

> 2.

Wskazówka: trzeba wykonaü podstawienie zmiennych.

Zadanie 35
Ile jest nieujemnych i całkowitych rozwiązaĔ nierównoĞci x

1

+ x

2

+ x

3

+ x

4

”

6,

które spełniają warunki: x

1

>

0 i x

1

parzyste, x

2

∈

{0, 1}, x

3

podzielne przez 3 oraz x

4

”

2.

Wskazówka: trzeba wyznaczyü funkcjĊ tworzącą.

Zadanie 36
Dla zbioru z powtórzeniami X = < 3

∗

a, 2

∗

b, 5

∗

c > skonstruuj funkcjĊ tworzącą dla ciągu liczb podzbiorów

k-elementowych, w których kaĪdy z elementów a, b i c wystĊpuje nieparzystą liczbĊ razy.
Ile takich podzbiorów zawiera ponad 5 elementów?

Zadanie 37
Dla zbioru z powtórzeniami X = < 3

∗

a, 4

∗

b, 2

∗

c, 3

∗

d > rozwaĪ podzbiory, w których kaĪdy z elementów

a, b, c i d nie wystĊpuje lub wystĊpuje parzystą liczbĊ razy.
Ile takich podzbiorów zawiera 6 lub 8 elementów?

Zadanie 38
W barze sałatkowym pozostały 2 porcje fasolki, 2 porcje kiełków i 2 porcja ananasa. KaĪda porcja kosztuje
50 gr. Ile róĪnych sałatek moĪna zmieszaü za dokładnie 1 zł i 50 gr?

Zadanie 39
Na ile sposobów moĪna podzieliü zbiór 6 elementowy na 3 bloki?
WyprowadĨ odpowiedĨ z własnoĞci rekurencyjnej.

Zadanie 40
Na ile sposobów moĪna podzieliü zbiór cyfr {1, 2, 3, 5, 6, 7, 8, 9} na 4 bloki tak, aby cyfry parzyste były
razem w tym samym bloku? WyprowadĨ odpowiedĨ z własnoĞci rekurencyjnej.

Zadanie 41
Narysuj tablicĊ dla relacji równowaĪnoĞci, która jest związana z podziałem zbioru X={a, b, c, d, e} na dwa
bloki: {a, c, d} i {b, e}?

Zadanie 42
Na ile sposobów moĪna przydzieliü 9 ponumerowanych procesów 4 ponumerowanym procesorom tak, Īe
pierwsze dwa procesy bĊdą wykonane na pierwszym procesorze?
Przydzieliü trzeba wszystkie procesy, Īaden z procesorów nie moĪe pozostaü bezczynny i kaĪdy proces
bĊdzie w całoĞci wykonany na jednym procesorze.

Zadanie 43
Jaki podział i na ile bloków odpowiada funkcji f : X

→

Y okreĞlonej w nastĊpujący sposób:

f (x) = x mod 3, dla X = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} i Y = {0, 1, 2}.
Ile jest w tym przypadku wszystkich surjekcji f : X

→

Y ?

Zadanie 44
Dla jakiej liczby ciąg 5, 5, 2, 1 jest podziałem. Wyznacz dla niego podział sprzĊĪony i dla obu tych
podziałów narysuj diagram Ferrersa. Czy dla danej liczby naturalnej wiĊkszej od 10, podziałów na 5
składników jest wiĊcej, czy mniej niĪ podziałów o najwiĊkszym składniku równym 5? OdpowiedĨ uzasadnij.

5 / 12

Zadanie 45
Na ile sposobów moĪna podzieliü liczbĊ 11 na 3 składniki? WyprowadĨ odpowiedĨ z własnoĞci
rekurencyjnej.

Zadanie 46
Na ile sposobów moĪna rozdzieliü 8 jednakowych procesów pomiĊdzy 4 jednakowe procesory tak, aby na
jednym z nich zostały wykonane 3 procesy?
Rozdzieliü trzeba wszystkie procesy, Īaden z procesorów nie moĪe pozostaü bezczynny i kaĪdy proces musi
byü w całoĞci wykonany na jednym procesorze.

Zadanie 47
Sprawdziü zwrotnoĞü, symetriĊ, antysymetriĊ i przechodnioĞü relacji okreĞlonych nastĊpującymi tabelami:

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

Zadanie 48
Uzupełniü tabele minimalną liczbą jedynek tak, aby definiowały relacje równowaĪnoĞci:

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

Zadanie 49
Uzupełniü tabele minimalną liczbą jedynek tak, aby definiowały relacje porządku:

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

Zadanie 50
Sprawdziü, czy podane tabele definiują funkcje

}

5

,..

1

{

}

6

,..,

1

{

:

→

f

(pierwsza kolumna oznacza dziedzinĊ,

a pierwszy wiersz przeciwdziedzinĊ funkcji).

f

1

2

3

4

5

1

1

2

1

3

1

4

1

5

1

6

1

f

1

2

3

4

5

1

1

2

1

3

1

4

1

5

6

1

f

1

2

3

4

5

1

1

2

1

3

1

4

1

5

1

1

6

1

6 / 12

Zadanie 51
Obliczyü liczbĊ wszystkich relacji:

a) symetrycznych,

b) antysymetrycznych

w zbiorze {1, 2, 3, 4, 5} (takĪe w ogólnym przypadku w zbiorze{1, 2, ...., n}).

Zadanie 52
Obliczyü liczbĊ wszystkich relacji:

a) symetrycznych,

b) antysymetrycznych

w zbiorze {1, 2, 3, 4, 5}, które zawierają relacjĊ

)}

2

,

4

(

),

5

,

3

(

),

3

,

1

(

),

4

,

4

(

),

2

,

2

(

),

1

,

1

{(

=

R

.

Zadanie 53
Ile jest wszystkich funkcji okreĞlonych na zbiorze

}

,

,

},

,

{

},

,

{{

c

b

a

c

b

b

a

o wartoĞciach w zbiorze

}}

4

,

3

,

2

{

},

2

,

1

{{

?

Zadanie 54
Ile jest funkcji róĪnowartoĞciowych okreĞlonych na zbiorze {1,...,10} w ten sam zbiór?

Ile spoĞród tych funkcji w punkcie 2 przyjmuje wartoĞü 4, natomiast w punkcie 6 przyjmuje wartoĞü 9?

Zadanie 55
W pewnej firmie jest 5 działów. Do pracy przyjĊto 8 nowych pracowników. Na ile sposobów moĪna ich
przydzieliü do działów, jeĪeli:

a) nie nakładamy Īadnych ograniczeĔ na przydział?
b) do 1. działu nie trafiła Īadna osoba?
c) do 3. działu trafiła przynajmniej jedna osoba?
d) do 1. działu trafiły dokładnie 4 osoby?

Zadanie 56
W firmie jest 8 działów. PrzyjĊto 5 nowych pracowników i przydzielono ich do działów pojedynczo.
Na ile sposobów moĪna ich przydzieliü:

a) bez Īadnych dodatkowych załoĪeĔ?
b) jeĞli Kowalski ma siĊ znaleĨü w dziale A lub B?
c) jeĞli, ani Kowalski, ani IksiĔski nie trafiają do działu A?

Zadanie 57
Dany jest zbiór liczba naturalnych {1,...15}. Na ile sposobów moĪemy wybraü 6-elementowy podzbiór tak,
aby zawierał liczby 8 i 15. Na ile sposobów moĪemy wybraü tak, aby zawierał 8, lecz nie zawierał 15?

Zadanie 58
GrupĊ 12 pracowników postanowiono podzieliü na 2 zespoły. Na ile sposobów moĪna to zrobiü, jeĞli:

a) jeden zespół ma mieü 7 pracowników, a drugi 5?
b) obydwa mają mieü po 6 pracowników?
c) obydwa mają mieü po 6 pracowników oraz Kowalski i IksiĔski muszą trafiü do róĪnych zespołów?

Zadanie 59
ZnaleĨü liczbĊ permutacji zbioru {1...12} takich, Īe:

a) 1, 2, 3 stoją obok siebie.
b) 1, 2 lub 4,5 stoją obok siebie (wskazówka: jest to suma permutacji takich, Īe 1, 2 stoją obok siebie ze

zbiorem permutacji takich, Īe 4 i 5 stoją obok siebie; moc sumy liczymy sumując moce tych dwóch
zbiorów i odejmując moc czĊĞci wspólnej).

Zadanie 60
Dany jest rząd szesnastu krzeseł, na których posadzono 16 osób. WĞród tych 16 osób jest 4-osobowa rodzina
oraz drugie małĪeĔstwo. Obliczyü liczbĊ takich rozmieszczeĔ, Īe:

a) członkowie 4 –osobowej rodziny siedzą obok siebie.
b) przynajmniej jedna para małĪonków bĊdzie siedziała obok siebie.

Zadanie 61
Na karuzeli jest 8 siedzeĔ. Na ile sposobów moĪe na niej usiąĞü 8 osób?

7 / 12

Zadanie 62
W kolejce do 3 okienek stoi 10 osób.

a) Ile jest wszystkich ustawieĔ?
b) Ile jest ustawieĔ takich, Īe do 1. okienka nikt siĊ nie zgłosił?
c) Ile jest ustawieĔ takich, Īe przy 1.okienku jest 5 osób?

Zadanie 63
W pewnej miejscowoĞci mieszka 1845 osób. Udowodniü, Īe co najmniej 6 z nich ma urodziny tego samego
dnia roku.

Zadanie 64
Dana jest grupa miliona obywateli RP, o majątku liczonym w pełnych złotych wynoszącym co najwyĪej
90 000 złotych. Udowodniü, iĪ co najmniej 12 spoĞród nich dysponuje tą samą wielkoĞcią majątku.

Zadanie 65

Dany jest zbiór funkcji

}

5

..

1

{

}

4

..

1

{

:

→

f

. Udowodniü, Īe wĞród tych funkcji istnieje co najmniej 21

posiadających ten sam zbiór wartoĞci funkcji.

Zadanie 66
Obliczyü liczbĊ najkrótszych dróg z A do B, w nastĊpujących obszarach:

B

A
B

A
B

A

Wskazówka: w pierwszym obszarze jest to suma zbiorów dróg przechodzących przez punkty łączące
kwadraty ; w obszarze drugim naleĪy usunąü ze zbioru wszystkich dróg idących z A do B, wszystkie
drogi przechodzące przez jeden z trzech punktów znajdujących siĊ w rzĊdzie powyĪej istniejącego (suma
zbiorów dróg przechodzących przez te punkty); w obszarze trzecim ze zbioru wszystkich dróg Za do B,
usuwamy sumĊ zbiorów dróg przechodzących bądĨ przez dwa odcinki poziome bądĨ przez odcinek
pionowy; naleĪy pamiĊtaü, iĪ w kaĪdym z przykładów sumujemy zbiory, które nie są rozłączne.

8 / 12

Zadanie 67
Dzieci zrobiły łaĔcuch na choinkĊ z 5 kawałków niebieskiego, 6 kawałków czerwonego, 7 kawałków
Ī

ółtego, 5 kawałków zielonego oraz 6 kawałków srebrzystego papieru. Na koĔcu łaĔcucha przyczepiły

gwiazdĊ.

a) Na ile sposobów mogły utworzyü łaĔcuch, przy załoĪeniu, Īe na początku i koĔcu był kolor

czerwony.

b) Na ile sposobów moĪna utworzyü, jeĞli wiadomo, Īe początku lub na koĔcu był kolor czerwony.
c) Na ile sposobów moĪna utworzyü, jeĞli wiadomo, Īe początku lub na koĔcu nie było koloru

czerwonego.

Zadanie 68
ZnajdĨ liczbĊ rozwiązaĔ całkowitoliczbowych nierównoĞci:

a)

.

4

2

,

6

3

,

e

nieparzyst

,

parzyste

gdzie

8

4

3

2

1

4

3

2

1

≤

≤

≤

≤

≤

+

+

+

x

x

x

x

x

x

x

x

b)

.

3

,

{2,4}

,

}

1

,

0

{

,

e

nieparzyst

gdzie

9

5

4

3

2

1

5

2

1

=

+

∈

∈

≤

+

+

+

x

x

x

x

x

x

x

x



Zadanie 69
Na talerzach Īółtym, czerwonym, zielonym i czarnym rozmieszczono 16 jednakowych morelek. Na ile
sposobów moĪna to zrobiü, jeĪeli wiadomo, Īe:

a) Wszystkie talerze były zajĊte.
b) Dokładnie jeden talerz był pusty.
c) Na Īółtym talerzu znalazły siĊ 4 morelki.

Zadanie 70
Pan Kowalski postanowił kupiü kilka psów. Udał siĊ wiĊc do hodowcy, który miał do sprzedania 3
szczeniaczki foksterierów, 4 wyĪły, 3 cocker spaniele i 4 sznaucery.
Na ile sposobów pan Kowalski mógł wybraü psy, jeĞli postanowił kupiü:

a) trzy psy?
b) cztery psy?

Pan Kowalski rozróĪnia psy tylko ze wzglĊdu na rasĊ.

Zadanie 71
W trzech jednakowych pudełkach zostało rozmieszczonych 10 jednakowych klocków.
Obliczyü ile jest wszystkich rozmieszczeĔ, jeĞli wiemy, Īe Īadne pudełko nie jest puste.

Zadanie 72
Do czterech zespołów przyjĊto 12 nowych pracowników. Na ile sposobów moĪna to zrobiü, jeĞli:

a) KaĪdy zespół ma zostaü wzmocniony?
b) Do zespołu nr 1 trafiają 4 nowe osoby?
c) Do zespołu nr 1 trafiają 4 nowe osoby i pozostałe zespoły teĪ muszą byü wzmocnione?

Zadanie 73
Na wycieczkĊ trzema jednakowymi autokarami ma jechaü grupa osób. W dniu odjazdu na początku pojawiło
siĊ 12 osób. Na ile sposobów początkowa grupa moĪe siĊ rozlokowaü w autokarach?

Zadanie 74
Na piĊciu stanowiskach pracowało 5 szwaczek, szyjących jednakowe pidĪamy. Ile moĪliwych wyników
wykonania planu moĪna im przyporządkowaü, jeĞli wiadomo, Īe uszyły danego dnia 21 pidĪam i kaĪda
uszyła co najmniej jedną pidĪamĊ?

Zadanie 75
Trzynastu ufoludków postanowiło wybraü siĊ w podróĪ miĊdzygalaktyczną jednakowymi statkami
kosmicznymi. Na ile sposobów mogą wsiąĞü do statków, jeĞli wiadomo, ze najliczniejsza załoga liczy piĊciu
członków, a ufoludki uwaĪamy za nierozróĪnialne?

Zadanie 76
Na ile sposobów moĪna podzieliü 14-osobową grupĊ na 3 podgrupy, z których jedna liczy 6 osób, a dwie
pozostałe po 4 osoby?

Zadanie 77
Babcia ugotowała kompot z 15 jednakowych Ğliwek, który rozlała do 4 jednakowych słoików. Ile jest
rozmieszczeĔ Ğliwek w słoikach, jeĞli w kaĪdym muszą byü co najmniej 2 Ğliwki?

9 / 12

Zadanie 78
Na kurs jĊzyka francuskiego zgłosiło siĊ 11 osób, które mają dołączyü do trzech istniejących grup,
odbywających zajĊcia w róĪnych terminach. W jaki sposób moĪna ich przydzieliü tak, aby :

a) Do kaĪdej z grup trafiła przynajmniej jedna osoba?
b) Nowe osoby trafiły do dokładnie dwóch grup?

Pomoc do obliczania podziałów liczby:

1

)

1

,

(

=

−

n

n

P

oraz

¬ ¼

2

)

2

,

(

n

n

P

=

.

Zadanie 79
Niech A = {1, 2, 3, 4, 5, 6} i B = {3, 6, 9}. Dla tych zbiorów znajdĨ:

a) (A \ B)

∪

B

b) A

⊗

B

c) A \ (A

⊗

B).

Zadanie 80
Podaj przykłady takich zbiorów A i B, Īe

a) (A \ B)

∪

B = A

b) A

⊗

B = A

c) A \ (A

⊗

B) =

∅

Zadanie 81
Obliczyü dla n = 8 wartoĞü

Σ

(–1)

¬

n
k ¼ ¬k | nº

k=1

Zadanie 82
SprawdĨ związki:

n =

¬

n
2

¼

+

¬

n+1

2

¼

, n

∈

Z

n =

ª

n
2

º

+

ª

n+1

2

º

, n

∈

Z

Zadanie 83
W zbiorze A = {1, 2, 3, 4, 5, 6} okreĞlono relacjĊ: x R y

⇔

5 | x

3

– y

3

.

SprawdĨ, czy jest to relacja zwrotna, przechodnia, symetryczna, antysymetryczna, czy jest relacją
równowaĪnoĞci i czy jest funkcją. Narysuj graf relacji.

Zadanie 84
W zbiorze A = {2, 4, 5, 16, 25, 125} okreĞlono relacjĊ: x R y

⇔

istnieje liczba naturalna k taka, Īe y = x

k

.

SprawdĨ, czy jest to relacja zwrotna, przechodnia, symetryczna, antysymetryczna, czy jest relacją
czĊĞciowego porządku. Narysuj graf relacji.

Zadanie 85
Relacja R jest okreĞlona w zbiorze X = {1, 2, 3, 4, 5}. NastĊpujące pary naleĪą do relacji:
(1, 2), (1, 4), (2, 2), (2, 4), (2, 5), (3, 3), (4, 4), (4, 5).
Czy tak okreĞlona relacja jest relacją czĊĞciowego porządku? JeĞli nie jest, to uzupełnij ją przez dodanie jak
najmniejszej liczby par (m, n) tak, aby była relacją czĊĞciowego porządku.

Zadanie 86
Rozpatrz czterocyfrowe liczby utworzone z cyfr nieparzystych. Ile jest takich liczb, Īe

a) wszystkie cyfry są róĪne?
b) cyfra 1 wystĊpuje w takiej liczbie co najmniej raz?

Zadanie 87
Na ile sposobów moĪna ustawiü litery a, b, c, d, e, f w takiej kolejnoĞci, by litery a i b sąsiadowały ze sobą?

7

10 / 12

Zadanie 88
Ile jest liczb czterocyfrowych, w których:

a) wszystkie cyfry są róĪne?
b) nie wystĊpują cyfry 1, 2, 5, zaĞ cyfry 0, 3 wystĊpują?

Zadanie 89
Numer rejestracyjny składa siĊ z 2 liter wybieranych ze zbioru {B, C, D, E, F}, nastĊpujących po nich 4 cyfr
wybieranych ze zbioru {0, 1, 2, 3, 4, 5} i jednej litery na koĔcu ze zbioru {B, C, D, E, F}. W numerze
rejestracyjnym litery mogą siĊ powtarzaü, ale cyfry nie. Ile moĪna utworzyü róĪnych numerów
rejestracyjnych, w których wystąpi co najmniej raz litera B?

Zadanie 90
Ile jest permutacji f zbioru oĞmioelementowego, dla których f(5) = 1?

Zadanie 91
Dla dwóch permutacji

1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9

f =

g =

7 8 5 2 9 3 4 1 6

9 8 7 6 5 4 3 2 1

a) wyznacz ich złoĪenie f g
b) wyznacz permutacje odwrotne
c) rozłóĪ je na cykle i okreĞl ich typ
d) wyznacz znak permutacji f g, sprawdĨ prawdziwoĞü wzoru sgn(fg) = sgn(f) · sgn(g)

Zadanie 92
Wyznacz znak permutacji przy pomocy wzoru, wykorzystującego liczbĊ cyklów o długoĞci parzystej:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

f =

14 7 10 6 5 8 15 13 2 1 12 3 4 11 9

Zadanie 93
Na ile sposobów moĪe 8 osób wysiąĞü na trzech piĊtrach z windy, jeĪeli uwzglĊdniamy kolejnoĞü
wysiadania?

Zadanie 94
Do zdania egzaminu potrzeba wiĊcej niĪ 50% punktów. Tworzymy dwie listy – tych osób, które zdały
egzamin i tych, które nie zdały, w kolejnoĞci otrzymanych punktów. Wiedząc, Īe w grupie 10 studentów
Ī

aden wynik nie powtórzył siĊ, oblicz ile jest moĪliwych rozmieszczeĔ tych 10 osób na dwóch listach.

Zadanie 95
Oblicz iloĞü róĪnych harmonogramów wykonywania piĊciu programów na trzech procesorach oraz iloĞü
róĪnych harmonogramów wykonywania trzech programów na piĊciu procesorach. Jeden program
przyporządkowujemy tylko jednemu procesorowi. Za róĪne uwaĪamy harmonogramy, w których inny jest
przydział programów do procesorów lub inna jest kolejnoĞü ich wykonywania. Która z obliczonych liczb jest
wiĊksza i ile razy?

Zadanie 96
Ile jest permutacji 10-elementowych, w których przy rozkładzie na cykle rozłączne wystąpi cykl
9-elementowy?

Zadanie 97
Oblicz ile wynosi wspó

ł

czynnik liczbowy przy wyrazie x

2

y

5

w rozwiniĊciu dwumianu (x – 2y)

7

.

Zadanie 98
Na ile sposobów moĪna wybraü z 20 osób 3 rozłączne zespoły liczące odpowiednio 3, 5 i 7 członków?

Zadanie 99
Ile jest najkrótszych dróg z punktu A do B na podanym planie miasta, które nie przechodzą przez punkt C?

C

A

•

•

•

B

11 / 12

Zadanie 100
Ile róĪnych liczb 7 cyfrowych moĪna utworzyü, zapisując w dowolnej kolejnoĞci 7 cyfr: 8, 8, 8, 8, 5, 5, 2?

Zadanie 101
WykaĪ toĪsamoĞü:

Σ

(-1)

r

©

§

¹

·

n

r

= 0

n

∈

N, n > 0

Zadanie 102
Ile jest rosnących ciągów czterocyfrowych o moĪliwych wartoĞciach 1, 2, 3, 4, 5, 6, 7?

Zadanie 103
Ile rozwiązaĔ ma równanie: x

1

+ x

2

+ x

3

+ x

4

= 10, gdzie kaĪda liczba x

i

jest całkowita dodatnia?

Zadanie 104
Wyznacz liczbĊ nieujemnych rozwiązaĔ całkowitoliczbowych dla równania x

1

+ x

2

+ x

3

+ x

4

= 9 takich, Īe

x

1

≥

2 i x

2

≥

2.

Zadanie 105
Z grupy kart zawierającej 3 piki, 4 trefle, 5 kar, 6 kierów losujemy:

a) 3 karty
b) 4 karty
c) 15 kart

Ile jest moĪliwych wyborów?
(2 wybory uwaĪamy za róĪne, jeĞli róĪnią siĊ iloĞciami kart poszczególnych kolorów).

Zadanie 106
Iloma sposobami moĪna rozmieĞciü 10 nierozróĪnialnych kulek w piĊciu rozróĪnialnych torbach, jeĞli
chcemy Īeby do kaĪdej torby trafiła co najmniej jedna kulka?

Zadanie 107
Wyznacz liczbĊ rozwiązaĔ całkowitoliczbowych równania: x

1

+ x

2

+ x

3

+ x

4

= 9, takich, Īe 0

≤

x

1

≤

1,

0

≤

x

2

≤

1, 0

≤

x

3

≤

1, x

4

≥

0.

Zadanie 108
Dla zbioru z powtórzeniami x = < 4

∗

a, 2

∗

b, 5

∗

c > rozwaĪ podzbiory, w których kaĪdy z elementów a, b, c

wystĊpuje co najmniej raz, ale nie wiĊcej niĪ trzy razy. Ile jest takich podzbiorów?

Zadanie 109
Z grupy kart zawierającej 4 asy, 4 króle, 4 damy i 3 walety wybieramy 4 karty. Ile jest moĪliwych wyborów?
(RozróĪniamy tylko iloĞci poszczególnych figur).

Zadanie 110
Oblicz iloĞü rozwiązaĔ całkowitoliczbowych nieujemnych równania x

1

+ x

2

+ x

3

+ x

4

= 10, zawierających

tylko liczby parzyste (uwaga: 0 jest liczbą parzystą).

Zadanie 111
Z egzaminu moĪna uzyskaü oceny: 2, 3, 4, 5. GrupĊ 10 studentów dzielimy na cztery grupy według ocen z
egzaminu. Wiedząc, Īe w kaĪdej grupie znalazł siĊ co najmniej jeden student, oblicz ile jest moĪliwych
takich podziałów. UĪyj odpowiedniej własnoĞci rekurencyjnej oraz nastĊpujących wartoĞci:

9

9

= 3025

i

= 7770.

3

4

Zadanie 112
Z grupy kart zawierającej 3 piki, 4 trefle, 5 kar, 6 kierów losujemy 3 karty. Ile jest moĪliwych wyborów?
(2 wybory uwaĪamy za róĪne jeĞli róĪnią siĊ iloĞciami kart poszczególnych kolorów).

Zadanie 113
Wyznacz liczbĊ rozwiązaĔ całkowitoliczbowych równania: x

1

+ x

2

+ x

3

+ x

4

= 9, takich, Īe 0

≤

x

1

≤

1,

0

≤

x

2

≤

1, 0

≤

x

3

≤

1, x

4

≥

0.

n

r =0

12 / 12

Zadanie 114
Dla zbioru z powtórzeniami X = < 4*a, 3*b, 5*c > rozwaĪ podzbiory, w których kaĪdy z elementów a, b, c
wystĊpuje co najmniej raz, ale nie wiĊcej niĪ trzy razy.
Ile takich podzbiorów zawiera parzystą liczbĊ elementów?

Zadanie 115
Z grupy kart zawierającej 2 asy, 2 króle, 2 damy i 2 walety wybieramy 5 kart. Ile jest moĪliwych wyborów?
RozróĪniamy tylko iloĞci poszczególnych figur.

Zadanie 116
Oblicz iloĞü rozwiązaĔ całkowitoliczbowych nierównoĞci: x

1

+ x

2

+ x

3

≤

6, takich Īe x

1

> 1, x

2

< 2,

2 < x

3

< 5. Zbuduj funkcjĊ tworzącą.

Zadanie 117
Na ile sposobów moĪna rozmieĞciü 7 piłeczek w piĊciu pudełkach, jeĞli:

a) Pudełka są ponumerowane, ale piłeczki nierozróĪnialne?
b) Pudełka i piłeczki są rozróĪnialne, ale chcemy, Īeby w kaĪdym pudelku znalazła siĊ co najmniej

jedna piłeczka?

1 / 11

ZEBRANE ZADANIA DOMOWE Z TEORII GRAFÓW

Zadanie 1

Dana jest macierz sąsiedztwa pewnego grafu nieskierowanego o postaci:

»

»

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

«

«

¬

ª

0

0

1

1

1

0

0

0

0

1

0

1

1

0

0

0

1

0

1

1

0

0

0

0

1

0

1

0

0

1

0

1

0

0

1

0

6

5

4

3

2

1

6

5

4

3

2

1

Na podstawie tej macierzy:

a.

oblicz stopnie wierzchołków grafu,

b. oblicz liczbĊ krawĊdzi,
c.

narysuj graf.

Zadanie 2
Dla grafu z Zadania 1 narysuj graf bĊdący jego dopełnieniem.

Zadanie 3
Na rysunku grafu z Zadania 1 oznacz w wybrany przez siebie sposób krawĊdzie grafu i wyznacz macierz
incydencji oraz narysuj graf krawĊdziowy dla tego grafu.

Zadanie 4
Dla grafu z Zadania 1 narysuj:

a.

dwa przykładowe podgrafy o zbiorze wierzchołków V

1

={1, 2, 3, 6}, które nie są podgrafami

indukowanymi przez zbiór V

1

,

b. podgraf indukowany przez zbiór V

1

.

Zadanie 5

Dana jest macierz sąsiedztwa pewnego grafu skierowanego o postaci:

»

»

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

«

«

¬

ª

0

1

0

0

1

0

1

0

1

1

0

1

0

1

0

0

1

0

0

1

0

0

0

0

1

0

1

0

0

1

0

1

0

0

1

0

6

5

4

3

2

1

6

5

4

3

2

1

Na podstawie tej macierzy:

a.

oblicz stopnie wyjĞciowe i wejĞciowe wierzchołków grafu,

b. oblicz liczbĊ łuków,
c.

narysuj graf.

Zadanie 6
Narysuj graf pochodny dla grafu z zadania 5.

Zadanie 7
Graf nieskierowany G1 ma ciąg stopni wierzchołków postaci (6, 5, 4, 5, 5, 6, 3), natomiast graf G2 postaci
(6, 5, 4, 5, 5, 4, 5). Czy grafy te mogą byü izomorficzne? OdpowiedĨ uzasadnij opierając siĊ na definicji
izomorfizmu grafów.

Zadanie 8
Zbadaj izomorficznoĞü podanych par grafów.

a.

1

5

4

2

6

7

3

1

6

5

7

4

3

2

2 / 11

b.

Zadanie 9
Zbadaj, które pary grafów są izomorficzne wĞród czterech podanych:

Zadanie 10
Skonstruuj graf (nieskierowany) o 4 wierzchołkach, który jest izomorficzny ze swoim dopełnieniem.
Udowodnij izomorfizm tej pary grafów. Narysuj i opisz macierzami incydencji oba grafy. ZnajdĨ związek
pomiĊdzy wyznaczonymi macierzami incydencji.

Zadanie 11
Skonstruuj graf (nieskierowany) o 5 wierzchołkach, który jest izomorficzny ze swoim dopełnieniem.
Udowodnij izomorfizm tej pary grafów. Narysuj i opisz macierzami incydencji oba grafy. ZnajdĨ związek
pomiĊdzy wyznaczonymi macierzami incydencji.

Zadanie 12
Skonstruuj graf (nieskierowany) o 4 wierzchołkach, który jest izomorficzny ze swoim grafem
krawĊdziowym. Udowodnij izomorfizm tej pary grafów. Narysuj i opisz macierzami sąsiedztwa oba grafy.
ZnajdĨ związek pomiĊdzy wyznaczonymi macierzami sąsiedztwa.

Zadanie 13
Skonstruuj graf (nieskierowany) o 5 wierzchołkach, który jest izomorficzny ze swoim grafem
krawĊdziowym. Udowodnij izomorfizm tej pary grafów. Narysuj i opisz macierzami sąsiedztwa oba grafy.
ZnajdĨ związek pomiĊdzy wyznaczonymi macierzami sąsiedztwa.

Zadanie 14
Skonstruuj graf skierowany o 4 wierzchołkach, który jest izomorficzny ze swoim dopełnieniem. Udowodnij
izomorfizm tej pary grafów. Narysuj i opisz macierzami incydencji oba grafy. ZnajdĨ związek pomiĊdzy
wyznaczonymi macierzami incydencji.

Zadanie 15
Dla grafu skierowanego

({1, 2, 3, 4, 5}, {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 2), (3, 5), (4, 1), (4, 3), (5, 3), (5, 4)})

utwórz graf pochodny. Dla obu grafów wyznacz macierze incydencji i sąsiedztwa oraz stopnie
wierzchołków. W obu grafach wyznacz stopnie wierzchołków wzglĊdem zbioru {1, 3, 4}.

2

1

3

7

6

5

4

9

1

2

7

6

8

5

9

4

3

8

1

6

4

2

5

3

1

6

5

4

3

2

1

5

4

2

6

3

1

5

4

2

6

3

3 / 11

Zadanie 16
Narysuj graf relacji binarnej P na zbiorze V = {2, 3, 4, 5, 6, 7} zdefiniowanej nastĊpująco: i P j dla i, j

∈

V

⇔

NWD(i, j) = 1 (NWD oznacza najwiĊkszy wspólny dzielnik). Graf pochodny dla tego grafu opisz

macierzami incydencji i sąsiedztwa. Wyznacz stopnie wierzchołków w grafie relacji i jego grafie
pochodnym. Wyznacz takĪe stopnie wierzchołków wzglĊdem zbioru liczb pierwszych zawartych w V.

Zadanie 17

Zbadaj spójnoĞü i silną spójnoĞü grafu o macierzy sąsiedztwa

»

»

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

«

«

¬

ª

0

1

0

0

0

0

0

0

1

0

0

1

1

0

0

0

0

0

0

0

1

0

1

0

1

0

1

0

0

0

0

0

0

1

0

0

.

Zadanie 18
Dany jest graf nieskierowany, którego stopnie wierzchołków tworzą ciąg (5, 6, 5, 6, 5, 6, 5, 6).
Oblicz liczbĊ krawĊdzi tego grafu i sprawdĨ jego spójnoĞü.

Zadanie 19
Dany jest graf nieskierowany, którego stopnie wierzchołków tworzą ciąg (3, 2, 3, 7, 3, 3, 2, 5).
Zbadaj spójnoĞü tego grafu.

Zadanie 20
Dany jest graf nieskierowany o 10 wierzchołkach i minimalnym stopniu wierzchołka równym 5. Udowodnij,
Ī

e taki graf jest spójny. Udowodnij w ogólnym przypadku, Īe graf o n wierzchołkach i minimalnym stopniu

wierzchołka nie mniejszym od n/2 jest spójny.

Zadanie 21
Dany jest graf skierowany bez pĊtli o 13 wierzchołkach, dla których zarówno stopnie wyjĞciowe jak i
wejĞciowe wynoszą co najmniej 6. Udowodnij, Īe graf jest silnie spójny.

Zadanie 22
Dla których z wymienionych liczb krawĊdzi: 30, 36, 42, 48, istnieje graf spójny o 10 wierzchołkach?

Zadanie 23
Czy istnieje graf spójny o co najmniej dwóch wierzchołkach, w którym stopnie wierzchołków tworzą ciąg
kolejnych liczb naturalnych? OdpowiedĨ uzasadnij.

Zadanie 24
Narysuj graf o 9 wierzchołkach i 4 składowych spójnych, który ma:

a) 5 krawĊdzi,
b) 15 krawĊdzi.

Zadanie 25

W podanych grafach:

1

2

3

4

5

6

7

,

1

2

3

4

5

6

7

8

,

1

2

3

4

5

6

7

,

metodami przeglądu grafu wszerz i przeglądu w głąb wyznacz ciągi wierzchołków, które zaczynają siĊ od
wierzchołka: a) 1,

b) 4,

c) 7.

4 / 11

Zadanie 26
SprawdĨ, czy podane grafy są planarne:

Zadanie 27
Posługując siĊ tw. Kuratowskiego wykaĪ, czy graf o podanym
rysunku jest, czy nie jest planarny.

1

2

3

4

5

6

7

8

9

1 0

11

Zadanie 28
Czy wĞród grafów o 5 wierzchołkach i 9 krawĊdziach są grafy nieplanarne?
OdpowiedĨ uzasadnij w oparciu o tw. Kuratowskiego.

Zadanie 29
Graf ma n wierzchołków i m krawĊdzi.
W którym z podanych przypadków wykluczona jest planarnoĞü grafu?

a) n = 4 i m = 6,

b) n = 5 i m = 8,

c) n = 6 i m = 13,

d) n = 7 i m = 14,

e) n = 8 i m = 19.

OdpowiedĨ uzasadnij w oparciu o warunek konieczny wynikający z wzoru Eulera.

1

3

4

5

6

8

7

2

3

4

5

6

8

7

2

1

1

2

3

4

5

6

9

8

7

1

7

6

5

4

3

2

8

1

2

3

4

5

6

8

7

1

2

3

4

5

6

7

8

5 / 11

Zadanie 30
Rozstrzygnij z uzasadnieniem,
czy podane grafy są dwudzielne:

2

1

3

6

7

4

5

4

2

1

3

5

6

7

Zadanie 31
SprawdĨ, czy podane grafy są dwudzielne:

Zadanie 32
SprawdĨ na podstawie podanej macierzy sąsiedztwa grafu, nie rysując go, czy istnieje w nim droga lub cykl
Eulera. W przypadku odpowiedzi pozytywnej, narysuj graf i wyznacz za pomocą algorytmu Fleury’ego
drogĊ lub cykl Eulera.

»

»

»

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

«

«

«

¬

ª

0

1

0

1

0

1

1

1

0

0

1

1

1

0

0

0

0

0

0

1

1

1

1

0

0

1

1

0

0

1

0

1

0

1

1

1

1

1

1

1

0

1

1

0

1

0

1

1

0

Zadanie 33
Stosując algorytm Fleury’ego wyznacz drogĊ Eulera w grafie.

Zadanie 34
Rozstrzygnij z uzasadnieniem, czy grafy o podanych rysunkach są Eulerowskie:

JeĞli są, to w kaĪdym z nich wyznacz drogĊ (cykl) Eulera za pomocą algorytmu Fleury’ego.

1

2

3

4

5

6

7

8

a

b

c

d

e

f

g

h

1

2

3

5

6

7

2

3

4

5

6

7

4

1

6 / 11

Zadanie 35
Czy po dodaniu do pierwszego z grafów podanych w zadaniu 34:

a) 1,

b) 2,

c) 3 krawĊdzi moĪna uzyskaü graf, w którym bĊdzie istniała droga Eulera?

OdpowiedĨ zilustruj na rysunku.

Zadanie 36
Czy graf pochodny dla dowolnego Eulerowskiego grafu skierowanego jest zawsze Eulerowski? OdpowiedĨ
uzasadnij!

Zadanie 37
Czy graf krawĊdziowy dla grafu Eulerowskiego jest zawsze Eulerowski? OdpowiedĨ uzasadnij!

Zadanie 38
W grafach z zadania 34 zamieĔ kaĪdą krawĊdĨ na łuk tak, aby powstały z nich Eulerowskie grafy
skierowane.

Zadanie 39
W poniĪszych grafach sprawdĨ, czy są spełnione warunki dostateczne istnienia cyklu Hamiltona:
a) z tw. Diraca

b) z tw. Ore

c) tw. Chvátala. ZnajdĨ w nich, jeĞli istnieje, cykl Hamiltona.

Zadanie 40
W podanych grafach sprawdĨ niezaleĪnie, które z omawianych warunków dostatecznych istnienia cyklu
Hamiltona dla grafów nieskierowanych (tw. Ore, Diraca, Chvátala, o liczbie krawĊdzi i inne) są spełnione, a
które nie:

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

Zadanie 41
Osiem komputerów połączono w sieü. Liczby komputerów, z którymi kaĪdy z nich ma bezpoĞrednie
dwukierunkowe połączenie wynoszą: 3, 5, 3, 4, 3, 5, 5, 6. Jeden z komputerów wysyła sygnał do wszystkich,
z którymi ma bezpoĞrednie łącze. KaĪdy z komputerów, otrzymawszy sygnał, przesyła go do kolejnych w
nastĊpnym kroku czasowym. Czy jest moĪliwe, aby sygnał dotarł do wszystkich komputerów i wrócił do
komputera początkowego w oĞmiu krokach czasowych?

Zadanie 42
Dany jest graf o nastĊpujących stopniach wierzchołków: 3, 3, 4, 3, 5, 3, 2, 3. WykaĪ, Īe dopełnienie tego
grafu posiada cykl Hamiltona.

3

4

5

1

2

7

6

1

7

2

3

4

5

6

7 / 11

Zadanie 43
WykaĪ, Īe graf krawĊdziowy grafu o nastĊpujących stopniach wierzchołków: 2, 4, 4, 4, 2, 4, 4, jest grafem
hamiltonowskim.

Zadanie 44
SprawdĨ, czy w poniĪszych grafach są spełnione:

a.

warunek dostateczny z tw. Nasha-Williamsa dla istnienia cyklu Hamiltona,

b. silna spójnoĞü grafu,
c.

warunek dostateczny z tw. Meyniela dla istnienia cyklu Hamiltona.

Wyznacz, jeĞli istnieją, cykle Hamiltona.

Zadanie 45
W podanych grafach skierowanych sprawdĨ, czy spełnione są warunki dostateczne istnienia cyklu Hamiltona
z tw. Meyniela i Nasha-Williamsa:

1

2

3

5

4

6

1

2

3

5

4

6

1

2

3

5

4

6

Zadanie 46
W podanych grafach sprawdĨ, czy spełnione są warunki dostateczne istnienia cyklu Hamiltona z tw. Redei,
Thomassena i Camiona:

1

2

3

4

5

1

2

3

4

5

Zadanie 47
W podanych grafach wyznacz kolejnoĞci wierzchołków oraz drzewa przeglądu grafu dla przeglądów wszerz
i w głąb, które zaczynają siĊ od wierzchołków: dla grafu a. od 3 i 7, dla grafu b. od 1 i 7.

a.

b.

2

3

1

4

5

6

7

8

2

3

1

4

5

6

7

8

1

2

3

4

5

6

1

2

3

4

5

6

8 / 11

Zadanie 48
W podanych grafach wyznacz kolejnoĞci
wierzchołków oraz drzewa przeglądu grafu dla
przeglądów wszerz i w głąb, które zaczynają
siĊ od wierzchołków:

a) 1,

b) 4,

c) 7.

1

2

3

4

5

6

7

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

Zadanie 49
Wyznacz kody Prüfera
dla nastĊpujących drzew
rozpinających w grafie K

8

:

Odp.:
a) (6, 3, 2, 5, 5, 8);
b) (2, 3, 8, 6, 4, 3);
c) (2, 1, 4, 8, 6, 4).

a)

1

2

3

4

5

6

7

8

, b)

1

2

3

4

5

6

7

8

, c)

1

2

3

4

5

6

7

8

.

Zadanie 50
Wyznacz kod Prüfera dla drzewa:

Zadanie 51
W grafie K

9

wyznacz i narysuj drzewa

rozpinające o nastĊpujących kodach Prüfera:

a) (1, 2, 3, 4, 5, 6, 7),

b) (2, 2, 3, 2, 1, 8, 9),

c) (7, 4, 4, 4, 4, 4, 3),

d) (9, 7, 5, 3, 1, 2, 4),

e) (5, 6, 4, 7, 3, 8, 2).

Zadanie 52
Dane są kody Prüfera dla drzew rozpinających: (3, 3, 4, 5, 6, 9, 6, 5, 7, 7) i (2, 3, 4, 3, 6, 7, 7, 8, 10, 8, 12).
Wyznacz i narysuj te drzewa na podstawie kodów.

Zadanie 53
Wyznacz liczbĊ wszystkich zer w macierzy incydencji grafu nieskierowanego, który jest drzewem
rozpinającym o kodzie Prüfera (10, 3, 4, 4, 7, 9, 2, 2, 5, 1). Odp.: 110.

Zadanie 54
W grafie podanym na rysunku zaznaczono jego drzewo rozpinające.
Wyznacz wszystkie cykle fundamentalne wzglĊdem tego drzewa i przedstaw
jako róĪnicĊ symetryczną takich cykli nastĊpujące cykle proste w grafie:

a) {{1, 2}, {2, 3}, {3, 6}, {1, 6}},

b) {{1, 4}, {4, 5}, {5, 6}, {1, 6}},

c) {{1, 4}, {3, 4}, {3, 6}, {1, 6}}.

1

2

3

4

5

6

7

2

3

1

4

5

6

7

8

9

10

11

12

9 / 11

Zadanie 55

Dla grafu na rysunku:

a.

znajdĨ wszystkie cykle fundamentalne wzglĊdem drzewa rozpinającego o zbiorze krawĊdzi
T={ {1,5},{2,4},{3,4},{4,7},{5,7},{6,7}} oraz przedstaw cykle proste:
{{1,6},{6,7},{4,7},{3,4},{1,3}} i {{1,6},{2,6},{2,5},{3,5},{1,3}}, jako róĪnice symetryczne
odpowiednich cykli fundamentalnych,

b. znajdĨ wszystkie cykle fundamentalne wzglĊdem drzewa rozpinającego o zbiorze

T={{1,6},{2,5},{2,6},{3,5},{4,7},{5,7}} oraz przedstaw cykle proste:
{{1,3},{3,4},{4,7},{5,7},{1,5}} i {{2,6},{2,4},{3,4},{1,3},{1,6}}, jako róĪnice symetryczne
odpowiednich cykli fundamentalnych.

Zadanie 56
Wyznacz w podanym grafie maksymalną liczbĊ dróg krawĊdziowo
rozłącznych, które łączą wierzchołki 1 i 8. Podaj przykładowy zbiór
takich dróg, który ma maksymalną moc. Co na podstawie mocy tego
zbioru moĪna powiedzieü o minimalnej liczbie krawĊdzi w zbiorze
rozspajającym 1 i 8? WskaĪ zbiór rozspajający 1 i 8 o wskazanej mocy.

1

4

2

3

6

7

8

5

Zadanie 57
Czy podany graf jest 3-spójny?
Ile wynosi jego spójnoĞü wierzchołkowa?
Odpowiedzi uzasadnij.

Zadanie 58

Dany jest graf spójny, niekierowany:

a.

wskaĪ zbiór rozspajający graf o mocy 4,

b. wskaĪ zbiór rozspajający graf o mocy 3,
c.

wskaĪ zbiór rozdzielający graf o mocy 3,

d. wskaĪ zbiór rozdzielający graf o mocy 2,
e.

wskaĪ zbiory rozspajające pary wierzchołków: 1 i 6, 1 i 11,

f.

zastosuj twierdzenie Mengera w wersji krawĊdziowej do wyznaczenia minimalnej mocy zbiorów
rozpajających dla powyĪszych par.

g. zastosuj twierdzenie Mengera w wersji wierzchołkowej do wyznaczenia minimalnej mocy zbioru

rozdzielającego wierzchołki 1 i 11,

h. wykaĪ 3-spójnoĞü krawĊdziową grafu,
i.

wykaĪ 2-spójnoĞü (wierzchołkową) grafu,

j.

sprawdĨ, czy graf jest 3-spójny (wierzchołkowo),

k. wyznacz spójnoĞü krawĊdziową grafu,
l.

wyznacz spójnoĞü wierzchołkową grafu.

1

2

3

4

5

7

10

11

8

9

6

2

3

1

4

5

6

7

10 / 11

Zadanie 59

W podanym grafie wyznacz:

b

a

c

v

w

e

d

f

h

g

j

a) maksymalną liczbĊ dróg krawĊdziowo rozłącznych pomiĊdzy parą wierzchołków

v

i

w

,

b) maksymalną liczbĊ dróg krawĊdziowo rozłącznych pomiĊdzy parą wierzchołków

d

i

j

,

c) maksymalną liczbĊ dróg wierzchołkowo rozłącznych pomiĊdzy parą wierzchołków

v

i

w

,

d) maksymalną liczbĊ dróg wierzchołkowo rozłącznych pomiĊdzy parą wierzchołków

d

i

c

,

e) minimalny zbiór krawĊdzi rozspajający wierzchołki

v

i

w

,

f)

minimalny zbiór krawĊdzi rozspajający wierzchołki

d

i

j

,

g) minimalny zbiór wierzchołków rozdzielający wierzchołki

v

i

w

,

h) minimalny zbiór wierzchołków rozdzielający wierzchołki

d

i

c

,

i)

spójnoĞü krawĊdziową,

j)

spójnoĞü wierzchołkową.

Zilustruj obie wersje tw. Mengera na powyĪszych zbiorach. Odpowiedz z uzasadnieniem na pytania:

a) czy ten graf jest 3-spójny?

b) czy ten graf jest 3-spójny krawĊdziowo?

c) czy ten graf jest 2-spójny?

Zadanie 60*
W podanym grafie wyznacz:

a) wszystkie S-T drogi,

b) co najmniej trzy róĪne S-T separatory

(róĪne od zbiorów S i T),

c) S-T separator o minimalnej mocy róĪny od zbiorów

S i T,

d) co najmniej dwa róĪne S-T konektory,

e) S-T konektor o maksymalnej mocy.

Zilustruj uogólnione tw. Mengera na powyĪszych zbiorach.

S

T

1

2

3

5

9

4

7

6

8

Zadanie 61*
W podanym grafie wyznacz:

a) wszystkie S-T drogi,

b) co najmniej trzy róĪne S-T separatory

(róĪne od zbiorów S i T),

c) S-T separator o minimalnej mocy,

d) co najmniej trzy róĪne S-T konektory,

e) S-T konektor o maksymalnej mocy.

Zilustruj uogólnione tw. Mengera na powyĪszych zbiorach.

S

T

1

2

3

5

9

4

7

6

8

11 / 11

Zadanie 62
W podanej sieci o przepustowoĞciach łuków równych 4 i
przepływach: f (a) = 4, f (b) = 3, f (d) = 2, f (e) = 1, f (f ) = 1,
f (g) = 1, f (i) = 1, wyznacz:

a) wartoĞci brakujących przepływów przez łuki tak, aby

powstał przepływ przez sieü z 2 do 6,

b) wartoĞü wyznaczonego przepływu przez sieü,

c) wartoĞci przepływów przez przekroje zadane zbiorami {2,

3, 4}, {2, 5, 7} i {1, 2, 3, 7},

d) tylko na podstawie wartoĞci wyznaczonych w punktach b) i

c) wyznacz wartoĞci przepływów przez przekroje zadane
zbiorami {1, 3, 4, 6}, {1, 5, 6, 7} i {4, 5, 6}.

Odp.: b) 8; c) 11, 10, 10; d) 2, 3, 2.

2

1

3

6

7

a

c

b

i

j

d

g

h

e

f

4

5

k

l

Zadanie 63
W podanej sieci o przepustowoĞciach łuków równych 4 i przepływach: f (a) =
1, f (c) = 2, f (d) = 1, f (f ) = 2, f (h) = 1, f (k) = 1, f (l) = 3, wyznacz:

a) wartoĞci brakujących przepływów przez łuki tak, aby powstał

przepływ przez sieü z 6 do 4,

b) wartoĞü wyznaczonego przepływu przez sieü,

c) wartoĞci przepływów przez przekroje zadane zbiorami

{1, 2, 6}, {1, 3, 5, 6} i {3, 5, 6, 7},

d) tylko na podstawie wartoĞci wyznaczonych w punktach b) i c)

wyznacz wartoĞci przepływów przez przekroje zadane zbiorami {3,
4, 5, 7}, {1, 2, 4} i {2, 4, 7}.

Odp.: b) 7; c) 9, 10, 10; d) 2, 3, 3.

4

2

1

3

5

6

a

c

b

i

d

g

h

e

f

7

j

k

l

Zadanie 64
W podanej sieci (przy łukach podano wartoĞci przepływów i w
nawiasach ich przepustowoĞci) wyznacz:

a) wartoĞü maksymalnego przepływu z s do t za pomocą ĞcieĪek

powiĊkszających przepływ,

b) minimalny przekrój pomiĊdzy s i t oraz jego przepustowoĞü.

Zilustruj tw. Forda i Fulkersona w podanej sieci.

Odp.: a) 6.

v

u

w

t

s

2 (3

)

2 (3)

1 (2)

2 (3)

1 (1)

1 (2)

1 (3)

1 (2)

1 (3)

x

y

z

1 (2)

1 (2)

1 (3)

2 (2)

2 (2)

1 (1)

Zadanie 65
W podanej sieci (przy łukach podano wartoĞci przepływów i w
nawiasach ich przepustowoĞci) wyznacz:

a) wartoĞü maksymalnego przepływu z s do t za pomocą ĞcieĪek

powiĊkszających przepływ,

b) minimalny przekrój pomiĊdzy s i t oraz jego przepustowoĞü.

Zilustruj tw. Forda i Fulkersona w podanej sieci.

Odp.: a) 8.

v

u

w

t

s

3

)

(4

3 (4)

2 (2)

2 (3)

1 (2)

1 (2)

2 (3)

0 (1)

2 (3)

x

y

z

0 (1)

1 (2)

1 (3)

1 (2)

1 (2)

1 (1)

* nadobowiązkowe

Przykładowe zadania egzaminacyjne z kombinatoryki

Zadanie 1
Na ile sposobów moĪna obdarowaü 8 dzieci 36 cukierkami tak, aby: rozdaü wszystkie cukierki, nie
pozostawiü Īadnego dziecka bez cukierków i zapewniü kaĪdemu dziecku parzystą liczbĊ cukierków?
Odp.: 19 448.

Zadanie 2
Dla relacji binarnej w zbiorze X = {a, b, c, d, e, f, g}, opisanej podaną tablicą,
naleĪy zbudowaü diagram Hassego i za jego pomocą wyznaczyü:
zbiór ograniczeĔ górnych i zbiór ograniczeĔ dolnych zbioru A = {c, d, e} oraz
kres dolny i kres górny zbioru A, łaĔcuch o maksymalnej licznoĞci i minimalną
liczbĊ antyłaĔcuchów pokrywających zbiór X.
Na przykładzie podanej relacji naleĪy zilustrowaü tezĊ dualnego tw. Dilwortha.
Odp.: sup A = e, inf A = b, 4 = 4.

»

»

»

»

»

»

»

»

»

¼

º

«

«

«

«

«

«

«

«

«

¬

ª

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

Zadanie 3
Na ile sposobów moĪna ułoĪyü w ciąg 4 jednakowe kule zielone, 3 jednakowe kule czerwone i 5 kul
ponumerowanych? Odp.: 3 326 400.

Zadanie 4
W turnieju wziĊło udział 9 pingpongistów. Rozegrano pewną liczbĊ spotkaĔ singlowych, w których Īadna
para graczy nie wystąpiła wiĊcej niĪ jeden raz.
NaleĪy wykazaü, Īe bez wzglĊdu na liczbĊ rozegranych spotkaĔ wĞród zawodników jest co najmniej
dwóch takich, którzy rozegrali tyle samo spotkaĔ w tym turnieju. Odp.: r = 1.

Zadanie 5
Ile jest permutacji zbioru {1, 2, 3, 4, 5, 6}, w których obok siebie są liczby 1 i 2 lub liczby 5 i 6?
Odp.: 384.

Zadanie 6
W gonitwie biorą udział 4 konie ponumerowane kolejnymi liczbami naturalnymi od 1 do 4.
Na ile sposobów moĪe zakoĔczyü siĊ ta gonitwa tak, aby Īaden z koni nie zajął miejsca zgodnego ze
swoim numerem? Odp.: 9.

Zadanie 7
Ile jest róĪnych ciągów zaczynających siĊ od M lub koĔczących siĊ na M, które moĪna utworzyü z
wszystkich liter słowa MATEMATYKA? Odp.: 57 120.

Zadanie 8
Ile jest nieujemnych i całkowitych rozwiązaĔ nierównoĞci

6

4

3

2

1

≤

+

+

+

x

x

x

x

, które spełniają warunki:

1

x

parzyste i

0

1

>

x

,

}

,

{ 1

0

2

∈

x

,

3

x

podzielne przez 3 i

2

4

≤

x

.

Odp.: 15.

Zadanie 9
W pewnym klubie tenisowym trenuje 5 równorzĊdnych deblistów. Klub planuje rozgrywki ligowe w
sezonie, w którym musi rozegraü 8 meczy z innymi klubami. Na ile sposobów moĪna zaplanowaü
rozgrywki deblowe w tym sezonie, jeĞli w kaĪdym meczu trzeba wystawiü jedna parĊ deblową?
Odp.: 100 000 000.

Zadanie 10
Na ile sposobów moĪna rozdzieliü 6 ponumerowanych procesów pomiĊdzy 3 jednakowe procesory tak,
aby Īaden z procesorów nie był obciąĪony wiĊcej jak 3 procesami?
Rozdzieliü trzeba wszystkie procesy, Īaden z procesorów nie moĪe pozostaü bezczynny i kaĪdy proces
bĊdzie w całoĞci wykonywany na jednym procesorze. Odp.: 75.

Zadanie 11
Na ile sposobów moĪna zaplanowaü wykonanie 5 róĪnych urządzeĔ na 3 stanowiskach montaĪowych tak,
aby Īadne z nich nie pozostało bezczynne?
Plan musi podawaü dla kaĪdego urządzenia numer stanowiska i okreĞlaü, w jakiej kolejnoĞci urządzenia
bĊdą montowane na kaĪdym ze stanowisk. Odp.: 720.

Przykładowe zadania egzaminacyjne z teorii grafów

Lp. Zadanie

1. WyjaĞnij w oparciu o tw. Halla, dlaczego w grafie podanym na rysunku nie

ma skojarzenia pełnego wzglĊdem zbioru V

1

= {1, 2, 3, 4, 5}.

2

3

4

1

5

6

7

8

9

10

2. W podanej sieci (przy jej łukach podano przepustowoĞci) znane są

nastĊpujące przepływy: f (v, s) = 1, f (s, y) = 3, f (v, y) = 1, f (z, x) = 0,
f (z, t) = 1, f (x, t) = 3.
Wyznacz przepływy w pozostałych łukach tak, aby został w sieci
zdefiniowany przepływ z s do t.
Wyznacz wartoĞü przepływu przez całą sieü i wartoĞü przepływu przez
przekrój zadany zbiorem wĊzłów {s, v, y}.
W oparciu o tw. Forda i Fulkersona rozstrzygnij, czy uzyskany przepływ jest
maksymalny w tej sieci.

v

x

y

t

s

6

3

2

3

1

2

3

1

2

3

3. W pewnym kraju Unii Europejskiej jest 9 duĪych miast. PomiĊdzy kaĪdą parą miast zbudowana jest wygodna autostrada.

Rolnicy tego kraju, niezadowoleni z wysokoĞci dopłat bezpoĞrednich, postanowili zablokowaü te autostrady wysypując na
nie efekty swojej pracy. Jednak płodów rolnych starczyło im tylko na zablokowanie po jednym kierunku ruchu z kaĪdej
autostrady. Rozstrzygnij z uzasadnieniem, czy premier tego kraju bĊdzie mógł odwiedziü samochodem, nie łamiąc
przepisów ruchu drogowego, wszystkie duĪe miasta, zaczynając podróĪ z dowolnego i odwiedzając kaĪde tylko raz. Czy
moĪe byü pewny, Īe wróci do miasta, z którego wyruszy?

4. W grafie pokazanym na rysunku zaznaczono skojarzenie (krawĊdzie

pogrubione). Za pomocą kolejnych dróg powiĊkszających wzglĊdem
skojarzenia wyznacz w tym grafie skojarzenie maksymalne.
Czy wyznaczone skojarzenie jest doskonałe? Odpowiedzi uzasadnij.
WskaĪ w grafie jakiekolwiek minimalne pokrycie krawĊdziowe.
Podaj ogólny związek liczby elementów w wyznaczonym skojarzeniu
i pokryciu.

1

2

5

4

8

11

7

10

3

6

9

5. Podaj, które z grafów pokazanych na rysunkach

są ze sobą izomorficzne, a które nie są.

G

1

G

2

G

3

G

4

G

5

G

6

6. RozwaĪ graf o liczbie wierzchołków n

≥

3 i jego dopełnienie. WyprowadĨ i podaj warunek dla stopni wierzchołków w

grafie, który zapewni, Īe w dopełnieniu tego grafu bĊdzie spełniony warunek dostateczny istnienia cyklu Hamiltona z
tw. Ore.

7. Rozstrzygnij z uzasadnieniem prawdziwoĞü nastĊpujących stwierdzeĔ:

1.

JeĪeli w grafie G istnieje cykl Eulera, to w grafie krawĊdziowym L(G) takĪe istnieje cykl Eulera.

2.

JeĪeli w grafie krawĊdziowym L(G) istnieje cykl Eulera, to w grafie G takĪe istnieje cykl Eulera.

8. Rozstrzygnij z uzasadnieniem, czy graf, którego zbiorem wierzchołków jest zbiór kodów Graya rzĊdu 3, a krawĊdzie

łączą dwa kody róĪniące siĊ dokładnie na jednej pozycji, jest grafem dwudzielnym.

9. W podanym grafie wyznacz:

a) maksymalną liczbĊ dróg krawĊdziowo rozłącznych pomiĊdzy parą

wierzchołków v i w,

b) minimalny zbiór krawĊdzi rozspajający te wierzchołki.

Zilustruj krawĊdziową wersjĊ tw. Mengera na powyĪszych zbiorach.
Rozstrzygnij z uzasadnieniem, czy ten graf jest 4-spójny krawĊdziowo?

b

a

c

v

w

e

d

f

h

g

j

10. Czy dla grafu o 9 wierzchołkach, w którym suma stopni wierzchołków wynosi 58 jego dopełnienie moĪe byü grafem

spójnym? OdpowiedĨ dokładnie uzasadnij bez konstruowania i rysowania grafu.