Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Podstawowe poj˛ecia, oznaczenia
1.1
Sumy
Maj ˛
ac dany sko ´nczony ci ˛
ag
a
1
,
a
2
,...
a
k
, sum˛e jego elementów zapisujemy jako
k
X
i
=1
a
i
.
Niezbyt formalnie mo˙zemy to zapisa´c
k
X
i
=1
a
i
= a
1
+ a
2
+ · · · + a
k
.
Jako przykład zastosujmy symbol sumy do zapisu wzoru na sum˛e ci ˛
agu arytmetycznego).
k
X
i
=1
i = 1 + 2 + · · · + k =
(k + 1)k
2
(1.1)
oraz wzoru na sum˛e ci ˛
agu geometrycznego).
k
X
i
=0
x
i
= 1 + x + x
2
+ · · · + x
k
=
x
k
+1
− 1
x − 1
,
(1.2)
(wzór (1.2) jest słuszny dla ka˙zdego
x 6= 1)
B˛edziemy te˙z u˙zywa´c zapisu typu
X
1≤i≤6
a
i
= a
1
+ a
2
+ a
3
+ a
4
+ a
5
+ a
6
.
W tym przypadku zbiór indeksów okre´slony jest za pomoc ˛
a warunku pod znakiem sumy.
Warunek okre´slaj ˛
acy indeksy, po których nale˙zy sumowa´c mo˙ze by´c bardziej skompliko-
wany, na przykład
X
1
≤i≤6
i parzyste
a
i
= a
2
+ a
4
+ a
6
.
3
4
Rozdział 1. Podstawowe poj˛ecia, oznaczenia
Stosowa´c b˛edziemy tak˙ze zapis
X
i∈I
a
i
oznaczaj ˛
acy sum˛e tych elementów
a
i
, których indeksy nale˙z ˛
a do sko ´nczonego zbioru
indeksów
I. Na przykład, je˙zeli I = {1, 3, 5, 7}, to
X
i∈I
a
i
= a
1
+ a
3
+ a
5
+ a
7
.
Mo˙zemy te˙z sumowa´c ci ˛
agi, których elementy zale˙z ˛
a od dwóch indeksów,
X
1
≤i≤3
2
≤j≤3
a
ij
=
X
1≤i≤3
X
2≤j≤3
a
ij
a
12
+ a
13
+ a
22
+ a
23
+ a
32
+ a
33
.
Za pomoc ˛
a podwójnej sumy mo˙zemy, na przykład, przedstawi ´c uogólnione prawo roz-
dzielno´sci mno˙zenia wzgl˛edem dodawania:
X
1≤i≤m
a
i
·
X
1≤j≤n
b
j
=
X
1
≤i≤m
1
≤j≤n
a
i
b
j
(1.3)
a tak˙ze wzór na podnoszenie sumy do kwadratu:
X
1≤i≤m
a
i
2
=
X
1≤i≤m
a
2
i
+
X
1≤i<j≤m
2a
i
a
j
(1.4)
1.2
Iloczyny
Aby zapisa´c iloczyn elementów ci ˛
agu
a
1
,
a
2
,...,
a
k
, stosujemy zapis
k
Y
i
=1
a
i
.
Znów niezbyt formalnie mo˙zemy to zapisa´c jako
k
Y
i
=1
a
i
= a
1
· a
2
· · · · · a
k
.
1.3
Zbiory
∅ oznacza zbiór pusty, który nie zawiera ˙zadnych elementów.
N oznacza zbiór liczb naturalnych N
= {0, 1, 2, 3, . . .}.
Z oznacza zbiór liczb całkowitych.
1.3. Zbiory
5
Q oznacza zbiór liczb wymiernych.
R oznacza zbiór liczb rzeczywistych.
a ∈ A oznacza, ˙ze elment a nale˙zy do zbioru A, a /
∈ A, ˙ze elment a nie nale˙zy do
zbioru
A. Najprostszy sposób zdefiniowania zbioru polega na wypisaniu jego elementów
w nawiasach klamrowych. Na przykład zbiór
{1, 2, 3} zawiera elementy 1,2,3. Inny spo-
sób definiowania zbioru polega na podaniu własno´sci, któr ˛
a spełniaj ˛
a elementy zbioru.
Na przykład
{x | x ∈ N, 3 < x < 7} oznacza zbiór liczb naturalnych wi˛ekszych od 3 i
mniejszych od 7.
|A| oznacza moc zbioru A, czyli liczb˛e jego elementów.
|{3, 6, 9}| = 3,
|∅| = 0.
A ∪ B oznacza sum˛e zbiorów, czyli zbiór zawieraj ˛
acy elementy, które nale˙z ˛
a do
A lub do
B:
A ∪ B = {x : x ∈ A lub x ∈ B}.
A zatem suma
A ∪ B zawiera wszystkie elementy zbioru A i wszystkie elementy zbioru
B.
A ∩ B oznacza iloczyn lub przekrój zbiorów, czyli zbiór zawieraj ˛
acy elementy, które
nale˙z ˛
a do obu zbiorów naraz.
A ∩ B = {x : x ∈ A i x ∈ B}.
A − B oznacza ró˙znic˛e zbiorów, czyli zbiór zawieraj ˛
acy elementy, które nale˙z ˛
a do
A
i nie nale˙z ˛
a do
B.
A − B = {x : x ∈ A i x /
∈ B}.
Przykład 1.1 Dla
A = {1, 2, 4} i B = {1, 4, 6} mamy:
A ∪ B = {1, 2, 4, 6},
A ∩ B = {1, 4},
A − B = {2}.
A ⊆ B oznacza, ˙ze zbior A zawiera si˛e w zbiorze B, to znaczy wszystkie elementy zbioru
A nale˙z ˛
a do zbioru
B.
{2, 1} ⊆ {1, 2, 3}
Dwa zbiory s ˛
a równe je˙zeli zawieraj ˛
a te same elementy, lub inaczej
A = B wtedy i tylko
wtedy gdy
A ⊆ B i B ⊆ A.
{1, 4, 2, 3} = {4, 1, 3, 2}.
Jak wida´c kolejno´s´c elementów w zapisie zbioru nie ma znaczenia. I tak na przykład
{1, 2} = {2, 1}. Taki zbiór dwuelementowy nazywamy par ˛
a nieuporz ˛
adkowan ˛
a.
W poni˙zszym lemacie zebrano podstawowe własno´sci operacji sumy i iloczynu zbio-
rów.
Lemat 1.2
• A ∪ B = B ∪ A
(przemienno´s´c sumy).
• A ∩ B = B ∩ A
(przemienno´s´c iloczynu).
6
Rozdział 1. Podstawowe poj˛ecia, oznaczenia
• A ∪ (B ∪ C) = (A ∪ B) ∪ C
(ł ˛
aczno´s´c sumy).
• (A ∩ B) ∩ C = A ∩ (B ∩ C)
(ł ˛
aczno´s´c iloczynu).
• (A ∪ B) ∩ C = A ∩ C ∪ B ∩ C
(rozdzielno´s´c sumy wzgl˛edem iloczynu).
• (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C)
(rozdzielno´s´c iloczynu wzgl˛edem sumy).
• A ∪ ∅ = A,
A ∩ ∅ = ∅,
A ∪ A = A,
A ∩ A = A,
Dowód: Udowodnimy tylko rozdzielno´s´c sumy wzgl˛edem iloczynu. W tym celu poka˙ze-
my dwa zawierania:
(A ∪ B) ∩ C ⊂ A ∩ C ∪ B ∩ C oraz A ∩ C ∪ B ∩ C ⊂ (A ∪ B) ∩ C.
Aby udowodni´c zawieranie
(A ∪ B) ∩ C ⊂ A ∩ C ∪ B ∩ C, we˙zmy dowolny element
x ∈ (A ∪ B) ∩ C, wtedy x ∈ A ∪ B oraz x ∈ C, a to oznacza, ˙ze x nalezy do C i do
jednego ze zbiorów
A lub B (lub do obu), czyli nale˙zy do A ∩ C lub do B ∩ C, a wi˛ec
x ∈ A ∩ C ∪ B ∩ C. Pokazali´smy wi˛ec, ˙ze dowolny element z (A ∪ B) ∩ C nale˙zy do
A ∩ C ∪ B ∩ C.
Aby udowodni´c zawieranie
A ∩ C ∪ B ∩ C ⊂ (A ∪ B) ∩ C. we˙zmy dowolny element
x ∈ A ∩ C ∪ B ∩ C, wtedy x ∈ A ∩ C lub x ∈ B ∩ C, a to oznacza, ˙ze x nalezy do C
i do jednego ze zbiorów
A lub B (lub do obu), czyli nale˙zy do A ∪ B oraz do C, a wi˛ec
x ∈ (A ∪ B) ∩ C. Pokazali´smy wi˛ec, ˙ze dowolny element z A ∩ C ∪ B ∩ C nale˙zy do
(A ∪ B) ∩ C.
2
1.4
Ró˙znica symetryczna zbiorów
A ⊕ B oznacza ró˙znic˛e symetryczn ˛
a zbiorów, która zawiera elementy nale˙z ˛
ace tylko do
jednego z dwóch zbiorów:
A ⊕ B = (A − B) ∪ (B − A).
Przykład 1.3
{1, 2, 4} ⊕ {1, 4, 6} = {2, 6}.
W poni˙zszym lemacie zebrano podstawowe własno´sci ró˙znicy symetrycznej zbiorów.
Lemat 1.4
• A ⊕ B = B ⊕ A
(przemienno´s´c).
• (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
(ł ˛
aczno´s´c).
• (A ⊕ B) ∩ C = A ∩ C ⊕ B ∩ C
(rozdzielno´s´c wzgl˛edem iloczynu).
• A ⊕ ∅ = A,
A ⊕ A = ∅.
• Je˙zeli A ⊕ B = ∅, to A = B.
Dowód:
Udowodnimy, tylko dwie to˙zsamo´sci, dowód pozostałych pozostawiamy czytelnikowi
jako ´cwiczenie.
1.5. Iloczyn kartezja ´nski
7
Aby pokaza´c, ˙ze ró˙znica symetryczna jest ł ˛
aczna wystarczy zauwa˙zy ´c, ˙ze zbiór
A ⊕
(B⊕C) lub (A⊕B)⊕C zawiera te elementy, które nale˙z ˛
a do nieparzystej liczby zbiorów,
czyli te, które nale˙z ˛
a tylko do
A, B lub C, plus te, które nale˙z ˛
a do przekroju
A ∩ B ∩ C.
Udowodnimy teraz ostatni ˛
a implikacj˛e. Je˙zeli
A ⊕ B = ∅, to
A = A ⊕ ∅ = A ⊕ (A ⊕ B) = (A ⊕ A) ⊕ B = ∅ ⊕ B = B.
2
Twierdzenie 1.5 Ró˙znica symetryczna
n zbiorów:
A
1
⊕ A
2
⊕ . . . ⊕ A
n
zawiera elementy, które nale˙z ˛
a do nieparzystej liczby spo´sród zbiorów
A
1
,
A
2
, . . . , A
n
.
Dowód przez indukcj˛e ze wzgl˛edu na
n. Twierdzenie jest oczywiste dla n = 1 lub
n = 2. Załó˙zmy teraz, ˙ze jest ono prawdziwe dla n i rozpatrzmy:
A
1
⊕ . . . ⊕ A
n
⊕ A
n
+1
= (A
1
⊕ . . . ⊕ A
n
) ⊕ A
n
+1
.
Zbiór ten zawiera te elementy, które nale˙z ˛
a do
(A
1
⊕ . . . ⊕ A
n
) i nie nale˙z ˛
a do
A
n
+1
,
oraz te, które nie nale˙z ˛
a do
(A
1
⊕ . . . ⊕ A
n
) i nale˙z ˛
a do
A
n
+1
. W pierwszym przypad-
ku s ˛
a to elementy, które nie nale˙z ˛
a do
A
n
+1
i na mocy zało˙zenia indukcyjnego nale˙z ˛
a
do jakiej´s nieparzystej liczby zbiorów spo´sród
A
1
, . . . , A
n
. W drugim przypadku s ˛
a to
elementy, które nale˙z ˛
a do
A
n
+1
, a tak˙ze do pewnej parzystej liczby zbiorów spo´sród
A
1
, . . . , A
n
. Razem mamy wszystkie elementy nale˙z ˛
ace do nieparzystej liczby zbiorów
spo´sród
A
1
, . . . , A
n
+1
.
2
1.5
Iloczyn kartezja ´nski
Para uporz ˛
adkowana jest to dwuelementowy ci ˛
ag
(x, y). Mamy (x, y) = (u, v) wtedy i
tylko wtedy gdy
x = u oraz y = v. Dopuszczalne jest tak˙ze x = y.
A × B oznacza iloczyn kartezja´nski zbiorów A i B. Jest to zbiór wszystkich uporz ˛
ad-
kowanych par
(a, b), w których a ∈ A i b ∈ B. Inaczej
A × B = {(a, b) | a ∈ A, b ∈ B}.
Przykład 1.6 Dla
A = {1, 3, 5} i B = {3, 4} mamy
A × B = {(1, 3), (1, 4), (3, 3), (3, 4), (5, 3), (5, 4)}.
Mo˙zna łatwo wykaza´c, ˙ze
|A × B| = |A| · |B|.
8
Rozdział 1. Podstawowe poj˛ecia, oznaczenia
1.6
Rodzina zbiorów
Czasami b˛edziemy mieli do czynienia ze zbiorem, którego elementami s ˛
a zbiory. Przez
P(A)
lub
2
A
b˛edziemy oznacza´c zbiór wszystkich podzbiorów zbioru
A.
Przykład 1.7 Dla
A = {a, b}
P(A) = {∅, {a}, {b}, {a, b}}.
Zbiór zbiorów nazywamy czasami rodzin ˛
a zbiorów. Na przykład
A = {A
1
, A
2
, A
3
, A
4
}
jest rodzin ˛
a zawieraj ˛
ac ˛
a cztery zbiory
A
1
,
A
2
,
A
3
i
A
4
, s ˛
a to elementy zbioru
A. Mo˙zemy
te˙z zapisa´c
A = {A
i
| 1 ≤ i ≤ 4}.
Mo˙zemy sumowa´c zbiory z rodziny. Suma
k
[
i
=1
A
i
zawiera te elementy, które nale˙z ˛
a do którego´s ze zbiorów
A
1
,
A
2
, ... ,
A
k
, czyli
k
[
i
=1
A
i
= {x | ∃
i
1≤i≤k
x ∈ A
i
}.
Inaczej mo˙zemy to zapisa´c:
k
[
i
=1
A
i
= A
1
∪ A
2
∪ . . . ∪ A
k
.
B˛edziemy te˙z u˙zywa´c zapisu
[
i∈I
A
i
na oznaczenie sumy wszystkich zbiorów
A
i
, których indeksy nale˙z ˛
a do zbioru
I. Zacho-
dzi wtedy
[
i∈I
A
i
= {x | ∃
i∈I
x ∈ A
i
}.
Zbiór indeksów sumowania mo˙ze by´c okre´slony za pomoc ˛
a warunku.
[
1<i<6
A
i
= A
2
∪ A
3
∪ A
4
∪ A
5
.
Dla sumy zbiorów zachodzi prawo rozdzielno´sci sumy wzgl˛edem przekroju:
Lemat 1.8
C ∩
[
i∈I
A
i
=
[
i∈I
(C ∩ A
i
)
1.6. Rodzina zbiorów
9
Dowód: We´zmy dowolny element
x ∈ C ∩
S
i∈I
A
i
. Wtedy
x nale˙zy do C i do którego´s
ze zbiorów
A
i
, czyli dla jakiego´s
i ∈ I, x nale˙zy do C ∩A
i
, a to znaczy, ˙ze
x ∈
S
i∈I
(C ∩
A
i
).
We´zmy z kolei dowolny element
x ∈
S
i∈I
(C ∩ A
i
). Wtedy x nale˙zy do C ∩ A
i
dla jakiego´s
i ∈ I, czyli x nale´zy do C i do sumy
S
i∈I
A
i
, czyli nale˙zy do przekroju
C ∩
S
i∈I
A
i
.
2
Mo˙zemy te˙z bra´c przekroje zbiorów z rodziny. Przekrój
k
\
i
=1
A
i
zawiera te elementy, które nale˙z ˛
a do wszystkich zbiorów
A
1
,
A
2
, ... ,
A
k
, czyli
k
\
i
=1
A
i
= {x | ∀
i
1≤i≤k
x ∈ A
i
}.
Inaczej mo˙zemy to zapisa´c:
k
\
i
=1
A
i
= A
1
∩ A
2
∩ . . . ∩ A
k
.
B˛edziemy te˙z u˙zywa´c zapisu
\
i∈I
A
i
na oznaczenie przekroju wszystkich zbiorów
A
i
, których indeksy nale˙z ˛
a do zbioru
I.
Zachodzi wtedy
\
i∈I
A
i
= {x | ∀
i∈I
x ∈ A
i
}.
Zbiór indeksów przekroju mo˙ze by´c okre´slony za pomoc ˛
a warunku:
\
1<i<6
A
i
= A
2
∩ A
3
∩ A
4
∩ A
5
.
Przykład 1.9 We´zmy rodzin˛e zło˙zon ˛
a z trzech zbiorów
A
1
= {4, 6, 8}, A
2
= {4, 5, 6},
A
3
= {4, 5, 8, 9}.
3
[
i
=1
A
i
= {4, 5, 6, 8, 9},
3
\
i
=1
A
i
= {4}.
Przykład 1.10 Niech
I = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} b˛edzie zbiorem indeksów. Dla ka˙z-
dego
i ∈ I okre´slamy zbór A
i
= {x ∈ N | 1 ≤ x ≤ i}. Mamy:
[
i∈I
A
i
= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
\
i∈I
A
i
= {1},
[
1<i<7
A
i
= {1, 2, 3, 4, 5, 6},
\
1<i<7
A
i
= {1, 2}.
10
Rozdział 1. Podstawowe poj˛ecia, oznaczenia
1.7
Grafy (nieskierowane)
Definicja 1.11 Graf (nieskierowany)
G = (V, E) jest to para składaj ˛
aca si˛e ze sko´nczo-
nego zbioru wierzchołków
V oraz ze zbioru kraw˛edzi E, gdzie kraw˛edzie to pary wierz-
chołków.
E ⊆ {{u, v} | u, v ∈ V, u 6= v}.
O kraw˛edzi
e = {u, v} mówimy, ˙ze ł ˛
aczy wierzchołki
u i v, a o wierzchołkach u i v, ˙ze
s ˛
a ko´ncami kraw˛edzi
e. Wierzchołki poł ˛
aczone kraw˛edzi ˛
a nazywamy s ˛
asiednimi. Stopie´n
wierzchołka
v, oznaczany przez d(v), jest to liczba kraw˛edzi wychodz ˛
acych z
v.
Graf przedstawiamy na rysunku jako zbiór punktów (lub kółek) poł ˛
aczonych odcin-
kami (lub łukami).
Rysunek 1.1: Przykład grafu
a
b
c
d
e
f
g
Przykład 1.12 Rysunek 1.1 przedstawia graf
G = (V, E) ze zbiorem wierzchołków V =
{a, b, c, d, e, f, g} i zbiorem kraw˛edzi
E = {{a, b}, {a, d}, {a, e}, {a, g}, {b, c}, {c, g}, {c, f }, {d, f}, {e, f}, {f, g}}. Sto-
pie´n wierzchołków
a i f wynosi 4, wierzchołki c i g s ˛
a stopnia 3, wierzchołki
b, d i e
stopnia 2.
Graf
H = (V
H
, E
H
) nazywamy podgrafem grafu G = (V
G
, E
G
), je˙zeli V
H
⊆ V
G
oraz
E
H
⊆ E
G
.
Przykład 1.13 Graf przedstawiony na rysunku 1.3 jest podgrafem grafu z rysunku 1.1.
Graf pełny o
n wierzchołkach, oznaczany przez K
n
, jest to graf z
n wierzchołkami,
w którym ka˙zde dwa wierzchołki poł ˛
aczone s ˛
a kraw˛edzi ˛
a.
Droga lub ´scie˙zka w grafie
G = (V
G
, E
G
) jest to ci ˛
ag wierzchołków
v
0
, v
1
, . . . , v
k
,
taki, ˙ze dla ka˙zdego
i, 1 ≤ i ≤ k, wierzchołki v
i−
1
,
v
i
s ˛
a poł ˛
aczone kraw˛edzi ˛
a, czyli
{v
i−
1
, v
i
} ∈ E
G
. O drodze
v
0
, v
1
, . . . , v
k
mówimy, ˙ze ł ˛
aczy wierzchołki
v
0
i
v
k
. Mówi-
my tak˙ze, ˙ze wierzchołek
v
k
jest osi ˛
agalny z wierzchołka
v
0
. Droga jest zamkni˛eta je˙zeli
1.7. Grafy (nieskierowane)
11
Rysunek 1.2: Graf pełny
K
6
.
a
b
c
d
e
f
v
0
= v
k
. Droga jest prosta, je˙zeli wszystkie wyst˛epuj ˛
ace w niej wierzchołki s ˛
a ró˙zne.
Drog˛e
v
0
, v
1
, . . . , v
k
nazywamy cyklem je˙zeli
v
0
= v
k
,
k ≥ 3 oraz wszystkie wierzchołki
v
1
, . . . , v
k
s ˛
a ró˙zne.
Przykład 1.14 W grafie z rysunku 1.1 ci ˛
ag
e, a, d, a, b, c, g jest drog ˛
a, a ci ˛
ag
a, e,
f , d, a jest cyklem. Ci ˛
ag
a, e, f, d, a, b, c, g, a jest drog ˛
a zamkni˛et ˛
a, ale nie jest cyklem.
Graf
G jest spójny, je˙zeli dla ka˙zdych dwóch wierzchołków u, v ∈ V
G
istnieje ´scie˙zka
ł ˛
acz ˛
aca
u i v.
Lemat 1.15 Je˙zeli istnieje droga ł ˛
acz ˛
aca wierzchołki
u i v, u 6= v, to istnieje te˙z droga
prosta ł ˛
acz ˛
aca
u i v.
Dowód: Niech
u = v
0
, v
1
, . . . , v
k
= v, b˛edzie najkrótsz ˛
a drog˛e ł ˛
acz ˛
ac ˛
a
u i v. Droga
ta jest prosta. Przypu´s´cmy bowiem, ˙ze
v
i
= v
j
, dla jakiego´s
i < j; mieliby´smy wtedy
krótsz ˛
a drog˛e
u = v
0
, . . . , v
i
, v
j
+1
, . . . , v
k
= v, ł ˛
acz ˛
ac ˛
a
u i v, wbrew zało˙zeniu.
2
Dowolne dwa wierzchołki w cyklu mog ˛
a by´c poł ˛
aczone dwoma drogami prostymi.
Na przykład w cyklu
a, b, c, g, a na rysunku 1.1, wierzchołki a i c ł ˛
aczy droga
a, b, c oraz
droga
a, g, c. Tak, wi˛ec, je˙zeli w grafie s ˛
a cykle, to istniej ˛
a pary wierzchołkow, które s ˛
a
poł ˛
aczone dwoma drogami prostymi. Ale i na odwrót.
Lemat 1.16 Je˙zeli w grafie istniej ˛
a dwa wierzchołki
u i v, u 6= v które mo˙zna poł ˛
aczy´c
dwoma ró˙znymi drogami prostymi, to w grafie istnieje cykl.
Dowód: Niech
u = v
0
, v
1
, . . . , v
k
= v oraz u = w
0
, w
1
, . . . , w
l
= v, b˛ed ˛
a dwoma
ro˙znymi prostymi drogami ł ˛
acz ˛
acymi
u i v. Mo˙zemy zało˙zy´c, ˙ze v
1
6= w
1
(w przeciw-
nym przypadku mo˙zemy usun ˛
a´c wspólny pocz ˛
atek obu dróg). Niech
v
i
b˛edzie pierw-
szym wierzchołkiem po
v
0
, który wyst˛epuje w drodze
w
0
, w
1
, . . . , w
m
, i niech
v
i
= w
j
.
12
Rozdział 1. Podstawowe poj˛ecia, oznaczenia
Wierzchołki
v
1
, . . . , v
i−
1
nie wyst˛epuj ˛
a w drodze
w
0
, w
1
, . . . , w
m
i droga
v
0
, . . . , v
i
=
w
j
, w
j−
1
, . . . , w
1
, w
0
= v
0
tworzy cykl (w drodze tej wyst˛epuj ˛
a conajmniej trzy ró˙zne
wierzchołki
v
0
,
v
1
oraz
w
1
).
2
Z tego lematu wynika, ˙ze graf jest acykliczny (nie ma cykli) wtedy i tylko wtedy, gdy
ka˙zde dwa wierzchołki grafu mo˙zna poł ˛
aczy´c co najwy˙zej jedn ˛
a drog ˛
a prost ˛
a.
1.8
Drzewa
Definicja 1.17 Spójny i acykliczny (bez cykli) graf to drzewo.
Rysunek 1.3: Przykład drzewa
a
b
c
d
e
f
g
Z rozwa˙za´n z poprzedniego podrozdziału wynika:
Lemat 1.18 Graf jest drzewem wtedy i tylko wtedy, gdy ka˙zde dwa jego wierzchołki mo˙z-
na poł ˛
aczy´c dokładnie jedn ˛
a prost ˛
a drog ˛
a.
1.9
Drzewa ukorzenione
Definicja 1.19 Drzewo ukorzenione to drzewo z wyró˙znionym jednym wierzchołkiem.
Wyró˙zniony wierzchołek nazywamy korzeniem drzewa.
Ka˙zdy wierzchołek
v ró˙zny od korzenia jest z nim poł ˛
aczony dokładnie jedn ˛
a drog ˛
a
prost ˛
a. S ˛
asiad le˙z ˛
acy na drodze do korzenia nazywamy ojcem wierzchołka
v. Pozastali
s ˛
asiedzi s ˛
a synami wierzchołka
v. Korze ´n drzewa nie ma ojca, wszyscy jego s ˛
asiedzi s ˛
a
jego synami. Wierzchołek, który nie posiada syna nazywamy li´sciem.
Przykład 1.20 Je˙zeli w drzewie z rysunku 1.3 wyró˙znimy wierzchołek
d jako korze´n, to
ojcem wierzchołka
a jest wierzchołek d, synami wierzchołka a s ˛
a wierzchołki
e, g i b.
Wierzchołki
f , e, g oraz c s ˛
a li´sciami.
1.10. Grafy skierowane
13
Rysunek 1.4: Drzewo ukorzenione
d
f
a
e
g
b
c
Zwykle drzewo ukorzenione rysujemy tak jak na rysunku 1.4. Korze´n jest na górze,
poni˙zej le˙z ˛
a jego synowie i ogólnie ka˙zdy wierzchołek le˙zy poni˙zej swojego ojca i powy˙zej
swoich synów.
1.10
Grafy skierowane
Definicja 1.21 Graf skierowany (zorientowany) to dowolna para
G = (V, E), ze sko´n-
czonym zbiorem wierzchołków
V i zbiorem kraw˛edzi E ⊆ V × V .
Rysunek 1.5: Graf skierowany
a
b
c
d
e
W grafie skierowanym kraw˛ed´z
e = (u, v) jest skierowana od wierzchołka u do wierz-
chołka
v. Wierzchołek u nazywamy pocz ˛
atkiem kraw˛edzi, a wierzchołek
v ko ´ncem. Na
rysunkach kraw˛edzie skierowane b˛edziemy przedstawia ´c jako strzałki. Droga w grafie
skierowanym jest to ci ˛
ag wierzchołków
v
0
, v
1
, . . . , v
k
, taki, ˙ze dla ka˙zdego
i, 1 ≤ i ≤ k,
14
Rozdział 1. Podstawowe poj˛ecia, oznaczenia
wierzchołki
v
i−
1
,
v
i
s ˛
a poł ˛
aczone kraw˛edzi ˛
a, czyli
(v
i−
1
, v
i
) ∈ E. Kraw˛ed´z typu (u, u),
w której pocz ˛
atek i koniec pokrywaj ˛
a si˛e, nazywamy p˛etl ˛
a.
1.11
Słowa
Słowa s ˛
a to ci ˛
agi liter lub symboli z jakiego´s sko´nczonego zbioru
Σ. Zbiór Σ nazywamy
wtedy alfabetem. Zbiór wszystkich słów nad alfabetem
Σ oznaczamy przez
Σ
∗
.
W´sród słów wyró˙zniamy słowo puste
λ, które nie zawiera ˙zadnych liter.
Przykład 1.22 Na przykład, je˙zeli
Σ = {a, b}, to Σ
∗
zawiera słowo puste
λ, dwa słowa
jednoliterowe
a i b, cztery słowa dwuliterowe aa, ab, ba i bb, osiem słów trzyliterowych
aaa, aab, aba i abb, baa, bab, bba i bbb, i tak dalej.
Długo´s´c słowa
w ∈ Σ jest to liczba jego liter, b˛edziemy j ˛
a oznacza ´c przez
|w|. Dłu-
go´s´c słowa pustego
|λ| = 0. Zbiór wszystkich słów długo´sci n nad alfabetem Σ oznacza-
my przez
Σ
n
.
Dla słów mo˙zemy okre´sli´c operacj˛e konkatenacji, lub składania słów. Konkatenacja (lub
zło˙zenie) dwóch słów
u, v ∈ Σ, oznaczana przez uv, jest to sklejenie słów u i v. Do słowa
u dopisujemy na ko´ncu słowo v. Dla dowolnego słowa v ∈ Σ
∗
zachodzi
λv = vλ = v.
Przykład 1.23 Konkatenacja słów
u = aaba i v = abba to sówo uv = aabaabba.
Słowo
u jest prefiksem lub przedrostkiem słowa v, je˙zeli istnieje takie słowo w, ˙ze
v = uw. Podobnie, słowo u jest sufiksem lub przyrostkiem słowa v, je˙zeli istnieje takie
słowo
w, ˙ze v = wu.
Przykład 1.24 Na przykład
aba jest prefiksem słowa abaaab, a słowo ab jest sufiksem
słowa
abaaab. Słowo puste jest prefixem i sufiksem dowolnego słowa v. Ka˙zde słowo v
jest swoim własnym prefiksem i sufiksem.
Zwykle alfabet jest zbiorem uporz ˛
adkowanym, lub mówi ˛
ac inaczej mamy pewn ˛
a ko-
lejno´s´c liter w alfabecie. Na przykład w zbiorze
Σ = {a, b} litera a stoi przed b. Mo˙zemy
wtedy uporz ˛
adkowa´c zbiór słów nad alfabetem
Σ.
Jeden porz ˛
adek nazywa si˛e porz ˛
adkiem leksykograficznym. Jest to porz ˛
adek słów w
słownikach. Aby porówna´c dwa słowa
u, v ∈ Σ, szukamy pierwszej pozycji, na której te
dwa słowa si˛e ró˙zni ˛
a. Słowo, które ma na tej pozycji wcze´sniejsz ˛
a liter˛e, jest wcze´sniejsze
w porz ˛
adku leksykograficznym. Je˙zeli takiej pozycji nie ma, to albo
u = v, albo jedno
ze słów jest prefiksem drugiego, wtedy wcze´sniejszy w porz ˛
adku leksykograficznym jest
prefiks.
Przykład 1.25 W porz ˛
adku leksykograficznym słowo
ab jest wcze´sniejsze od słowa ababa,
a to jest wcze´sniejsze od
abb.
1.12. Zaokr ˛
aglenia
15
Porz ˛
adek leksykograficzny jest wygodny, je˙zeli zbiór słów jest sko ´nczony. Zauwa˙zmy, ˙ze
w zbiorze wszystkich słów
{a, b}
∗
niesko´nczenie wiele słów (wszystkie słowa zło˙zone
tylko z litery
a) poprzedza słowo b. Dlatego czasami stosuje si˛e inny porz ˛
adek, tak zwany
porz ˛
adek kanoniczny.
Słowo
u poprzedza słowo v w porz ˛
adku kanonicznym, je˙zeli:
• albo |u| < |v|,
• albo |u| = |v| i u poprzedza v w porz ˛
adku leksykograficznym.
Przykład 1.26 Pocz ˛
atkowe słowa zbioru
{a, b}
∗
uporz ˛
adkowane według porz ˛
adku kano-
nicznego to:
λ, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, . . .
1.12
Zaokr ˛
aglenia
Wprowad´zmy dwa oznaczenia na zaokr ˛
aglenie liczby rzeczywistej. Dla dowolnej liczby
rzeczywistej
x
dxe oznacza zaokr ˛
aglenie
x w gór˛e do najbli˙zszej liczby całkowitej.
bxc oznacza zaokr ˛
aglenie
x w dół do najbli˙zszej liczby całkowitej.
Zaokr ˛
aglenie
dxe nazywamy sufitem z x, a zaokr ˛
aglenie
bxc nazywamy podłog ˛
a z
x.
Przykład 1.27
d4e = 4,
d4.3e = 5,
d−4e = −4,
d−4.3e = −4.
b4c = 4,
b4.3c = 4,
b−4c = −4,
b−4.3c = −5.
1.13
Przedrostki
W przypadku bardzo du˙zych lub bardzo małych warto´sci u˙zywa si˛e czasami jednostek
miar b˛ed ˛
acych wielokrotno´sciami lub podwielokrotno´sciami podstawowych jednostek.
Takie jednostki wyra˙za si˛e przez dodanie do nazwy jednostki odpowiedniego przedrostka,
a do oznaczenia tej jednostki dodaje si˛e oznaczenie przedrostka. W nast˛epuj ˛
acej tabeli
zebrano te przedrostki.
16
Rozdział 1. Podstawowe poj˛ecia, oznaczenia
Przedrostek
Oznaczenie
Wielokrotno´s´c
exa
E
10
18
peta
P
10
15
tera
T
10
12
giga
G
10
9
mega
M
10
6
kilo
k
10
3
hekto
h
10
2
deka
da
10
Przedrostek
Oznaczenie
Podwielokrotno´s´c
decy
d
10
−
1
centy
c
10
−
2
mili
m
10
−
3
mikro
µ
10
−
6
nano
n
10
−
9
piko
p
10
−
12
femto
f
10
−
15
atto
a
10
−
18
Przykładami tak utworzonych jednostek s ˛
a: centymetr (cm), milimetr (mm), hehtopa-
skal, hektolitr, kilogram (kg), kilowat (kW). Do mierzenia pr˛edko´sci (zegara) procesora
u˙zywa si˛e megahertzów. Jeden megahertz (MHz) to jednostka cz˛esto´sci równa miliono-
wi impulsów na sekund˛e. Kilobajtów, megabajtów i gigabajtów u˙zywa si˛e do mierzenia
liczby komórek pami˛eci. Cz˛esto przyjmuje si˛e, ˙ze kilobajt ma
1024 bajtów, megabajt
1024 × 1024 bajtów, a gigabajt 1024 × 1024 × 1024 bajtów.
1.14
Notacja asymptotyczna
W analizie jakiego´s algorytmu (programu) wa˙zne jest oszacowanie jego czasu działania.
Jako przykład we´zmy algorytm sortowania b ˛
abelkowego, który ustawia elementy ci ˛
agu
wej´sciowego w porz ˛
adku niemalej ˛
acym.
Algorytm sortowania b ˛
abelkowego.
Dane wej´sciowe: ci ˛
ag
a
1
,
a
2
, ... ,
a
n
.
Dane wyj´sciowe: elementy ci ˛
agu w porz ˛
adku niemalej ˛
acym.
n − 1 razy wykonuj
(1) wska˙z na pierwszy element,
(2)
n − 1 razy wykonuj:
(2a) porównaj wskazany element z elementem nast˛epnym,
(2b) je˙zeli porównane elementy s ˛
a w niewła´sciwej kolejno´sci,
to zamie´n je miejscami,
(2c) wska˙z na nast˛epny element.
W poni˙zszej tabeli zilustrowano zastosowanie algorytmu dla ci ˛
agu
(3, 4, 1, 2).
1.14. Notacja asymptotyczna
17
ˆ
3
4
1
2
3
ˆ
4
1
2
3
1
ˆ
4
2
ˆ
3
1
2
4
1
ˆ
3
2
4
1
2
ˆ
3
4
ˆ
1
2
3
4
1
ˆ
2
3
4
1
2
ˆ
3
4
Kolejne wiersze przedstawiaj ˛
a ci ˛
ag po kolejnych porównaniach. Element aktualnie wska-
zany jest zaznaczony daszkiem.
Poprawno´s´c powy˙zszego algorytmu wynika z faktu, ˙ze po pierwszym wykonaniu ze-
wn˛etrznej p˛etli (instrukcje (1) i (2)) najwi˛ekszy element ci ˛
agu znajdzie si˛e na ko ´ncu, po
drugim wykonaniu p˛etli drugi najwi˛ekszy element ci ˛
agu znajdzie si˛e na przedostatniej
pozycji, i tak dalej. Po ka˙zdym kolejnym wykonaniu p˛etli kolejny najwi˛ekszy element
znajdzie swoj ˛
a wła´sciw ˛
a pozycj˛e. Czas działania algorytmu zale˙zy od
n — liczby ele-
mentów w ci ˛
agu. P˛etla zewn˛etrzna (instrukcje (1) i (2)) jest wykowywana
n − 1 razy.
W ka˙zdej iteracji p˛etli zewn˛etrznej p˛etla wewn˛etrzna (instrukcje (2a), (2b) i (2c)) rów-
nie˙z jest wykonywana
n − 1 razy. W ka˙zdym kolejnym wykonaniu p˛etli wewn˛etrznej
algorytm wykonuje kilka kroków. Tak wi˛ec, aby posortowa ´c ci ˛
ag długo´sci
n algorytm w
sumie wykonuje
c(n − 1)
2
kroków, gdzie
c jest pewn ˛
a stał ˛
a.
Czas pracy powy˙zszego algorytmu został oszacowany z dokładno´sci ˛
a do stałej. Jest
to powszechna praktyka i b˛edziemy tak post˛epowa´c w tej ksi ˛
a˙zce. Do szacowania czasu
pracy algorytmu (jego zło˙zono´sci czasowej) i do porównywania algorytmów pod wzgl˛e-
dem czasu działania b˛edziemy u˙zywa´c notacji asymptotycznej. Niech
f i g b˛ed ˛
a dwiema
funkcjami okre´slonymi na zbiorze liczb naturalnych o warto´sciach w zbiorze dodatnich
liczb rzeczywistych
f, g : N → {x|x ∈ R, x > 0}.
Wtedy:
• g(n) = O(f (n)), je˙zeli istnieje dodatnia stała c > 0 taka, ˙ze g(n) ≤ c · f (n)
dla prawie wszystkich
n ∈ N, to znaczy istnieje n
0
, takie, ˙ze
g(n) ≤ c · f (n) dla
ka˙zdego
n ≥ n
0
. W takim przypadku mówimy, ˙ze funkcja
g jest O du˙ze od f .
• g(n) = o(f (n)), je˙zeli lim
n→∞
g
(n)
f
(n)
= 0. W takim przypadku mówimy, ˙ze funk-
cja
g jest o małe od f .
• g(n) = Ω(f (n)), je˙zeli istnieje dodatnia stała c > 0 taka, ˙ze g(n) ≥ c · f (n) dla
prawie wszystkich
n ∈ N. W takim przypadku mówimy, ˙ze funkcja g jest Omega
du˙ze od
f .
• g(n) = Θ(f (n)), je˙zeli istniej ˛
a dwie dodatnie stałe
c
1
, c
2
> 0 takie, ˙ze c
1
· f (n) ≤
g(n) ≤ c
2
· f (n) dla prawie wszystkich n ∈ N. W takim przypadku mówimy, ˙ze
funkcja
g jest Theta du˙ze od f .
18
Rozdział 1. Podstawowe poj˛ecia, oznaczenia
Je˙zeli
g(n) = O(f (n)), to mówimy, ˙ze funkcja f ogranicza z góry funkcj˛e g(n) (z
dokładno´sci ˛
a do stałej), albo, ˙ze rz ˛
ad funkcji
g jest nie wi˛ekszy od rz˛edu funkcji f .
Przykład 1.28
• Czas działania algorytmu sortowania b ˛
abelkowego jest
O(n
2
).
• n = O(3n − 2).
• 3n − 2 = O(n).
• n
3
+ n
2
− n = O(n
3
).
• n
3
= O(2
n
).
• n
2
log n = O(n
3
).
B˛edziemy dopuszcza´c notacj˛e asymptotyczn ˛
a tak˙ze wobec funkcji, które s ˛
a dodatnie
dla prawie wszystkich liczb naturalnych. Na przykład
n
2
− 3n = O(n
2
).
Je˙zeli
g(n) = o(f (n)), to mówimy, ˙ze g jest ni˙zszego rz˛edu ni˙z f .
Przykład 1.29
• n
2
= o(n
3
).
• n = o(n log n).
• n
3
= o(2
n
).
Je˙zeli
g(n) = Θ(f (n)), to g i f s ˛
a tego samego rz˛edu, czyli
g(n) = O(f (n)) oraz
f (n) = O(g(n)).
Przykład 1.30
• n
2
= Θ(n
2
+ n).
• n = Θ(n + log n).
Nast˛epuj ˛
acy lemat jest bardzo u˙zyteczny przy szacowaniu asymptotycznym. Jego do-
wód zostawiamy jako ´cwiczenie.
Lemat 1.31 Je˙zeli granica
lim
g
(n)
f
(n)
istnieje i jest wła´sciwa (nie jest równa
∞), to g(n) =
O(f (n)).
Wniosek 1.32 Je˙zeli
g(n) = o(f (n)), to g(n) = O(f (n)).
Nast˛epuj ˛
acy przykład pokazuje, ˙ze oszacowanie asymptotyczne mo˙ze by ´c czasem zawod-
ne.
Przykład 1.33 We´zmy dwie funkcje
f (n) = 300n oraz g(n) = n log
2
n. Mamy f (n) =
o(g(n)), ale f (n) ≥ g(n) dla wszystkich n ≤ 2
300
, czyli dla wszystkich liczb mniejszych
od liczby atomów w naszej galaktyce (porównaj podrozdział du˙ze liczby w rozdziale o
arytmetyce).
1.15. Wielomiany
19
Z drugiej jednak strony oszacowanie asymptotyczne wystarczy do naszych celów i
jest łatwiejsze do uzyskania.
Przykład 1.34 Rozwa˙zmy trzy algorytmy: pierwszy działaj ˛
acy w czasie
f
1
(n) = c
1
n,
drugi w czasie
f
2
(n) = c
2
n
3
i trzeci w czasie
f
3
(n) = c
3
2
n
. Funkcje te okre´slaj ˛
a czas
działania na pewnym konkretnym komputerze. Niech
n
1
,
n
2
i
n
3
oznazczaj ˛
a długo´sci
wej´s´c, dla których algorytmy daj ˛
a odpowied´z w ci ˛
agu jednej sekundy, to znaczy
f
1
(n
1
) =
f
2
(n
2
) = f
3
(n
3
) = 1s.
Przypu´s´cmy teraz, ˙ze mamy 1000 razy szybszy komputer i pytamy jakie wej´scia teraz
mog ˛
a by´c policzone przez te algorytmy w ci ˛
agu jednej sekundy.
Dla pierwszego algorytmu działaj ˛
acego w czasie liniowym mo˙zemy teraz oblicza´c
1000 razy dłu˙zsze dane wej´sciowe, poniewa˙z
f
1
(1000n
1
) = 1000f
1
(n
1
). Dla drugie-
go algorytmu działaj ˛
acego w czasie sze´sciennym mo˙zemy teraz oblicza´c 10 razy dłu˙zsze
dane wej´sciowe, poniewa˙z
f
2
(10n
2
) = 1000f
2
(n
2
). Dla trzeciego algorytmu działaj ˛
a-
cego w czasie wykładniczym mo˙zemy teraz oblicza´c tylko dane wej´sciowe o 10 dłu˙zsze,
poniewa˙z
f
3
(n
3
+ 10) = 1024f
3
(n
3
).
1.15
Wielomiany
Wielomian jest to funkcja postaci
P (x) = a
n
· x
n
+ · · · + a
0
,
gdzie
x jest zmienn ˛
a rzeczywist ˛
a, a
a
0
,
a
1
, ... ,
a
n
s ˛
a stałymi rzeczywistymi, nazywanymi
współczynnikami wielomianu. Stopniem wielomianu
P (x) jest najwi˛eksze takie k, ˙ze
a
k
6= 0, stopie´n oznaczamy, przez st(W (x)). Zwykle pisz ˛
ac
P (x) = a
n
· x
n
+ · · · + a
0
b˛edziemy zakłada´c, ˙ze
a
n
6= 0, czyli ˙ze stopie´n st(P (x)) = n. U˙zywaj ˛
ac symbolu sumy
wielomian mo˙zemy przedstawi´c w nast˛epuj ˛
acy sposób:
P (x) =
n
X
i
=0
a
i
x
i
.
Wielomian, którego wszystkie współczynniki s ˛
a równe zeru nazywamy wielomianem ze-
rowym. Dwa wielomiany
P (x) =
P
n
i
=0
a
i
x
i
oraz
Q(x) =
P
n
i
=0
b
i
x
i
s ˛
a równe je˙zeli
maj ˛
a takie same wspólczynniki, to znaczy je˙zeli
a
i
= b
i
dla ka˙zdego
i.
Wielomiany mo˙zna dodawa´c, odejmowa´c lub mno˙zy´c. Suma, ró˙znica i iloczyn wie-
lomianów
P (x) i Q(x) okre´slone s ˛
a nast˛epuj ˛
aco:
• P (x) + Q(x) =
P
n
i
=0
(a
i
+ b
i
)x
i
,
• P (x) − Q(x) =
P
n
i
=0
(a
i
− b
i
)x
i
,
• P (x) · Q(x) =
P
2n
i
=0
c
i
x
i
,
gdzie
c
i
=
P
i
k
=0
a
k
· b
i−k
oraz
a
k
= 0 i b
k
= 0
dla wszystkich
k > n.
20
Rozdział 1. Podstawowe poj˛ecia, oznaczenia
Wzór na iloczyn wielomianów wygl ˛
ada skomplikowanie, ale jest on równowa˙zny szkol-
nemu sposobowi mno˙zenia wielomianów, gdzie wyrazy (jednomiany) obu wielomianów
wymna˙za si˛e ka˙zdy z ka˙zdym a nast˛epnie grupuje wyrazy według wykładników. Wielo-
mian
P (x) mo˙zna pomno˙zy´c przez stał ˛
a
a
a · P (x) =
n
X
i
=0
a · a
i
x
i
.
Przykład 1.35 Niech
P (x) = x
2
+ 2x + 1 oraz Q(x) = 2x
2
+ x. Wtedy
P (x) + Q(x) = 3x
2
+ 3x + 1
P (x) · Q(x) = 2x
4
+ 5x
3
+ 4x
2
+ x
3 · P (x) = 3x
2
+ 6x + 3
1.15.1
Dzielenie wielomianów
Wielomiany mo˙zna te˙z dzieli´c. Mamy
Twierdzenie 1.36 Dla dowolnych dwóch wielomianów
W (x) i V (x) istniej ˛
a dwa wielo-
miany
Q(x) i R(x) takie ˙ze
(a)
W (x) = V (x) · Q(x) + R(x)
(b)
st(R(x)) < st(V (x))
Wielomian
Q(x) nazywamy ilorazem a R(x) reszt ˛
a z dzielenia
W (x) przez V (x). Iloraz
i reszta s ˛
a wyznaczone jednoznacznie, to znaczy istnieje tylko jedna para
Q(x), R(x)
spełniaj ˛
aca warunki (a) i (b).
Dowód: Najpierw przedstawimy
Algorytm dzielenia wielomianów
Dane wej´sciowe: Dwa wielomiany
W (x) = a
n
x
n
+· · ·+a
0
oraz
V (x) = b
m
x
m
+· · ·+b
0
.
Zakładamy przy tym, ˙ze
a
n
6= 0 i b
m
6= 0, czyli ˙ze W (x) jest stopnia n, a V (x) jest
stopnia
m.
Dane wyj´sciowe: iloraz
Q(x) oraz reszta R(x)
Podstaw
Q(x) := 0 oraz R(x) := W (x);
dopóki
st(R(x)) = k ≥ m wykonuj:
Niech
c
k
x
k
b˛edzie składnikiem
R(x) z najwy˙zszym wykładnikiem.
Podziel
c
k
x
k
przez
b
m
x
m
.
Podstaw
Q(x) := Q(x) +
c
k
b
m
x
k−m
Podstaw
R(x) := R(x) −
c
k
b
m
x
k−m
· V (x)
Je˙zeli
st(R(x)) < m, to
koniec, para
Q(x), R(x) spełnia warunki (a) i (b).
1.15. Wielomiany
21
Aby udowodni´c, ˙ze przedstawiony algorytm poprawnie oblicza iloraz i reszt˛e, poka-
˙zemy, przez indukcj˛e, ˙ze warunek (a) jest spełniony po ka˙zdym kolejnym wykonaniu p˛etli
dopóki. Na pocz ˛
atku welomiany
Q(x) = 0 oraz R(x) = W (x) spełniaj ˛
a warunek (a).
Oznaczmy warto´sci wielomianów
Q(x) i R(x) przed i -tym wykonaniem p˛etli dopóki
przez
Q
1
(x) i R
1
(x), a warto´sci po i -tym wykonanu p˛etli przez Q
2
(x) i R
2
(x). Zakła-
damy przy tym, ˙ze
W (x) = V (x) · Q
1
(x) + R
1
(x), ˙ze stopie´n st(R
1
(x)) ≥ m, oraz ˙ze
c
k
x
k
jest składnikiem
R
1
(x) z najwie˛ekszym wykładnikiem. W trakcie i-tego wykonania
p˛etli nast ˛
api ˛
a podstawienia
Q
2
(x) := Q
1
(x) +
c
k
b
m
x
k−m
oraz
R
2
(x) := R
1
(x) −
c
k
b
m
x
k−m
· V (x).
Mamy teraz
R
1
(x) :=
c
k
b
m
x
k−m
· V (x) + R
2
(x)
oraz
W (x) = Q
1
(x)·V (x)+R
1
(x) = (Q
1
(x)+
c
k
b
m
x
k−m
)·V (x)+R
2
(x) = Q
2
(x)·V (x)+R
2
(x),
czyli
Q(x) oraz R(x) spełniaj ˛
a warunek (a) po
i tym wykonaniu p˛etli.
Zauwa˙zmy, ˙ze stopie ´n wielomianu
R
2
(x) jest mniejszy od stopnia wielomianu R
1
(x),
poniewa˙z w wielomianie
R
2
(x) = R
1
(x) −
c
k
b
m
x
k−m
· V (x). współczynnik przy x
k
jest
równy
0 i stopie´n st(R
2
(x)) < k. Tak wi˛ec p˛etla (3) nie mo˙ze si˛e wykonywa´c wi˛ecej ni˙z
n − m razy. Po wyj´sciu z p˛etli stopie´n st(R(x) < st(V (x)), czyli spełniony jest warunek
(b).
Pokazali´smy wi˛ec, ˙ze wielomian
W (x) mo˙zna przedstawi´c w postaci W (x) = Q(x) ·
V (x) + R(x) tak, ˙zeby st(R(x)) < st(V (x)). Teraz poka˙zemy, ˙ze iloraz Q(x) i reszta
R(x) s ˛
a wyznaczone jednoznacznie. Przypu´s´cmy bowiem, ˙ze
W (x) = Q
1
(x)V (x) + R
1
(x)
oraz
W (x) = Q
2
(x)V (x) + R
2
(x)
i ˙ze
st(R
1
(x)), st(R
2
(x)) < st(V (x)). Po odj˛eciu tych równo´sci stronami otrzymamy
0 = (Q
1
(x) − Q
2
(x))V (x) + (R
1
(x) − R
2
(x)).
Je˙zeli wielomiany
Q
1
(x) 6= Q
2
(x), to wielomian (Q
1
(x) − Q
2
(x))V (x) ma stopie´n
wi˛ekszy lub równy od
st(V (x)), a wielomian R
1
(x) − R
2
(x) ma stopie´n mniejszy od
st(V (x)), wi˛ec ich suma nie mo˙ze by´c wielomianem zerowym. Doszli´smy wi˛ec do sprzecz-
no´sci, czyli
Q
1
(x) = Q
2
(x), z tego za´s wynika, ˙ze R
1
(x) = R
2
(x).
Przykład 1.37 Podzielmy wielomian
W (x) = 8x
3
+ 6x
2
+ 3x + 2 przez wielomian
V (x) = 2x − 1 według opisanego wy˙zej algorytmu.
22
Rozdział 1. Podstawowe poj˛ecia, oznaczenia
Najpierw podstawiamy
Q(x) := 0 oraz R(x) := 8x
3
+ 6x
2
+ 3x + 2. Poniewa˙z
st(R(x)) = 3 > 1 = st(V (x)) przechodzimy do p˛etli dopóki Dzielimy składnik 8x
3
przez
2x otrzymuj ˛
ac
4x
2
i podstawiamy
R(x) := R(x) − 4x
2
V (x) = 8x
3
+ 6x
2
+ 3x + 2 − 4x
2
(2x − 1) = 10x
2
+ 3x + 2.
oraz
Q(x) := Q(x) + 4x
2
= 4x
2
.
Zauwa˙zmy, ˙ze spełniony jest warunek
W (x) = Q(x) · V (x) + R(x).
Poniewa˙z
st(R(x)) jest wi˛ekszy od 1 wykonujemy ponownie instrukcje p˛etli. Dzielimy
składnik
10x
2
przez
2x otrzymuj ˛
ac
5x i podstawiamy
R(x) := R(x) − 5xV (x) = 10x
2
+ 3x + 2 − 5x(2x − 1) = 8x + 2.
oraz
Q(x) := Q(x) + 5x = 4x
2
+ 5x.
(warunek
W (x) = Q(x) · V (x) + R(x) jest spełniony).
Stopie´n
st(R(x)) jest równy 1, wi˛ec wykonujemy ponownie instrukcje p˛etli. Dzielimy
składnik
8x przez 2x otrzymuj ˛
ac
4 i podstawiamy
R(x) := R(x) − 4V (x) = 8x + 2 − 4(2x − 1) = 6.
oraz
Q(x) := Q(x) + 4 = 4x
2
+ 5x + 4.
Warunek
W (x) = Q(x) · V (x) + R(x) jest spełniony i teraz stopie´n st(R(x)) = 0 < 1
wi˛ec algorytm ko´nczy prac˛e. Wielomian
Q(x) = 4x
2
+ 5x + 2 jest ilorazem a wielomian
R(x) = 6 reszt ˛
a.
1.15.2
Schemat Horna
Aby obliczy´c warto´s´c wielomianu
P (x) w jakim´s konkretnym punkcie x
0
mogliby´smy
bezpo´srednio skorzysta´c ze wzoru
P (x
0
) =
P
n
i
=0
a
i
x
i
0
. W ten sposób potrzebujemy, w
najgorszym przypadku, około
n
2
mno˙ze´n. Istnieje jednak sposób wymagaj ˛
acy tylko
n
mno˙ze´n. Nale˙zy oblicza´c warto´s´c wielomianu według schematu
P (x
0
) = ((. . . (a
n
· x
0
+ a
n−
1
) · x
0
+ a
n−
2
) · x
0
+ · · · a
1
) · x
0
+ a
0
.
Jest to tak zwany schemat Horna. Dokładniej mo˙zemy go przedstawi ´c nast˛epuj ˛
aco:
Algorytm obliczania warto´sci wielomianu, schemat Horna
Dane wej´sciowe: współczynniki
a
0
,
a
1
, ... ,
a
n
wielomianu
P (x) = a
n
· x
n
+ · · · + a
0
oraz argument
x
0
.
Dane wyj´sciowe: warto´s´c wielomianu
y
0
= P (x
0
) = a
n
x
n
0
+ · · · + a
1
x
0
+ a
0
.
y
0
:= a
n
;
dla kolejnych
i od 1 do n wykonuj
y
0
:= y
0
· x
0
+ a
n−i
1.16. Zadania
23
1.15.3
Pierwiastki wielomianu
Pierwiastkiem wielomianu
W (x) jest ka˙zda liczba rzeczywista a, która podstawiona do
wielomianu da warto´s´c
W (a) = 0. Zachodzi
Twierdzenie 1.38 (Bézout) Liczba
a jest pierwiastkiem wielomianu W (x) wtedy i tylko
wtedy, gdy
W (x) dzieli si˛e przez x−a, czyli, gdy istnieje wielomian Q(x) taki, ˙ze W (x) =
Q(x)(x − a).
Dowód: Je˙zeli
W (x) = Q(x)(x − a), to W (a) = Q(a)(a − a) = 0.
Niech teraz
W (a) = 0. Podzielmy W (x) przez x − a, otrzymamy
W (x) = Q(x)(x − a) + R(x)
przy czym stopie ´n
R(x) jest mniejszy od 1, czyli jest stał ˛
a
R(x) = r. Wstawiaj ˛
ac teraz
a
do obu stron otrzymamy
0 = Q(a)(a − a) + r,
czyli
r = 0 i W (x) = Q(x)(x − a).
2
Wniosek 1.39 Je˙zeli wielomian nie jest to˙zsamo´sciowo równy zero, to liczba jego pier-
wiastków nie jest wi˛eksza od jego stopnia.
Dowód: Niech
a
1
,...,
a
k
b˛ed ˛
a ró˙znymi pierwiastkami wielomianu
W (x). Z twierdzenia
Bézout mamy
W (x) = Q
1
(x)(x − a
1
). Po podstawieniu a
2
mamy
0 = W (a
2
) =
Q
1
(a
2
)(a
2
− a
1
), czyli a
2
, jest pierwiastkiem wielomianu
Q
1
(x). Korzystaj ˛
ac znowu
z twierdzenia Bézout otrzymamy
W (x) = Q
2
(x)(x − a
2
)(x − a
1
), i tak dalej. W ko´ncu
otrzymamy, ˙ze
W (x) jest postaci W (x) = Q(x)(x − a
k
) · · · (x − a
2
)(x − a
1
), czyli
stopie´n
W (x) musi by´c wi˛ekszy od k.
1.16
Zadania
1. Oblicz: a)
P
4
i
=1
i2
i
,
b)
P
3
k
=1
k
3
,
c)
P
4
n
=1
(n
2
−1), d)
P
3
i
=1
P
2
j
=1
ij
2
,
e)
P
2
k
=1
P
4
n
=1
(k − n),
2. Oblicz: a)
Q
5
i
=1
(i + 1), b)
Q
4
k
=1
(2k + 1), c)
Q
4
n
=1
(n
2
− 1).
3. Niech
A = {1, 2, 3, 4, 5}, B = {1, 3, 5, 7} i C = {4, 5, 6, 7, 8}. Oblicz A ∪ B ∪ C,
A ∩ B ∩ C, A − B, A ∩ (B − C), A ⊕ B, A ⊕ B ⊕ C.
4. Niech
I = {1, 2, 3, 4, 5} b˛edzie zbiorem indeksów. Dla ka˙zdego i ∈ I okre´slamy
zbór
B
i
= {x ∈ N | i ≤ x ≤ 2i}. Oblicz
S
i∈I
B
i
,
T
i∈I
B
i
,
B
1
⊕ B
3
⊕ B
5
oraz
B1 ⊕ B
2
⊕ B
3
⊕ B
4
⊕ B
5
.
5. Niech
I = {1, 2, 3, 4, 5}. Dla ka˙zdego i ∈ I mamy A
i
= {3i − 3, 3i, 3i + 3}.
Oblicz
S
i∈I
A
i
,
T
i∈I
A
i
, oraz
A
1
⊕ A
2
⊕ B
3
⊕ B
4
⊕ A
5
.
24
Rozdział 1. Podstawowe poj˛ecia, oznaczenia
6. Niech
I = {1, 2, 3, 4, 5} b˛edzie zbiorem indeksów. Dla ka˙zdego i ∈ I okre´slamy
zbór
C
i
= {x ∈ N | 1 ≤ x ≤ 30 oraz i dzieli x}. Oblicz
S
i∈I
C
i
oraz
T
i∈I
C
i
.
7. Niech
A = {1, 2, 3, 4}, B = {1, 2, 3}. Wypisz elementy A × B, B × A oraz
{(a, b) ∈ A × B | a < b}.
8. Niech
X = {a, b, c}. Wypisz elementy X
2
,
X
3
oraz
{(x, y) ∈ X
2
| x 6= y}.
9. Wypisz wszystkie podzbiory: a) zbioru pustego
∅, b) zbioru {a}, c) zbioru {a, b, c, d}.
10. Udowodnij, ˙ze
A ⊂ B wtedy i tylko wtedy gdy A ∩ B = A.
11. Narysuj wszystkie grafy ze zbiorem wierzchołków
V = {a, b, c}. Które z nich s ˛
a
spójne?
12. Narysuj wszystkie drzewa ze zbiorem wierzchołków
V = {a, b, c}.
13. Narysuj wszystkie grafy skierowane ze zbiorem wierzchołków
V = {a, b}.
14. Narysuj graf
G = (V, E), ze zbiorem wierzchołków V = {a, b, c, d, e} i zbiorem
kraw˛edzi
E = {{a, b}, {a, c}, {b, c}, {a, d}, {d, e}}. Czy graf G jest spójny? Czy
posiada cykle?
15. Narysuj graf skierowany
G = (V, E), ze zbiorem wierzchołków V = {a, b, c, d} i
zbiorem kraw˛edzi
E = {(a, b), (b, c), (c, b), (c, d), (d, d)}.
16. Wypisz 10 pierwszych słów zbioru
{a, b, c}
∗
według porz ˛
adku leksykograficznego
i kanonicznego.
17. Wypisz wszystkie prefiksy i sufiksy słowa
aaba.
18. Uporz ˛
adkuj nast˛epuj ˛
acy zbiór słów według porz ˛
adku leksykograficznego i kano-
nicznego: słowik, wróbel, kos, jaskółka, kogut, dzi˛ecioł, gil, kukułka, szczygieł,
sowa, kruk, czubatka, drozd, sikora i dzierlatka, kaczka, g ˛
aska, jemiołuszka, dudek,
trznadel, po´smieciuszka, wilga, zi˛eba, bocian, szpak. [Fragment wiersza Ptasie ra-
dio Juliana Tuwima]
19. Udowodnij wzory (1.1), (1.2), (1.3), (1.4).
20. Udowodnij lemat 1.31,
21. Udowodnij zale˙zno´sci z przykładów 1.28, 1.29, 1.30.
22. Niech
x, y b˛ed ˛
a dowolnymi liczbami rzeczywistymi, a
k dowoln ˛
a liczb ˛
a całkowit ˛
a.
Udowodnij nast˛epuj ˛
ace zale˙zno´sci:
bx + yc ≥ bxc + byc.
bx + kc = bxc + k.
dx + ye ≤ dxe + dye.
dx + ke = dxe + k.
1.16. Zadania
25
23. Podaj przykład liczb rzeczywistych
x i y, dla których zachodzi a) bx + yc > bxc +
byc, b) dx + ye < dxe + dye.
24. Podaj przykład liczby rzeczywistej
x i liczby całkowitej k, dla których zachodzi
dk · xe < k · dxe.
25. Za pomoc ˛
a algorytmu sortowania b ˛
abelkowego posortuj ci ˛
agi: a) 1,3,5,4,2;
b)
8,1,6,3,4,5,2,7.
26. Dane s ˛
a dwa wielomiany
U (x) = 4x
3
+ 3x + 2 oraz V (x) = 2x
4
+ x
2
+ 3x. Oblicz
ich sum˛e oraz iloczyn. Oblicz według schematu Horna warto´sci
U (1) oraz V (1).
27. Podziel wielomian
U (x) = 4x
4
+ 3x
2
+ x − 2 przez V (x) = x
2
+ x.