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.