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.