MATEMATYKA DYSKRETNA 2010

A. PAWE L WOJDA

Spis tre´

sci

1.

Wyk lad 1 - 3.III.2010

3

1.1.

Matematyka dyskretna

3

1.2.

Zasada indukcji matematycznej

3

1.3.

R´

ownania rekurencyjne

4

2.

Wyk lad 2 - 10.III.2010

5

2.1.

Wyznacznik Vandermonde’a

5

2.2.

R´

ownania rekurencyjne liniowe

5

2.3.

Metody zliczania

6

3.

Wyk lad 3 - 17.III.2010

8

3.1.

Metody zliczania c.d.

8

4.

Wyk lad 4 - 24.III.2010

9

4.1.

Metody zliczania c.dc.d.

9

4.2.

Arytmetyka modularna

10

5.

Wyk lad 5 - 31.III.2010

12

5.1.

Arytmetyka modularna c.d.

12

5.2.

Grupy

12

6.

Wyk lad 6 - 21.IV.2010

14

6.1.

Grupy c.d.

14

7.

Wyk lad 7 - 28.IV.2010

16

7.1.

Grupy c.d.c.d.

16

7.2.

Kwadratowe residua modulo

16

7.3.

Zasady kryptografii z kluczem publicznym

17

7.4.

Metoda Rabina

18

8.

Wyk lad 8 - 5.V.2010

20

8.1.

Metoda RSA

20

8.2.

Grupy c.d.

21

9.

Wyk lad 9 - 12.V.2010

23

9.1.

Lemat Burnside’a

23

9.2.

Teoria graf´

ow

23

10.

Wyk lad 10 - 19.V.2010

24

10.1.

Grafy eulerowskie c.d.

24

10.2.

Grafy p laskie i planarne

25

11.

Wyk lad 11 - 26.V.2010

26

11.1.

Garfy planarne c.d.

26

11.2.

Drzewa i lasy

26

12.

Wyk lad 12 - 2.VI.2010

28

12.1.

Drzewa c.d.

28

12.2.

Drzewa jako przestrzenie metryczne

28

1

2

A. PAWE L WOJDA

12.3.

Drzewa z korzeniem i drzewa binarne

28

12.4.

Dendryty

29

13.

Wyk lad 13 - 9.VI.2010

30

13.1.

Kolorowanie wierzcho lk´

ow grafu

Liczba chromatyczna

30

13.2.

Wielomiany chromatyczne

30

13.3.

Kolorowanie kraw

,

edzi

31

13.4.

Grafy skierowne i turnieje.

31

14.

Wyk lad 14 - 16.VI.2010

32

14.1.

Turnieje -ci

,

ag dalszy.

32

14.2.

Liczba nieizomorficznych turniej´

ow rz

,

edu n

32

Literatura

35

MATEMATYKA DYSKRETNA 2010

3

1. Wyk lad 1 - 3.III.2010

1.1. Matematyka dyskretna. Przez matematyk

,

e dyskretn

,

a rozumie si

,

e dzia l ma-

tematyki, w kt´

orym nie stosuje si

,

e aparatu topologicznego, a w ka˙zdym razie w

kt´

orej ten aparat ma znaczenie raczej drugorz

,

edne

1

. Podczas wyk lad´

ow nie zoba-

czymy wi

,

ec ani pochodnych, ani ca lek. B

,

edziemy za to wykorzystywa´

c wiadomo´

sci

z algebry, teorii mnogo´

sci, teorii liczb. B

,

edziemy m´

owi´

c o kombinatoryce i teorii

graf´

ow.

Na wyk ladzie por´

ownywa lem matematyk

,

e ci

,

ag l

,

a z przemieszczaj

,

acy

,

a si

,

e wskaz´

ow-

k

,

a zegarka, za´

s matematyk

,

e dyskretn

,

a ze zmieniaj

,

ac

,

emi si

,

e cyframi zegarka elek-

tronicznego.

1.2. Zasada indukcji matematycznej. Zasada indukcji matematycznej jest stu-
dentom dobrze znana ze szko ly. Mo˙zna j

,

a sformu lowa´

c nast

,

epuj

,

aco.

Niech b

,

edzie dany ci

,

ag zda´

n (T

n

)

∞
n=k

(gdzie k jest pewn

,

a liczb

,

a naturaln

,

a).

• Je˙zeli zdanie T

k

jest prawdziwe oraz

• dla ka˙zdego n ≥ k z faktu, ˙ze T n jest prawdziwe wynika, ˙ze T

n+1

jest

prawdziwe,

w´

owczas dla wszystkich n ≥ k zdania T

n

s

,

a prawdziwe.

Zasad

,

e indukcji matematycznej mo˙zna przyj

,

a´

c jako pewnik.

My jednak za-

uwa˙zyli´

smy, ˙ze wynika ona z jeszcze latwiejszej do zaakceptowania zasady do-

brego uporz

,

adkowania zbioru liczb naturalnych. Zasada ta m´

owi, ˙ze ka˙zdy

podzbi´

or zbioru liczb naturalnych N ma element najmniejszy. W bardzo prosty

spos´

ob udowodnili´

smy, ˙ze z zasady dobrego uporz

,

adkowania zbioru liczb natural-

nych wynika zasada indukcji matematycznej.

Przyk lad 1. Wie ˙ze Hanoi (Brahmy)
Zabawka polega na tym, ˙ze dane s

,

a 3 patyczki nazwane A, B i C na podstawkach

oraz n k´

o leczek r´

o˙znej ´

srednicy z dziurkami w ´

srodku ka˙zdego. K´

o lka s

,

a na lo˙zone na

patyczek A tak, ˙ze nigdy ´

zadne wi

,

eksze k´

o lo nie le˙zy na k´

o lku mniejszym (czyli s

,

a

u lo˙zone od najwi

,

ekszego na dole do najmniejszego na wierzchu). K´

o lka przek lada

si

,

e po jednym tak, by korzystaj

,

ac z po´

sredniego patyczka B prze lo˙zy´

c wszystkie k´

o lka

na patyczek C ca ly czas trzymaj

,

ac si

,

e zasady, ˙ze nigdy k´

o lko wi

,

eksze nie mo˙ze by´

c

po lo˙zone na mniejszym.
Problem jest nast

,

epuj

,

acy: w ilu ruchach da si

,

e rozwi

,

aza´

c nasze zadanie?

Oznaczmy przez a

n

liczb

,

e koniecznych ruch´

ow przy n k´

o lkach. Z latwo´

sci

,

a stwier-

dzamy, ˙ze a

0

= 0, a

1

= 1 no i niezbyt trudno jest zauwa˙zy´

c, ˙ze a

n

= 2a

n−1

+ 1 (dla

n > 0). St

,

ad latwo obliczy´

c, ˙ze a

2

= 3, a

3

= 7, a

4

= 15. Te liczby sugeruj

,

a og´

olny

wz´

or. No i rzeczywi´

scie, indukcyjnie udowodnili´

smy, ˙ze

a

n

= 2

n

− 1

dla dowolnego n naturalnego.
Stara lem si

,

e przekona´

c s luchaczy, ˙ze to bardzo du˙zo (przek ladaj

,

ac 64 k´

o lka z szybko´

sci

,

a

1

Od tej regu ly s

,

a bardzo znacz

,

ace odst

,

epstwa. By´

c mo˙ze najcz

,

e´

sciej cytowany artyku l ma-

tematyczny, to praca dotycz

,

aca teorii graf´

ow Kazimierza Kuratowskiego charakteryzuj

,

aca grafy

planarna. Grafy to jeden z najwa˙zniejszych obiekt´

ow zainteresowa´

n matematyki dyskretnej. Ka-

zimierz Kuratowski za´

s to jeden z najwybitniejszych topolog´

ow.

4

A. PAWE L WOJDA

1 mikrosekundy jedno, mo˙zna z latwo´

sci

,

a oszacowa´

c czas potrzebny wsystkich k´

o lek

na grubo ponad 500 000 lat).

1.3. R´

ownania rekurencyjne. Niech b

,

edzie zadany ci

,

ag (a

n

) w nast

,

epuj

,

acy spos´

ob.

• Dane s

,

a warto´

sci a

0

, a

1

, ..., a

k−1

(a wi

,

ec k pierwszych wyraz´

ow ci

,

agu) oraz

wz´

or

• a

n

= f (a

n−1

, a

n−2

, ...a

n−k

), gdzie f jest pewn

,

a funkcj

,

a.

Zdefiniowany w taki spos´

ob ci

,

ag (a

n

) nazywamy rekurencyjnym stopnia k.

1.3.1. Ci

,

ag Fibonacciego. Ci

,

ag Fibonacciego

2

to z pewno´

sci

,

a najs lynniejszy ci

,

ag

rekurencyjny (drugiego stopnia). Pomijaj

,

ac tu anegdot

,

e o kr´

olikach, mo˙zna go

zdefiniowa´

c nast

,

epuj

,

aco:

• f

0

= 1

• f

1

= 1

• f

n+1

= f

n

+ f

n−1

dla n ≥ 2

Oczywi´

scie i tym razem mo˙zna z latwo´

sci

,

a wypisa´

c pierwszych kilka wyraz´

ow

ci

,

agu:

f

2

= 2, f

3

= 3, f

4

= 5, f

5

= 8, f

6

= 13, f

7

= 21, f

8

= 34, f

9

= 55, f

10

= 89

Tym razem jednak ci

,

ag kolejnych wyraz´

ow, nawet gdyby´

smy wypisali ich znacz-

nie wi

,

ecej, nie sugeruje ˙zadnego og´

olnego wzoru. Na nast

,

epnym wyk ladzie po-

znamy spos´

ob jak sobie z niekt´

orymi ci

,

agami rekurencyjnymi radzi´

c. Metoda kt´

or

,

a

poznamy obejmuje tak˙ze ci

,

ag Fibonacciego. Nie precyzuj

,

ac metody og´

olnej ci

,

ag

Fibonacciego jednak rozwi

,

azali´

smy. Okaza lo si

,

e, ˙ze

f

n

=

1

√

5





1 +

√

5

2

!

n+1

−

1 −

√

5

2

!

n+1





Tak skomplikowane rozwi

,

azanie oczywi´

scie wyja´

snia, dlaczego nie byli´

smy w

stanie odgadn

,

a´

c og´

olnego wzoru.

2

Postaci i znaczeniu Fibonacciego (1175-1250) po´

swi

,

eci lem na wyk ladzie chwilk

,

e. Warto po-

szpera´

c w wyszukiwarce i poczyta´

c o cz lowieku, kt´

ory poruszy l europejsk

,

a matematyk

,

e, napisa l

pierwsze znacz

,

ace dzie la matematyczne w Europie po 1000 lat zacofania.

MATEMATYKA DYSKRETNA 2010

5

2. Wyk lad 2 - 10.III.2010

2.1. Wyznacznik Vandermonde’a. Z nast

,

epuj

,

acego twierdzenia dotycz

,

acego wy-

znacznik´

ow, b

,

edziemy korzysta´

c w najbli˙zszej przysz lo´

sci.

Twierdzenie 1.

det










1

1

...

1

x

1

x

2

...

x

n

...

x

n−1
1

x

n−1
2

...

x

n−1

n










=

Y

1≤i≤j≤n

(x

j

− x

i

)

2.2. R´

ownania rekurencyjne liniowe. R´

ownaniem rekurencyjnym linio-

wym jednorodnym stopnia k nazywamy r´

ownanie postaci

(1)

a

n

= f (a

n−1

, ..., a

n−k

)

gdzie f : R

k

→ R jest pewn

,

a funkcj

,

a liniow

,

a, oraz zadane s

,

a warto´

sci pierwszych

k wyraz´

ow ci

,

agu (a

n

), a

0

, a

1

, ..., a

k−1

. Przy tych zamych za lo˙zeniach r´

ownanie

(2)

a

n

= f (a

n−1

, ..., a

n−k

) + g(n)

Nazywamy r´

ownaniem liniowym niejednorodnym stopnia k (o funkcji g :

N → R, poza tym, ˙ze jest to funkcja okre´

slona w zbiorze liczb naturalnych i o

warto´

sciach rzeczywistych, niczego szczeg´

olnego nie zak ladamy). Dla tak og´

olnie

postawionego problemu nie b

,

edziemy w stanie tu przedstawi´

c metody rozwi

,

azania,

niemniej ta posta´

c u latwi pewne zapisy.

R´

ownaniem rekurencyjnym liniowym o sta lych wsp´

o lczynnikach jedno-

rodnym nazywamy r´

ownanie rekurencyjne postaci

(3)

a

n

= α

1

a

n−1

+ α

2

a

n−2

+ ... + α

k

a

n−k

za´

s r´

ownanie

(4)

a

n

= α

1

a

n−1

+ α

2

a

n−2

+ ... + α

k

a

n−k

+ g(n)

nazywamy r´

ownaniem rekurencyjnym liniowym o sta lych wsp´

o lczynnikach

niejednorodnym.

Dla r´

ownania (3) r´

ownanie

(5)

r

k

= α

1

r

k−1

+ α

2

r

k−2

+ ... + α

k−1

r + α

k

nazywamy r´

ownaniem charakterystycznym.

Podczas wyk ladu zauwa˙zyli´

smy nast

,

epuj

,

ace fakty.

• Je´sli dane s

,

a ci

,

agi b

,

ed

,

ace rozwi

,

azaniami r´

ownania (1), to tak˙ze dowolna

kombinacja liniowa tych ci

,

ag´

ow jest rozwi

,

azaniem (1) (inaczej m´

owi

,

ac,

zbi´

or rozwi

,

aza´

n r´

ownania (1) jest podprzestrzeni

,

a przestrzeni wszystkich

ci

,

ag´

ow rzeczywistych).

• Warunki pocz

,

atkowe (czyli warto´

sci ci

,

agu dla pierwszych k indeks´

ow) nale˙z

,

a

do k-wymiarowej podprzestrzeni przestrzeni wszystkich ci

,

ag´

ow rzeczywi-

stych.

• Dla ka˙zdego rozwi

,

azania r r´

ownania charakterystycznego (5) ci

,

ag (r

n

) jest

rozwi

,

azaniem r´

ownania (3) (pomijamy w tym rozumowaniu, na razie, wa-

runki pocz

,

atkowe).

6

A. PAWE L WOJDA

• Z twierdzenia o wyznaczniku Vandermonde’a mo˙zna wywnioskowa´

c, ˙ze

je´

sli r´

ownanie charakterystyczne (5) ma k r´

o ˙znych rozwi

,

aza´

n r

1

, r

2

, ..., r

k

,

w´

owczas rozwi

,

azanie (1) ma (jedyne) rozwi

,

azanie postaci

a

0
n

= c

1

r

n

1

+ c

2

r

n

2

+ ... + c

k

r

n

k

To oczywi´

scie oznacza, ˙ze w przypadku istnienia k r´

o˙znych pierwiastk´

ow r´

ownania

charakterystycznego problem r´

owna´

n liniowych jednorodnych o sta lych wsp´

o lczynnikach

jest teoretycznie rozwi

,

azany

3

.

Powiedzieli´

smy tak˙ze (ju˙z bez dowodu), ˙ze je´

sli r

0

jest l-krotnym rozwi

,

azaniem

r´

ownania charakterystycznego, w´

owczas takie rozwi

,

azanie dostarcza nam l nie-

zale˙znych rozwi

,

aza´

n (1), mianowicie r

n

0

, nr

n

0

, ..., n

l−1

r

n

0

.

R´

ownanie niejednorodne nauczyli´

smy si

,

e rozwi

,

azywa´

c stosuj

,

ac metod

,

e prze-

widywa´

n. Metoda ta polega na zastosowaniu nast

,

epuj

,

acego algorytmu post

,

epo-

wania.

• Metod

,

e stosujemy wy l

,

acznie do przypadku gdy w r´

ownaniu (4) funkcja g

jest postaci

g(n) = βq

n

• Przewidujemy rozwi

,

azanie postaci

a

00
n

= An

l−1

q

n

gdzie l jest krotno´

sci

,

a pierwiastka charakterystycznego q (czyli przewidu-

jemy rozwi

,

azanie postaci a

00

n

= Aq

n

je´

sli q nie jest pierwiastkiem charakte-

rystycznym).

• Teraz nadszed l moment uwzgl

,

ednienia faktu, ˙ze zadane mamy pierwsze k

wyrazy ci

,

agu: znajdujemy takie c

1

, c

2

, ..., c

k

by

a

n

= a

0
n

+ a

00
n

spe lnia ly warunki pocz

,

atkowe problemu, czyli tak, by

a

0
i

+ a

00
i

= a

i

dla i = 0, 1, ..., k − 1

Przyk lad 2. R´

ownania

a

n

− 3a

n−1

= 5 · 7

n

a

n

− 3a

n−1

= 5 · 3

n

a

0

= 4.

2.3. Metody zliczania.

3

W la´

sciwie by lby rozwi

,

azany, nie tylko teoretycznie, gdyby´

smy umieli rozwi

,

azywa´

c r´

ownania

algebraiczne. Tymczasem nie tylko tego nie umiemy, ale wiemy, ˙ze metoda rozwi

,

azywania takich

r´

owna´

n nie istnieje.

MATEMATYKA DYSKRETNA 2010

7

2.3.1. Zasada w l

,

aczania-wy l

,

aczania (metoda sita).

Twierdzenie 2. (Formu la Sita

4

lub Zasada W l

,

aczania i Wy l

,

aczania) Niech

A

1

, A

2

, ..., A

n

b

,

ed

,

a zbiorami sko´

nczonymi. W´

owczas zachodzi wz´

or

|A

1

∪ A

2

∪ ... ∪ A

n

| =

X

1≤i

1

<i

2

<...<i

k

≤n

(−1)

k+1

|A

i

1

∩ A

i

2

∩ ... ∩ A

i

k

|.

Formu l

,

e sita wykazali´

smy metod

,

a indukcji matematycznej.

2.3.2. Miasta Parzyste i Nieparzyste. W mie´

scie P o 32 mieszka´

ncach kluby s

,

a

tworzone wed lug nast

,

epuj

,

acych zasad.

(i) Ka˙zdy klub ma parzyst

,

a liczb

,

e cz lonk´

ow.

(ii) Przeci

,

ecie dowolnych dw´

och klub´

ow ma parzyst

,

a liczb

,

e element´

ow.

Natomiast w mie´

scie N (tak˙ze o 32 mieszka´

ncach) kluby s

,

a tworzone wed lug tak,

by

(a) Ka˙zdy klub mia l nieparzyst

,

a liczb

,

e cz lonk´

ow.

(b) Przeci

,

ecie dowolnych dw´

och klub´

ow mia lo parzyst

,

a liczb

,

e element´

ow.

Problem. Jaka jest maksymalna liczba klub´

ow w P, a jaka w N?

Wykazali´

smy, ˙ze w P mo˙zna utworzy´

c co najmniej 2

16

≥ 65536 klub´

ow, podczas

gdy w N co najwy˙zej 32.
Bardzo si

,

e zdziwili´

smy!

Oszacowanie liczby klub´

ow w P znale´

zli´

smy stosuj

,

ac metody czysto kombinato-

ryczne. Dla oszacowania liczby klub´

ow w N stosowali´

smy podstawowe wiadomo´

sci

dotycz

,

ace wymiaru pewnej przestrzeni liniowej. Przyda la si

,

e wi

,

ec algebra liniowa.

4

Dok ladniej: ”sita Eratostenesa”. Eratostenes, (276-194 p.n.e) by l kustoszem Biblioteki Alek-

sandryjskiej i jednym z najwi

,

ekszych umys l´

ow staro ˙zytno´

sci. Sito Eratostenesa s lu ˙zy lo do ”od-

siewania” liczb pierwszych od ”plew” innych liczb. Jego innym, wielkim osi

,

agni

,

eciem by la pr´

oba

zmierzenia promienia Ziemi przez zmierzenie d lugo´

sci cieni rzucanych w po ludnie przez dwie

tyczki: jednej ustawionej w Aleksandrii, drugiej za´

s w Syene (dzisiejszy Asuan).

Wynik jaki

otrzyma l r´

o ˙zni l sie tylko o 1% od nam znanego, a by lo to w czasach kiedy w kulisto´

s´

c Ziemi

wierzy l ma lo kto!

8

A. PAWE L WOJDA

3. Wyk lad 3 - 17.III.2010

3.1. Metody zliczania c.d. Poza twierdzeniem Cantora (twierdzenie 9), o wszyst-
kich zbiorach wyst

,

epuj

,

acych poni˙zej zak ladamy, ˙ze s

,

a sko´

nczone.

3.1.1. Liczno´

s´

c zbioru par.

|A × B| = |A| · |B|

3.1.2. Wariacje z powt´

orzeniami. Niech B

A

= {f : A → B}. Wwczas

|B

A

| = |B|

|A|

(dow. indukcyjny ze wzgl

,

edu na |A| ).

3.1.3. —Wariacje bez powt´

orze´

n.

|{f : A → B|f − bijekcja}| = |B|(|B| − 1) · ... · (|B| − |A| + 1)

Wniosek 3. Liczba permutacji zbioru n elementowego: n!

3.1.4. Liczba k elementowych podzbior´

ow zbioru n elementowego. Niech

A

k

= {B ⊂

A : |B| = k}.






A

k







=

|A|

k



=

n!

k!(n − k)!

Wniosek 4.

(1) (a + b)

n

=

P

n
k=0

n
k

a

k

b

n−k

(2)

P

n
k=0

n
k

= 2

n

3.1.5. Wz´

or Cauchy’ego.

Twierdzenie 5.

p + q

m



=

m

X

k=0

p

k



q

m − k



3.1.6. Wybory z powt´

orzeniami. Wykorzystuj

,

ac model Lov´

asza-P´

elikana-Vesztera

wykazali´

smy nast

,

epuj

,

ace.

Twierdzenie 6. Istnieje dok ladnie

n+r−1

r

rozwi

,

aza´

n ca lkowitych nieujemnych

r´

ownania

x

1

+ x

2

+ ... + x

n

= r

3.1.7. Zasada Go l

,

ebnika (szufladkowa Dirichleta).

Twierdzenie 7. Niech A i B b

,

ed

,

a zbiorami sko´

nczonymi, f : A → B.

(1) Je´

sli A| > |B| w´

owczas f nie jest r´

o˙znowarto´

sciowa.

(2) Je´

sli |A| < |B| w´

owczas f nie jest suriekcj

,

a.

Wniosek 8 (Twierdzenia Erd˝

osa-Szek´

eresza). Niech n ∈ N. Ka˙zdy ci

,

ag r´

o˙znych

n

2

+ 1 liczb rzeczywistych zawiera n + 1 wyrazowy podci

,

ag monotoniczny.

Twierdzenie 9 (Cantor). Niech A b

,

edzie dowolnym (niekoniecznie sko´

nczonym!)

zbiorem. Nie istnieje suriekcja zbioru A na zbi´

or wszystkich podzbior´

ow zbioru A.

MATEMATYKA DYSKRETNA 2010

9

4. Wyk lad 4 - 24.III.2010

4.1. Metody zliczania c.dc.d.

4.1.1. Liczby Stirlinga pierwszego rodzaju. Przypomnieli´

smy co to jest permutacja,

jak zapisujemy permutacje w przypadku zbioru sko´

nczonego (wygl

,

ada lo na to, ˙ze

nie wszyscy wiedzieli!), co to jest cykl permutacji (permutacja cykliczna) i jak
rozk ladamy permutacj

,

e na iloczyn (z lo˙zenie) cykli.

c(n, k) - liczba permutacji zbioru n-elementowego, kt´

ore maj

,

a k cykli.

Twierdzenie 10. Niech k, n ∈ N, 0 < k ≤ n.

(1) c(n, k) = c(n − 1, k − 1) + (n − 1)c(n − 1, k).
(2) c(n, n) = 1
(3) c(n, 0) = c(0, k) = 0.

Dow. ...

Oznaczmy

[x]

n

= x(x − 1) · ... · (x − n + 2)(x − n + 1)

[x]

n

=

n

X

k=0

s(n, k)x

k

Wsp´

o lczynniki s(n, k) nazwyamy liczbami Stirlinga I-go rodzaju.

Twierdzenie 11. Niech k, n ∈ N, 0 < k < n. W´

owczas

(1) s(n, k) = s(n − 1, k − 1) − (n − 1)s(n − 1, k).
(2) s(n, n) = 1.
(3) s(n, 0) = s(0, k) = 0

Dow. ...

Twierdzenie 12. Niech n, k ∈ N, k ≤ n.

c(n, k) = (−1)

n+k

s(n, k)

Dow. ...

4.1.2. Liczba permutacji danego typu.

Definicja 1. Permutacj

,

e σ ∈ S

n

nazywamy typu 1

λ

1

2

λ

2

. . . n

λ

n

je˙zeli ma λ

i

cykli

d lugo´

sci i (w rozk ladzie kanonicznym na cykle roz l

,

aczne), dla i = 1, . . . , n.

Uwaga. Oczywi´

scie, je´

sli permutacja σ jest typu 1

λ

1

2

λ

2

. . . n

λ

n

, w´

owczas zacho-

dzi:

1λ

1

+ 2λ

2

+ · · · + nλ

n

= n

Twierdzenie 13 (Cauchy’ego). Je´

sli 1λ

1

+ 2λ

2

+ · · · + nλ

n

= n, w´

owczas liczba

permutacji typu 1

λ

1

2

λ

2

. . . n

λ

n

jest r´

owna

h(λ

1

, ..., λ

n

) =

n!

1

λ

1

2

λ

2

. . . n

λ

n

λ

1

!λ

2

!...λ

n

!

Dow. ...

10

A. PAWE L WOJDA

4.1.3. Liczba podzia l´

ow zbioru.

Definicja 2. Rodzina

5

{A

i

}

i=1,...,n

jest podzia lem zbioru X je˙zeli:

(1) X =

S

i=1,...,n

A

i

,

(2) A

i

∩ A

j

dla i 6= j.

Definicja 3. Podzia l zbioru n-elementowego jest typu 1

λ

1

2

λ

2

...n

λ

n

je´

sli zawiera λ

i

zbior´

ow liczno´

sci i (dla i = 1, ..., n).

Uwaga: Je´

sli istnieje podzia l n-elementowego zbioru typu 1

λ

1

2

λ

2

...n

λ

n

, w´

owczas

1λ

1

+ 2λ

2

+ ... + nλ

n

= n.

Twierdzenie 14. Je´

sli 1λ

1

+ 2λ

2

+ ... + nλ

n

= n w´

owczas liczba podzia l´

ow typu

1

λ

1

2

λ

2

...n

λ

n

dana jest wzorem

P (λ

1

, ..., λ

n

) =

n!

λ

1

!λ

2

!...λ

n

!(1!)

λ

1

(2!)

λ

2

. . . (n!)

λ

n

Dow. ...

4.1.4. Liczby Stirlinga II rodzaju.

Definicja 4. Liczb

,

a Stirlinga II rodzaju nazywamy S(n, k) – liczb

,

e podzia l´

ow zbioru

n-elementowego na k podzbior´

ow niepustych.

Twierdzenie 15.

S(n, k) =

X

λ

1

+...+λ

n

=k; λ

1

+...+nλ

n

=n

n!

λ

1

!λ

2

!...λ

n

!(1!)

λ

1

(2!)

λ

2

. . . (n!)

λ

n

Twierdzenie 16. (Zale˙zno´

s´

c rekurencyjna dla liczb Stirlinga II rodzaju)

(1) S(n, n) = 1 (dla n ≥ 0),
(2) S(n, 0) = 0 dla n > 0,
(3) S(n, k) = S(n − 1, k − 1) + kS(n − 1, k) dla 0 < k < n

Dow. ...

4.2. Arytmetyka modularna.

4.2.1. Twierdzenie o dzieleniu liczb ca lkowitych i jego konsekwencje.

Twierdzenie 17. Dla dowolnych liczb ca lkowitych a i b, b > 0 istniej

,

a jednoznacz-

nie wyznaczone liczby q, r ∈ Z takie, ˙ze a = bq + r, przy czym 0 ≤ r < b.

Liczby q oraz r nazywamy, odpowiednio, ilorazem i reszt

,

a dzielenia a przez b.

Warto podkre´

sli´

c, ˙ze twierdzenie 17 nie jest tym, kt´

ore wi

,

ekszo´

s´

c student´

ow

pami

,

eta ze szko ly

6

.

M´

owimy, ˙ze d jest najwi

,

ekszym wsp´

olnym dzielnikiem liczb ca lowitych a i

b je˙zeli

• d|a i d|b oraz
• dla ka˙zdego c ∈ Z: c|a ∧ c|b ⇒ c|d

5

Inaczej: zbi´

or zbior´

ow.

6

Sprawd´

z, jaki jest wynik dzielenia liczby −9 przez 7?

MATEMATYKA DYSKRETNA 2010

11

Algorytm Euklidesa
Niech a, b ∈ Z, a, b 6= 0.
Tworzymy rekurencyjnie ci

,

ag (r

n

):

r

0

= a, r

1

= b

r

n−1

= q

n

r

n

+ r

n+1

, gdzie 0 ≤ r

n+1

< r

n

.

Twierdzenie 18. Niech a, b ∈ Z, a, b 6= 0. Istnieje takie k ca lkowite, ˙ze r

k

6= 0,

r

k+1

= 0 (gdzie ci

,

ag (r

n

) jest wyznaczony przy pomocy algorytmu Euklidesa). Co

wi

,

ecej, mamy w´

owczas r

k

=NWD(a, b).

12

A. PAWE L WOJDA

5. Wyk lad 5 - 31.III.2010

5.1. Arytmetyka modularna c.d.

Twierdzenie 19 (O postaci NWD). Niech a, b ∈ Z nie r´

owne r´

ownocze´

snie zero.

W´

owczas

N W D(a, b) = min{c > 0 : c = αa + βb, α, β ∈ Z}

Dow. ...
Uwaga. Zauwa˙zmy, ˙ze dzi

,

eki twierdzeniu 19 oraz algorytmowi Euklidesa, dla

dowolnych liczb ca lkowitych a i b umiemy nie tylko efektywnie policzy´

c ich NWD,

ale tak˙ze przedstawi´

c w postaci

d = αa + βb

W najbli˙zszej przesz lo´

sci ta umiej

,

etno´

s´

c bardzo nam si

,

e przyda.

Definicja 5. M´

owimy, ˙ze dwie liczby ca lkowite a i b s

,

a wzgl

,

ednie pierwsze, je´

sli

N W D(a, b) = 1.
Piszemy w´

owczas a ⊥ b.

5.2. Grupy.

5.2.1. Przypomnienie poj

,

ecia grupy. Zbi´

or G z dzia lanem ∗ nazywamy grup

,

a je˙zeli

∗ jest w G dzia laniem

• l

,

acznym,

• posiadaj

,

acym element neutralny e, oraz

• takim, ˙ze dla dowolnego g ∈ G istnieje g

0

∈ G spe lniaj

,

acy

g ∗ g

0

= g

0

∗ g = e

(element odwrotny elementu g).

Je´

sli dzia lanie ∗ jest w G przemienne, w´

owczas G nazywamy przemienn

,

a lub

abelow

,

a.

Przyk lady: grupa Kleina, Z

n

(dla r´

o˙znych n).

5.2.2. Grupy Z

∗

n

. D lu˙zsz

,

a chwil

,

e po´

swi

,

ecili´

smy zbiorowi Z

n

(n naturalne i wi

,

eksze

od 1) z dzia laniem mno˙zenia. Do´

s´

c oczywistym jest, ˙ze elementem neutralnym

dla mno˙zenia w Z

n

jest 1. Latwo si

,

e okaza lo, ˙ze dla niekt´

orych n do niekt´

orych

element´

ow Z

n

nie ma element´

ow odwrotnych. Tak wi

,

ec, cho´

c dla dodawania Z

n

zawsze jest grup

,

a przemienn

,

a, dla mno˙zenia nigdy grup

,

a nie jest (bo 0 nie ma

elementu odwrotnego). Postanowili´

smy tak zmodyfikowa´

c Z

n

, by jednak grup

,

e

multyplikatywn

,

a (t.j. z dzia laniem mno˙zenia) otrzyma´

c. Rych lo okaza lo si

,

e, ˙ze

z Z

n

nie wystarczy usun

,

a´

c zera. Na szcz

,

e´

scie uda lo si

,

e udowodni´

c nast

,

epuj

,

ace

twierdzenie.

Twierdzenie 20. Element a ∈ Z

n

ma w Z

n

element odwrotny ze wzgl

,

edu na

mno˙zenie wtedy i tylko wtedy gdy a ⊥ n

Dow. ...
St

,

ad ju˙z tylko krok do nast

,

epnego, wa˙znego twierdzenia.

Twierdzenie 21. Niech Z

∗

b

,

edzie zbiorem element´

ow Z

n

wzgl

,

ednie pierwszych z

n. W´

owczas Z

∗

n

jest grup

,

a przemienn

,

a z mno˙zeniem.

Uwaga. Znowu, dzi

,

eki algorytmowi Euklidesa, umiemy do dowolnego elementu

a ∈ Z

∗

n

efektywnie znale´

z´

c element odwrotny.

MATEMATYKA DYSKRETNA 2010

13

5.2.3. Chi´

nskie Twierdzenie o Resztach.

Twierdzenie 22 (Sun Ze ok. 450 r.). Niech a, b, n, k b

,

ed

,

a liczbami ca lkowitymi,

n, k > 0, n ⊥ k. W´

owczas istnieje dok ladnie jedno rozwi

,

azanie x

0

∈ Z, 0 ≤ x

0

< nk

uk ladu r´

owna´

n:



x

≡

a

( mod n)

x

≡

b

( mod k)

Co wi

,

ecej, ka˙zde rozwi

,

azanie tego uk ladu r´

o˙zni si

,

e od x

0

o wielokrotno´

s´

c nk.

Dow. ... (Warto zna´

c, bo zawiera algorytm roawi

,

azywania uk lad´

ow modular-

nych, o kt´

orych m´

owi twierdzenie!)

Na koniec wyk ladu by la anegdota o cesarzu (chi´

nskim), a de facto pewne za-

stosowanie twierdzenia do policzenia liczno´

sci zbioru, bez liczenia wszystkich jego

element´

ow.

14

A. PAWE L WOJDA

6. Wyk lad 6 - 21.IV.2010

Uwaga: Napis DOM! na marginesie oznacza, ˙ze zdanie podane w tek´

scie

pozostawione zosta lo do udowodnienia (ca lkowicie lub cz

,

e´

sciowo) w domu lub na

´

cwiczeniach.

6.1. Grupy c.d.

6.1.1. Homomorfizmy grup. Niech (G; ∗) i (H, ◦) b

,

ed

,

a grupami. Odwzorowanie

φ : G → H nazywamy homomorfizmem grup je´

sli dla wowolnych a, b ∈ G

spe lniony jest warunek

φ(a ∗ b) = φ(a) ◦ φ(b)

Je´

sli, dodatkowo, φ jest bijekcj

,

a, w´

owczas homomorfizm ten nazywamy izomorfi-

zmem. W´

owczas grupy nazywamy izomorficznymi.

Przyk lad. Sprawdzili´

smy, ˙ze

φ : Z

5

3 k → k ∈ Z

nie jest homomorfizmem, za´

s

ψZ 3 k → k

[5]

∈ Z

5

homomorfizmem jest

7

.

Inne przyk lady te˙z by ly.

6.1.2. Podgrupy. Niech (G; ∗) b

,

edzie grup

,

a. H ⊂ G jest podgrup

,

a grupy G je´

sli

H z dzia laniem ∗

|

H

(czyli z dzia lanie ∗ zacie´

snionym do zbioru H) jest grup

,

a.

Przyk lad. {0, 2, 4, 6} jest podgrup

,

a grupy Z

8

(addytywnej).

Q, Z s

,

a podgrupami addytywnej grupy R.

Przyk lad. Sprawdzili´

smy, ˙ze grupa Kleina jest izomorficzna z pewn

,

a podgrup

,

a

grupy permutacji czterech element´

ow a tak˙ze, ˙ze grupa izometrii sze´

scianu wykonal-

DOM!

nych bez zniszczenia tego sze´

scianu, jest podgrup

,

a grupy permutaci zbioru o´

smio-

elementowego (wierzcho lk´

ow sze´

scianu).

Twierdzenie 23. Niech G b

,

edzie grup

,

a multyplikatywn

,

a, H ⊂ G, H 6= ∅. H jest

podgrup

,

a grupy G wtedy i tylko wtedy, gdy dla dowolnych element´

ow a, b ∈ H

ab

−1

∈ H

Dow... co´

s chyba m´

owi lem, ale bardzo szybko, a wi

,

ec −→...

DOM!

Krotno´

s´

c i pot

,

ega elementu w grupie.

Niech G b

,

edzie grup

,

a addytywn

,

a. Krotno´

s´

c elementu a ∈ G definiujemy nast

,

epuj

,

aco.

(1) 0a = 0

Nale˙zy zwr´

oci´

c uwag

,

e na fakt, ˙ze 0 z lewej strony r´

owno´

sci oznacza liczb

,

e

ca lkowit

,

a 0, za´

s 0 z prawej strony r´

owno´

sci jest elementem neutralnym

grupy G. Mog

,

a to by´

c (i na og´

o l s

,

a) zupe lnie r´

o˙zne elementy, kt´

ore ozna-

czamy tym samym symbolem.

(2) Dla n ∈ N:

(n + 1)a = na + a

7

Przez k

[n]

oznaczamy reszt

,

e z dzielenia k przez n (inaczej m´

owi

,

ac, obcinamy k modulo n).

MATEMATYKA DYSKRETNA 2010

15

(3) Dla n ∈ Z, n < 0:

na = (−n)(−a)

Je´

sli H jest grup

,

a multyplikatywn

,

a, w´

owczas definiujemy pot

,

egi ca lkowite elementu

a ∈ H.

(1) a

0

= 1

1 oznacza tu oczywi´

scie element neutralny grupy H.

(2) Dla n ∈ N:

a

n+1

= a · a

n

(3) Dla n ∈ Z i n < 0:

a

n

= (a

−1

)

−n

Uwaga 1. Zbi´

or wszystkich ca lkowitych krotno´

sci pewnego elementu a dowolnej

grupy addytywnej jest podgrup

,

a tej grupy.

Podobnie:
Zbi´

or wszystkich ca lkowitych pot

,

eg elementu a grupy multyplikatywnej jest podgrup

,

a.

DOM!

Podgrup

,

e pot

,

eg elementu a (w grupie multyplikatywnej) nazywamy podgrup

,

a

generowan

,

a przez ten element. Oczywi´

scie rz

,

ad elementu i rz

,

ad podgrupy gene-

rowanej przez ten element s

,

a identyczne.

Rz

,

ad elementu w grupie.

Niech G b

,

edzie grup

,

a multyplikatywn

,

a, a ∈ G.

M´

owimy, ˙ze a jest rz

,

edu k je˙zeli

k = min{n ∈ N − {0} : a

n

= 1}

Zauwa˙zyli´

smy, ˙ze w Z

8

rz

,

ad elementu 2 jest r´

owny 4 (przenosz

,

ac przy okazji

poj

,

ecie rz

,

edu na grupy addytywne).

W grupie Z ˙zaden, poza 0, element nie ma rz

,

edu (w takiej sytuacji m´

owimy tak˙ze,

˙ze rz

,

edem elementu jest ∞).

Twierdzenie 24. W dowolnej grupie sko´

nczonej G ka˙zdy element ma rz

,

ad sko´

nczony.

Dow. ...

6.1.3. Grupy transformacji i Twierdzenie Cayleya. Niech X b

,

edzie dowolnym zbio-

rem niepustym.

Ka˙zd

,

a podgrup

,

e grupy S(X) permutacji zbioru X nazywamy

grup

,

a transformacji.

Przyk lady ...

Twierdzenie 25 (Cayley). Ka˙zda grupa jest izomorficzna z pewn

,

a grup

,

a transfor-

macji.

Dow. ...

16

A. PAWE L WOJDA

7. Wyk lad 7 - 28.IV.2010

Uwaga: Egzamin I termin: 22 czerwca 2010 w U2

Godz. 9.00

7.1. Grupy c.d.c.d.

7.1.1. Twierdzenie Lagrange’a.

Twierdzenie 26 (Lagrange’a). Niech H b

,

edzie podgrup

,

a grupy sko´

nczonej G, a =

|H|, b = |G|. W´

owczas a|b.

Definicja 6 (Przystawanie modulo p´

o lgrupa). Niech H b

,

edzie podgrup

,

a grupy G,

a, b ∈ G. M´

owimy, ˙ze a przystaje do b modulo H (piszemy a ≡ b (mod H) lub

aR

H

b) je˙zeli ab

−1

∈ H.

Lemat 27. Je˙zeli H jest podgrup

,

a G w´

owczas relacja przystawania modulo H jest

w G relacj

,

a r´

ownowa˙zno´

sci.

Lemat 28. Niech G b

,

edzie dowoln

,

a grup

,

a, za´

s H jej podgrup

,

a. W´

owczas klas

,

a

elementu neutralnego grupy G modulo H jest zbi´

or H.

Lemat 29. Niech G b

,

edzie dowoln

,

a grup

,

a, za´

s H jej podgrup

,

a. W´

owczas dowolne

dwie klasy r´

ownowa˙zno´

sci modulo H s

,

a r´

ownoliczne (bijektywne)

8

.

Oczywi´

scie twierdzenie Lagrange’a wynika natychmiast z lematu 29.

7.1.2. Wnioski z twierdzenia Lagrange’a.

Wniosek 30. Ka˙zdy element grupy sko´

nczonej G ma rz

,

ad b

,

ed

,

acy dzielnikiem rz

,

edu

grupy G.

Twierdzenie 31 (Eulera). Je´

sli liczby naturalne a, n s

,

a wzgl

,

ednie pierwsze, w´

owczas

a

ϕ(n)

≡ 1 (mod n)

Twierdzenie 32 (Ma le Twierdzenie Fermata). Je´

sli p jest liczb

,

a pierwsz

,

a, a ∈ Z,

to

a

p

≡ a( mod p)

7.2. Kwadratowe residua modulo.

Twierdzenie 33. Niech p b

,

edzie liczb

,

a pierwsz

,

a i niech a ∈ Z

p

. W´

owczas a ma

co najwy˙zej dwa pierwiastki kwadratowe w Z

p

.

Niech n ∈ N, a ∈ Z

n

. M´

owimy, ˙ze a jest kwadratowym residuum modulo

n, je˙zeli istnieje b ∈ Z

n

takie, ˙ze a = b

2

(mod n).

Twierdzenie 34. Niech p ∈ N b

,

edzie liczb

,

a pierwsz

,

a, p ≡ 3 (mod 4) i niech a

b

,

edzie residuum kwadratowym w Z

p

. W´

owczas pierwiastkami kwadratowymi a z Z

p

s

,

a a

p+1

4

(mod p) oraz −a

p+1

4

(mod p).

8

W przypadku gdy G jest grup

,

a sko´

nczon

,

a oznacza to, ˙ze dowolne dwie klasy r´

ownowa ˙zno´

sci

modulo H maj

,

a tak

,

a sam

,

a liczb

,

e element´

ow.

MATEMATYKA DYSKRETNA 2010

17

7.3. Zasady kryptografii z kluczem publicznym. Wyobra´

zmy sobie, ˙ze mamy

trzy osoby: Alicj

,

e, Boba i Ew

,

e. Alicja chce przesla´

c Bobowi pewne informacje

tak, by Ewa (ani nikt inny poza Bobem) nie m´

og l odgadn

,

a´

c ich tre´

sci mimo, ˙ze

informacje te przekazywane s

,

a w spos´

ob jawny

9

. Warto w tym miejscu zda´

c sobie

spraw

,

e, ˙ze ka˙zd

,

a informacj

,

e mo˙zna traktowa´

c jako liczb

,

e. Standardowym zapisem

jest powszechnie znany kod ASCII kt´

ory mo˙zna z latwo´

sci

,

a zdoby´

c, na przyk lad

za pomoc

,

a internetu (w kodzie tym ka˙zdemu znakowi odpowiada 3-cyfrowa liczba,

a to 097, spacja to 032, o to 111 itd). Kod ASCII ma jednak oczywist

,

a wad

,

e:

wszyscy go znaj

,

a, a w ka˙zdym razie wiedz

,

a jak sie w niego zaopatrzy´

c. Tak wi

,

ec

Alicja i Bob b

,

ed

,

a musieli przesy lane dane zaszyfrowa´

c (funkcj

,

e szyfruj

,

ac

,

a oznacza´

c

b

,

edziemy przez E

10

, na dodatek wychodz

,

ac z za lo˙zenia, ˙ze wszystkie przesy lane

wiadomo´

sci s

,

a pods luchiwane (przez Ew

,

e).

By osi

,

agn

,

a´

c sw´

oj cel, Alicja i Bob b

,

ed

,

a post

,

epowali wed lug nast

,

epuj

,

acego sche-

matu:

1

Bob znajduje funkcj

,

e koduj

,

ac

,

a (szyfruj

,

ac

,

a) E oraz dekoduj

,

ac

,

a D,

a wi

,

ec takie by D(E(l)) = l

2

Bob przesy la tekstem otwartym (Ewa widzi przekaz) funkcj

,

e E Alicji

3

Alicja koduje informacj

,

e kt´

or

,

a chce przes la´

c Bobowi wed lug

otrzymanej przez niego instrukcji (t

,

e instrukcje zna tak˙ze Ewa).

Inaczej m´

owi

,

ac Alicja oblicza warto´

s´

c m = E(l)

4

Alicja wysy la Bobowi m

(Ewa oczywi´

scie tak˙ze widzi przesy lan

,

a informacj

,

e)

5

Bob liczy D(m) i poznaje tre´

s´

c przesy lki Alicji

Wydaje si

,

e, ˙ze znalezienie w tej sytuacji skutecznej metody szyfrowania chroni

,

acej

przesy lane informacje przed niezdrow

,

a

11

ciekawo´

sci

,

a Ewy b

,

edzie bardzo trudne.

Okazuje si

,

e, ˙ze taka metoda istnieje, cho´

c opiera si

,

e na bardzo, na poz´

or, kruchej

podstawie. T

,

a podstaw

,

a jest przekonanie (hipoteza), ˙ze nie istnieje skuteczna me-

toda faktoryzacji liczb naturalnych. Rzeczywi´

scie, cho´

c pomno˙zenie r

,

ecznie, a wi

,

ec

bez u˙zycia komputera dw´

och du˙zych, powiedzmy o 500 pozycjach dziesi

,

etnych liczb,

wydaje si

,

e czynno´

sci

,

a k lopotliw

,

a, wymagaj

,

ac

,

a du˙zej ilo´

sci czasu i papieru, dla kom-

putera jest proste i odbywa si

,

e w mgnieniu oka, daj

,

ac w rezultacie liczb

,

e o 1000

miejscach dziesi

,

etnych. Nawet naszemu domowemu komputerowi taka czynno´

s´

c

zajmie mniej ni˙z sekund

,

e. Je´

sli jednak odwr´

ocimy zagadnienie, czyli je´

sli otrzy-

mamy 1000-pozycyjn

,

a liczb

,

e n = pq, gdzie p i q s

,

a nieznanymi nam liczbami pierw-

szymi, i zadanie nasze b

,

edzie polega lo na znalezieniu p i q, to b

,

edziemy musieli

wykona´

c liczb

,

e dziele´

n (pr´

ob) rz

,

edu 10

500

, co nawet najszybszemu komputerowi

zajmie niewyobra˙zaln

,

a ilo´

s´

c czasu

12

. Na dodatek, gdyby wynaleziono komputery o

wiele szybsze ni˙z znane do tej pory, wystarczy zwi

,

ekszy´

c liczb

,

e cyfr znacz

,

acych n

9

Rozszyfrujmy kilka spraw. Dlaczego Alicja, Bob i Ewa? To proste. Alicja, bo na liter

,

e A,

Bob bo na liter

,

e B, E bo po angielsku pods luchiwacz to eavesdropper (a wi

,

ec na liter

,

e E, jak Ewa

(Eve)). Rozs

,

adnie jest tak˙ze za lo˙zy´

c, ˙ze wszystkie przesy lane informacje mog

,

a by´

c ´

sledzone. Czy˙z

nie tak jest gdy wyjmujemy pieni

,

adze z bankomatu lub, w jeszcze wi

,

ekszym stopniu, gdy p lacimy

za zakupy dokonywane za po´

srednictwem internetu?

10

E od angielskiego encoding

11

A przede wszystkiem niebezpieczn

,

a dla Alicji i Boba!

12

Sam sprawd´

z. Przyjmij, ˙ze jedno dzielenie wymaga 1 mikrosekundy, a dla u latwienia obli-

cze´

n, ˙ze minuta ma 100 sekund, doba 100 godzin, rok 1000 dni.

18

A. PAWE L WOJDA

z 1000 do 2000 by liczba operacji potrzebnych do znalezienia faktoryzacji wzros la
10

1000

krotnie.

Poni˙zej poka˙zemy w jaki spos´

ob rozwa˙zania na temat z lo˙zono´

sci obliczeniowej

mno˙zenia i znajdowania rozk ladu liczb na czynniki pierwsze mog

,

a by´

c przydatne

w kryptografii.

7.4. Metoda Rabina. Metod

,

e kodowania Rabina

13

mo˙zna opisa´

c nast

,

epuj

,

aco.

Niech n b

,

edzie ustalon

,

a, wystarczaj

,

aco du˙z

,

a (powiedzmy 300-cyfrow

,

a) liczb

,

a.

Funkcj

,

a koduj

,

ac

,

a jest

E(l) = l

2

( mod n)

Oznacza to tyle, ˙ze Bob prze´

sle Alicji liczb

,

e n i funkcj

,

e koduj

,

ac

,

a. Alicja obliczy

l

2

(mod n), prze´

sle t

,

e informacje Bobowi. Ewa, pods luchiwaczka, b

,

edzie zna la

zar´

owno l

2

jak i n, a jednak, z powod´

ow opisanych wy˙zej, nie b

,

edzie w stanie obli-

czy´

c l. Zauwa˙zmy. ˙ze tak ´

swietnie licz

,

ace pierwiastki kalkulatory (czy komputery)

s

,

a w tej sytuacji zupe lnie bezu˙zyteczne. Na przyk lad gdyby´

smy obliczyli przy po-

mocy kalkulatora

√

10 to otrzymaliby´

smy 3.1621..., co nijak ma si

,

e do pierwiastka

z 10 (mod 13) (dwie liczby daj

,

a w kwadracie 10 (mod 13), mianowicie 6 i 7). Jak

to jednak mo˙zliwe, ˙ze Bob b

,

edzie w stanie zrobi´

c to, czego nie jest w stanie uczyni´

c

Ewa, to znaczy obliczy´

c l?

Oto opis metody.

(1) Bob wybiera dwie du˙ze liczby pierwsze p i q takie, by p ≡ q ≡ 3 (mod 4).

Nast

,

epnie oblicza n = pq i przesy la Alicji (a wszystko to podgl

,

ada Ewa).

(2) Alicja konwertuje swoj

,

a wiadomo´

s´

c w kodzie ASCII otrzymuj

,

ac liczb

,

e l i

oblicza m = l

2

(mod n). Nast

,

epnie przesy la Bobowi m. Ewa widzi m, zna

ju˙z n, nie umie jednak obliczy´

c p i q, bo to jest w la´

snie trudny problem

faktoryzacji.

(3) Bob znajduje pierwiastki z m obliczaj

,

ac wpierw a = m

p+1

4

(mod p), b =

−m

p+1

4

(mod p), c = m

q+1

4

(mod q) oraz d = −m

q+1

4

(mod q), a nast

,

epnie

rozwi

,

azuj

,

ac cztery uk lady r´

owna´

n modularnych:



x

≡

a

(mod p)

x

≡

c

(mod q)



x

≡

a

(mod p)

x

≡

d

(mod q)



x

≡

b

(mod p)

x

≡

c

(mod q)



x

≡

b

(mod p)

x

≡

d

(mod q)

Uk lady r´

owna´

n modularnych maj

,

a jednoznaczne rozwi

,

azania modulo n = pq

dzi

,

eki lematowi chi´

nskiemu. Otrzymamy wi

,

ec a˙z cztery rozwiazania, cho´

c wiemy,

˙ze dobre jest tylko jedno z nich. To jednak, by w´

sr´

od rozwi

,

aza´

n odr´

o˙zni´

c w la´

sciwe

b

,

edzie dla Boba bardzo proste. Po przej´

sciu z kodu ASCII na litery otrzyma jedn

,

a

wiadomo´

s´

c sensown

,

a i trzy ci

,

agi znak´

ow nie maj

,

acych sensu.

Przyk lad. Alicja ma wiadomo´

s´

c w = 15. Bob wybiera n = 209 = 11 · 19

(zauwa˙zmy, ˙ze 11, 19 ≡ 3 (mod 4).
Alicja liczy: 15

2

= 225 ≡ 16 (mod 209)

i przesy

,

a Bobowi, kt´

ory oblicza:

16

11+1

4

= 16

3

≡ 5

3

≡ 25 · 5 ≡ 3 · 5 = 15 ≡ 4 (mod 11)

16

19+1

4

= 16

5

= 16

2

·16

2

·16 = 256·256·16 ≡ 9·9·16 = 81·16 ≡ 5·16 ≡ 5·16 = 80 ≡ 4

(mod 19)

13

Nazwa od tw´

orcy metody: Michaela Rabina

MATEMATYKA DYSKRETNA 2010

19

Bob rozwi

,

azuje teraz (oczywi´

scie korzystaj

,

ac z chi´

nskiego twierdzenia o resztach)

cztery uk lady r´

owna´

n modularnych:



x

≡

4

(mod 11)

x

≡

4

(mod 19)



x

≡

4

(mod 11)

x

≡

15

(mod 19)



x

≡

7

(mod 11)

x

≡

4

(mod 19)



x

≡

7

(mod 11)

x

≡

15

(mod 19)

Rzeczywi´

scie, latwo sprawdzi´

c, ˙ze jeden z tych uk lad´

ow ma rozwi

,

azanie, r´

owne 15.

20

A. PAWE L WOJDA

8. Wyk lad 8 - 5.V.2010

8.1. Metoda RSA. O ile metoda Rabina wykorzystuje Ma le Twierdzenie Fer-
mata, to metoda RSA

14

opiera si

,

e na twierdzeniu Eulera.

Opis metody RSA.

(1) Bob:

(a) Znajduje 2 du˙ze liczby pierwsze p, q, liczy n = pq oraz ϕ(n) = (p −

1)(q − 1).

(b) Wybiera (dowolne) e ∈ Z

∗
ϕ(n)

(a wi

,

ec e jest wzgl

,

ednie pierwsze z ϕ(n)).

(c) Oblicza d = e

−1

w Z

∗
ϕ(n)

.

(2) Ewa: Widzi! Widzi zar´

owno n jak i e. Wie tak˙ze jaka jest funkcja szy-

fruj

,

aca.

(3) Alicja:

(a) Liczy l = m

e

(mod n)

(b) Wysy la l Bobowi.

Bob: Liczy

(6)

l

d

= (m

e

)

d

≡ m

Prawdziwo´

s´

c wzoru 6 wymaga uzasadnienia. Oto one.

(a) Przypadek: m ⊥ n. Skoro ed ≡ 1 (mod ϕ(n)) mamy: ed = 1 + kϕ(n)

(gdzie n jest pewn

,

a liczb

,

a ca lkowit

,

a. W´

owczas

m

ed

= m

1+kϕ(n)

= m(m

ϕ(n)

)

k

≡ m( mod n)

(b) Przypadek: m i n nie s

,

a wzgl

,

ednie pierwsze. Wtedy albo p|m albo q|m

(gdyby p|m i q|m to mieliby´

smy sprzeczno´

s´

c z za lo˙zeniem, ´

ze m < n

15

).

Za l´

o˙zmy, ˙ze p|m oraz q 6 |m.

Mamy teraz: m

ed

= m

1+k(p−1)(q−1)

= m(m

q−1

)

k(p−1)

. Ale q ⊥ m (bo

q jest liczb

,

a pierwsz

,

a i q nie dzieli m). Wiemy ˙ze, ϕ(q) = q − 1. A

wi

,

ec m

ed

≡ m · 1

k(p−1)

= m (mod q).

Ostatecznie otrzymali´

smy

m

ed

≡ m (mod q)

Mamy tak˙ze

m

ed

≡ m (mod p)

(bo m ≡ 0 (mod p). Z chi´

nskiego twierdzenia o resztach m jest jedy-

nym rozwi

,

azaniem uk ladu r´

owna´

n

m ≡ l

d

(mod q)

m ≡ 0 (mod p)

(tak czy inaczej mamy m ≡ l

d

(mod n), niezale˙znie od tego, czy m ⊥ n,

czy te˙z nie).

14

Nazwa metody od pierwszych liter nazwisk jej tw´

orc´

ow: Rivest, Shamir i Adleman.

15

Zak ladamy, ˙ze liczby szyfrowane s

,

a mniejsze od n, w przeciwnym przypadku ulega lyby

obci

,

eciu modulo n, a wi

,

ec zniekszta lceniu. Takie szyfrowanie by loby bez sensu!

MATEMATYKA DYSKRETNA 2010

21

8.2. Grupy c.d.

8.2.1. Lemat Burnside’a. Definicja. Niech G b

,

edzie grup

,

a multyplikatywn

,

a. M´

owimy,

˙ze G dzia la na zbiorze X je´

sli jest okre´

slone odwzorowanie ϕ : G × X → X

spe lniaj

,

ace nast

,

epuj

,

ace dwa warunki (piszemy g(x) zamiast ϕ(g, x)):

(1) dla dowolnych g

1

, g

2

∈ G oraz dla ka˙zdego x ∈ X (g

1

· g

2

)(x) = g

1

(g

2

(x))

(2) dla dowolnego x ∈ X e(x) = x (gdzie e jest elementem neutralnym grupy

G).

Przyk lady: grupa Kleina jako podgrupa permutacji na zbiorze {1, 2, 3, 4}.

Twierdzenie 35. Je´

sli grupa G dzia la na zbiorze X, g ∈ G, to g jest bijekcj

,

a.

Dla grupy G dzia laj

,

acej na zbiorze X oraz el. x ∈ X stabilizatorem x nazy-

wamy

Stab x = {g ∈ G : g(x) = x}

Przyk lad ..

Twierdzenie 36. Stabilizator dowolnego elementu x ∈ X jest podgrup

,

a grupy G.

Przyk lad. Grupa obrot´

ow sze´

scianu (foremnego).

Orbit

,

a elementu x ∈ X nazywamy zbi´

or

Orb x = {g(x) : g ∈ G}

Relacja R okre´

slona przez

xRy ⇐⇒ ∃g ∈ G : g(x) = y

jest w X r´

ownowa˙zno´

sciowa.

Twierdzenie 37. Je´

sli sko´

nczona grupa G dzia la na zbiorze X, w´

owczas dla

ka˙zdego x ∈ X

|G| = |Stab x| · |Orb x|

Dow´

od.

Niech x ∈ X. Oznaczmy przez H stabilizator elementu x (czyli: H =

Stab x). Na mocy twierdzenia 36 wiemy, ˙ze H jest podgrup

,

a grupy G. Mo˙zemy

wic, podobnie jak w dowodzie twierdzenia Lagrange’a (tw. 26), rozwa˙za´

c warstwy

grupy G modulo podgrupa H (czyli zbi´

or klas abstrakcji relacji R zdefiniowanej

przez gRh ⇔ gh

−1

∈ H). Przypomnijmy, ˙ze w dowodzie twierdzenia Lagrange’a

zbi´

or warstw G modulo H oznaczyli´

smy przez G/H i wykazali´

smy, ˙ze

• Warstwa dowolnego elementu a ∈ G jest postaci Ha,
• Wszystkie warstwy s

,

a r´

ownoliczne (a poniewa˙z warstw

,

a elementu neutral-

nego jest H, w przypadku sko´

nczonym ka˙zda warstwa ma tyle samo ele-

ment´

ow co podgrupa H).

Tym razem wyka˙zemy, ˙ze ka˙zda warstwa jest r´

ownoliczna ze orbit

,

a elementu x.

Zdefiniujmy funkcj

,

e

ϕ : G/H 3 Hg → g

−1

(x) ∈ Orb x

Nim wyka˙zemy, ˙ze ϕ jest bijekcj

,

a, musimy udowodni´

c, ˙ze

• g

−1

(x) ∈ Orb x

• ϕ jest dobrze okre´slona czyli, ˙ze je˙zeli Hg = Hh, to

22

A. PAWE L WOJDA

Rzeczywi´

scie, w orbicie elementu x s

,

a wzystkie warto´

sci funkcji z G na elemencie

x, no a przecie˙z g

−1

jest elementem G.

Przypu´

s´

cmy teraz, ˙ze Hg = Hh. Poniewa˙z e ∈ H, musi w H istnie´

c taki element

f , ˙ze g = f h A wobec tego

g

−1

(x) = (f h)

−1

(x) ⇒ g

−1

(x) = (h

−1

f

−1

)(x) = h

−1

(f

−1

(x))

Ale f ∈ H, za´

s H jest stabilizatorem x, czyli f

−1

(x) = x i otrzymujemy ostatecznie

g

−1

(x) = h

−1

(x), czyli ϕ(hg) = ϕ(Hh).

• ϕ jest iniektywna: ϕ(Hg) = ϕ(Hh) ⇒ g

−1

(x) = h

−1

(x) ⇒ h ◦ g

−1

(x) =

x ⇒ hg

−1

∈ H ⇒ Hg = Hh

• ϕ jest suriektywna: Niech y ∈ Orb x. W´

owczas istnieje g ∈ G takie, ˙ze

y = g(x), a wtedy y = h

−1

(x) dla h = g

−1

, czyli y = ϕ(Hh).

Przyk lad – ilustracja funkcjonowania twierdzenia 37.
Grupa izometrii pi

,

eciok

,

ata.

Przyk lad. Grupa izometrii wykonalnych sze´

scio´

scianu: 24-elementowa

MATEMATYKA DYSKRETNA 2010

23

9. Wyk lad 9 - 12.V.2010

9.1. Lemat Burnside’a. Dla danej grupy G dzia laj

,

acej na zbiorze X oraz ginG

zbi´

or punkt´

ow sta lych g oznaczamy przez F ix g:

F ix g = {x ∈ X : g(x) = x}

Twierdzenie 38 (Lemat Burnside’a). Niech G b

,

edzie grup

,

a sko´

nczon

,

a dzia laj

,

a-

c

,

a na zbiorze sko´

nczonym X. W´

owczas liczba N orbit zbioru X ze wzgl

,

edu na G

wynosi

N =

1

|G|

X

g∈G

|F ix g|

Przyk lady ...

Dow´

od (metod

,

a podw´

ojnego zliczania)...

9.2. Teoria graf´

ow. Definicja grafu prostego. Rz

,

ad (ozn. |G|) i rozmiar (ozn.

k G k) grafu G. Wierzcho lki po l

,

aczone, wierzcho lki i krawdzie incydentne. Sto-

pie´

n wierzcho lka v (ozn. d

G

(v)) w grafie G.

Twierdzenie 39. Je´

sli G = (V ; E) jest grafem zwyk lym sko´

nczonym, w´

owczas

k G k=

1

2

X

v∈V

d

G

(v)

Wniosek 40. W dowolnym grafie sko´

nczonym liczba wierzcho lk´

ow stopni stopni

nieparzystych jest parzysta.

Twierdzenie 41 (O podawaniu r

,

ak

16

). W dowolnym grafie zwyk lym (prostym)

istniej

,

a co najmniej dwa wierzcho lki tego samego stopnia.

Dow. ...

Definicje trasy, ´

scie ˙zki, drogi, cyklu w grafie. Graf sp´

ojny.

Twierdzenie 42. Je´

sli graf G ma dok ladnie dwa wierzcho lki stopnia nieparzystego,

to wierzcho lki te po l

,

aczone s

,

a ´

scie˙zk

,

a (a co za tym idzie, s

,

a we wsp´

olnej sk ladowej).

Dow. ...

9.2.1. Grafy eulerowskie. Definicja multigrafu (grafu)
Definicja cyklu Eulera, graf´

ow eulerowskich. Anegdota o mostach kr´

olewieckich.

Twierdzenie 43 (Eulera). Multigraf bez wierzcho lk´

ow izolowanych jest eulerowski

wtedy i tylko wtedy gdy

(1) jest sp´

ojny,

(2) stopie´

n dowolnego wierzcho lka jest parzysty.

Dow. ...

16

Handshaking Theorem

24

A. PAWE L WOJDA

10. Wyk lad 10 - 19.V.2010

10.1. Grafy eulerowskie c.d.

Wniosek 44. W multigrafie G bez wierzcho lk´

ow izolowanych istnieje (otwarta)

droga eulerowska wtedy i tylko wtedy, gdy

(1) G jest sp´

ojny,

(2) dok ladnie dwa wierzcho lki G s

,

a stopnia nieparzystego.

Dow. ...

Algorytm Fleury’ego znajdowania cyklu Eulera.
Algorytm ten znajduje cykl Eulera w grafie

17

spe lniaj

,

acym warunki twierdzenia

Eulera (graf sp´

ojny, stopnie wszystkich wierzcho lk´

ow parzyste).

Algorytm dzia la wed lug nast

,

epuj

,

acych regu l.

(1) Algorytm rozpoczyna swoje dzia lanie od dowolnego wierzcho lka u (od tego

jednak momentu ju˙z ustalonego).

(2) Tworzymy ci

,

ag ES, do kt´

orego w ka˙zdej kolejnej iteracji dopisujemy nast

,

epn

,

a

kraw

,

ed´

z e tworzonego cyklu eulerowskiego, kt´

or

,

a z kolei wyrzucamy ze

zbioru kraw

,

edzi grafu, tworz

,

ac w ten spos´

ob bie˙z

,

acy graf G

0

. Je´

sli w wy-

niku tej operacji w grafie pojawia si

,

e wierzcho lek izolowany (stopnia zero),

w´

owczas usuwamy go tak˙ze.

Powiedzmy, ˙ze ostatnim wierzcho lkiem, do kt´

orego dotarli´

smy jest wierzcho lek

v nie izolowany w bie˙z

,

acym grafie G

0

. Niech e b

,

edzie kraw

,

edzi

,

a G

0

tak

,

a, ˙ze

• jednym z jej ko´

nc´

ow jest v a drugim, powiedzmy, w.

• G

0

− {e} jest dalej sp´

ojny (chyba, ˙ze stopie´

n v w G

0

jest r´

owny 1).

Uwaga: To, ˙ze e mo˙zna tak w la´

snie wybra´

c, udowodnimy p´

o´

zniej.

• Do ci

,

agu ES dopisujemy e, G

0

(graf bie˙z

,

acy) zast

,

epujemy przez G

0

− {e}

(je´

sli v sta l si

,

e po tej operacji izolowany, to usuwamy go z grafu r´

ownie˙z).

Je´

sli w jest w nowym grafie G

0

izolowany, algorytm si

,

e ko´

nczy. Skonstru-

owali´

smy cykl Eulera. Je´

sli nie, kontynuujemy od wierzcho lka w.

Jest oczywistym, ˙ze algorytm si

,

e ko´

nczy, gdy graf G

0

nie ma ju˙z kraw

,

edzi, a wi

,

ec

gdy ES jest ci

,

agiem kraw

,

edzi tworz

,

acym cykl Eulera.

Pozostaje jednak wykaza´

c, ˙ze algorytm jest wykonalny, to znaczy, ˙ze w ka˙zdym

etapie mo˙zna w G

0

wybra´

c tak

,

a kraw

,

ed´

z e o ko´

ncu w v, ˙ze G

0

− {e} jest sp´

ojny

chyba, ˙ze v w G

0

− {e} jest izolowany (wtedy v tak˙ze z G

0

usuwamy i w dalszym

ci

,

agu mamy, rzecz jasna, graf sp´

ojny)

18

.

W tym celu zauwa˙zmy, ˙ze graf G

0

jest sp´

ojny (z konstrukcji) oraz, ˙ze w G

0

albo

(i) s

,

a dok ladnie 2 wierzcho lki stopnia nieparzystego (jednym z nich jest wtedy

u a drugim v),
albo

(ii) wszystkie wierzcho lki s

,

a stopnia parzystego (tak b

,

edzie jesli v = u).

W przypadku (i) do l

,

aczamy do G

0

now

,

a kraw

,

ed´

z l

,

acz

,

ac

,

a u i v (wierzcho lki stopni

nieparzystych).
W dugim przypadku nie robimy nic

19

.

W obu przypadkach w efekcie otrzymujemy graf, kt´

ory jest sp´

ojny (bo G

0

taki

17

Zamiast m´

owi´

c (pisa´

c) multigraf najcz

,

e´

sciej m´

owimy i piszemy graf

18

Prosz

,

e zauwa ˙zy´

c, ˙ze ten dow´

od jest, niewiele ale jednak, r´

o ˙zny od tego, kt´

ory by l podany

ma wyk ladzie. Oba s

,

a dobre.

19

Czyli to, co lubimy najbardziej!

MATEMATYKA DYSKRETNA 2010

25

by l) i ma wszystkie wierzcho lki stopnia parzystego. Jest wi

,

ec eulerowski (na mocy

twierdzenia Eulera). Latwo stwierdzi´

c teraz, ˙ze mo˙zna tak wybra´

c e, kraw

,

ed´

z o

jednym ko´

ncu w v, by G

0

−{e} by l sp´

ojny (chyba, ˙ze d

G

0

(v) = 1, lecz ten przypadek,

to najmniejszy problem, opisany zosta l ju˙z powy˙zej).

10.2. Grafy p laskie i planarne. Definicja graf´

ow p laskich i planarnych.

Regiony. Stopie´

n regionu (podczas wyk ladu stopie´

n oznacza le inaczej, lepiej jest

jednak oznacza´

c tak jak poni˙zej, czyli przez deg R).

Twierdzenie 45 (Euler). Je´

sli G jest grafem p laskim rz

,

edu n o rozmiarze m i o

f regionach, w´

owczas

n = m − f + 2

Dow. ...
Definicja stopnia regionu: stopniem regionu deg R nazywamy d lugo´

s´

c (liczb

,

e

kraw

,

edzi) najkr´

otszej drogi stanowi

,

acej jego brzeg.

Twierdzenie 46. Je´

sli G jest grafem p laskim o regionach R

1

, . . . , R

f

oraz rozmia-

rze m, w´

owczas

f

X

i=1

deg R

i

= 2m

26

A. PAWE L WOJDA

11. Wyk lad 11 - 26.V.2010

11.1. Garfy planarne c.d. Udowodnili´

smy nast

,

epuj

,

acy wniosek z twierdzenia 45

(Eulera).

Wniosek 47. Je´

sli G jest grafem planarnym sp´

ojnym bez p

,

etli i kraw

,

edzi wielo-

krotnych rz

,

edu n, rozmiaru m i o f regionach, w´

owczas

(1) 3f ≤ 2m
(2) m ≤ 3n − 6

Wniosek 48. Grafy K

5

i K

3,3

nie s

,

a planarne.

Def. bry ly regularnej.
Siatki wielo´

scian´

ow.

Twierdzenie 49 (O bry lach plato´

nskich). Jedynymi bry lami regularnymi s

,

a czworo´

scian,

sze´

scian, o´

smio´

scian, dwunasto´

scian i dwudziesto´

scian.

Dow´

od....

Twierdzenie 50 (K. Kuratowski). Graf prosty G jest planarny wtedy i tylko wtedy
gdy nie zawiera podgraf´

ow homeomorficznych z K

5

ani z K

3,3

.

11.2. Drzewa i lasy. Drzewem nazywamy dowolny graf prosty (tzn. bez p

,

etli

i kraw

,

edzi wielokrotnych) sp´

ojny i bez cykli. Las to graf, kt´

orego ka˙zda sk ladowa

jest drzewem.

Twierdzenie 51. Graf prosty jest drzewem wtedy i tylo wtedy, gdy dowolne dwa
jego wierzcho lki po l

,

aczone s

,

a dok ladnie jedn

,

a ´

scie˙zk

,

a.

Dow´

od. ...

Twierdzenie 52. Je´

sli graf T jest drzewem, w´

owczas k T k= |T | − 1.

Dow´

od. ...

Twierdzenie 53 (O w lasno´

sciach drzew). Niech T = (V ; E) b

,

edzie grafem zwyk lym.

Nast

,

epuj

,

ace warunki s

,

a r´

ownowa˙zne.

(1) T jest drzewem.
(2) T jest sp´

ojny i dla dowolnego e ∈ E graf T − e nie jest sp´

ojny.

(3) T nie zawiera cykli i |T | =k T k +1
(4) T jest sp´

ojny i |T | =k T k +1

(5) T nie zaweiera cykli i dla dowolnych niepo l

,

aczonych wierzcho lk´

ow a, b grafu

T graf T ∪ {ab} zawiera dok ladnie jeden cykl.

Uwaga: T ∪ {ab} to graf otrzymany z T przez dodanie kraw

,

edzi ab (inaczej:

przez po laczenie wierzcho lk´

ow a i b kraw

,

edzi

,

a).

Dow. ...

Twierdzenie 54. Niech T b

,

edzie dowolnym drzewem za´

s v jego dowolnym wierz-

cho lkiem. W´

owczas istnieje taka numeracja wierzcho lk´

ow T : v = v

1

, v

2

, . . . , v

n

oraz kraw

,

edzi e

1

, e

2

, . . . , e

n−1

, ˙ze wierzcho lek v

i+1

jest po l

,

aczony z dok ladnie jed-

nym spo´

sr´

od wierzcho lk´

ow v

1

, ..., v

i−1

kraw

,

edzi

,

a e

i

.

Przyk lad...

MATEMATYKA DYSKRETNA 2010

27

Macierz incydencji grafu G. M = (a

ij

) nazywamy macierz

,

a incydencji grafu

G o zbiorach wierzcho lk´

ow {v

1

, . . . , v

n

} i kraw

,

edzi {e

1

, . . . , e

m

} je˙zeli

a

ij

=



1

je´

sli wierzcho lek v

i

jest jednym z ko´

nc´

ow kraw

,

edzi e

j

,

0

w przeciwnym przypadku

Przyk lad...

28

A. PAWE L WOJDA

12. Wyk lad 12 - 2.VI.2010

Uwaga egzamin!

Przypominam:

Egzamin pisemny 22-go czerwca w U2, 9-12

Egzamin ustny dla s´

ob zwolnionych z pisemnego na podstawie

wysokich ocen z zalicze´

n:

22-go czerwca w B.7, na I pi

,

etrze w moim pokoju od godz. 8.00

(numeru pokoju nie pami

,

etam, jestem w nim zaledwie 12 ostatich lat, ale ka˙zde

dziecko wska˙ze)

lista szczeg´

o lowa, z orientacyjnym terminem rozpocz

,

ecia egzaminu uka˙ze si

,

e w

terminie p´

o´

zniejszym.

II termin: 20 wrze´

snia, 9-12, w s. 1.8 paw. B7 (Czarnowiejska 70, za

budynkiem Metalurgii)

III termin: 27 wrze´

snia w s. 2.1 B7

12.1. Drzewa c.d.

Wniosek 55. Macierz incydencji drzewa rz

,

edu n jest rz

,

edu n − 1.

Dow. ...

12.2. Drzewa jako przestrzenie metryczne. Niech G b

,

edzie grafem prostym.

Odleg lo´

sci

,

a wierzcho lk´

ow a i b nazywamy liczb

,

e dist

G

(a, b) r´

own

,

a d lugo´

sci

najkr´

otszej ´

scie˙zki z a do b.

dist

G

spe lnia warunki metryki.

Ekscentryczno´

sci

,

a wierzcho lka a grafu G = (V ; E) nazywamy

Ec

G

= max{dist

G

(a, b) : b ∈ V }

Wierzcho lek centralny to wierzcho lek o ekscentryczno´

sci najmniejszej w grafie,

peryferyjny to taki, kt´

ory ma ekscentryczno´

s´

c maksysmaln

,

a. Centrum grafu to

zbi´

or wierzcho lk´

ow centralnych.

Twierdzenie 56 (D˝

ones K˝

onig). Ka˙zde drzewo ma centrum z lo˙zone z jednego lub

dw´

och po l

,

aczonych wierzcho lk´

ow.

Dow´

od - ladny i latwy. Podczas wyk ladu nie powiedzia lem, ˙ze twierdzenie to

jako pierwszy udowodni l D˝

ones K˝

onig

20

.

12.3. Drzewa z korzeniem i drzewa binarne. Korze´

n drzewa T - dowolny,

wyr´

o˙zniony wierzcho lek.

Drzewo binarne - drzewo, w kt´

orym korze´

n jest wierzcho lkiem stopnia 2, pozo-

sta le wierzcho lki s

,

a stopnia 3 lub 1 (li´

scie)

Poziom wierzcho lka w drzewie (z korzeniem) - odleg lo´

s´

c od korzenia.

Wysoko´

s´

c drzewa - maksymalna odleg lo´

s´

c wiercho lka od korzenia.

20

W

,

egierski matematyk, kt´

ory w 1935 roku opublikowa l w la´

sciwie pierwsz

,

a monografi

,

e z teorii

graf´

ow. Ta ksi

,

a˙zka jest bardzo szczeg´

olna tak´

ze dlatego, ˙ze zawiera wiele nowych twierdze´

n. St

,

ad

wi

,

ekszo´

s´

c wynik´

ow K˝

oniga ma dat

,

e 1935. Opublikowanie jego monografii spowodowa lo ogromne

zwi

,

ekszenie zainteresowania teori

,

a graf´

ow. Pewno K˝

onig jest w znacznie wi

,

ekszym stopniu ojcem

teorii graf´

ow ni˙z Euler. Ale po co te rozwa ˙zania? Czy mo˙zna by´

c bardziej ojcem czego´

s ni˙z kto

inny? :)

MATEMATYKA DYSKRETNA 2010

29

Przyk lad 3. Model funkcjonowania automatu rozpoznaj

,

acego monety - drzewo bi-

narne o 9 wierzcho lkach.

Twierdzenie 57. Ka˙zde drzewo binarne ma rz

,

ad nieparzysty.

Dow. ...

Twierdzenie 58. W dowolnym drzewie binarnym T rz

,

edu n jest p =

n+1

2

li´

sci i

k =

n−3

2

wierzcho lk´

ow stopnia 3.

Twierdzenie 59. Niech T b

,

edzie drzewem binarnym o p li´

sciach i wysoko´

sci h.

W´

owczas h ≥ dlog pe.

12.4. Dendryty. Dendrytem grafu G nazywamy podgraf T tego grafu, kt´

ory

jest drzewem i |T | = |G|.

Twierdzenie 60. Graf G jest sp´

ojny wtedy i tylko wtedy gdy ma dendryt.

ALGORYTM DRZEWO

Grafy z wagami. Problem minimalnego dendrytu. Algorytmy Kruskala i
Prima

21

znajdowania dendrytu minimalnego.

Podczas wyk ladu obieca lem, ˙ze w tych notatkach podam te algorytmy (jeszcze raz,
bo podczas wyk ladu (chyba?) poda lem) i na dodatek napisz

,

e dowody. Przepra-

szam, ale nie zd

,

a˙ze. Mam inn

,

a propozycj

,

e. T

,

e cz

,

e´

s´

c wyk ladu realizuj

,

e wed lug

ksi

,

a˙zki Rossa i Wrighta [6]. Je´

sli jeste´

scie ciekawi (mam nadziej

,

e, ˙ze jeste´

scie,

wiem, ˙ze nie wszyscy), zar´

owno algorytmy jak i dowody ich funkcjonowania na

stronach 382-291 tej ksi

,

a˙zki. Tam te˙z algorytm DRZEWO.

21

Zaniepokoi lo mnie, ˙ze nie wiedzia lem podczas wyk ladu kim by l Prim i w zwi

,

azku z tym, jak

nale ˙zy czyta´

c jego nazwisko. Ju˙z wiem! To ameryka´

nski matematyk (Princeton), Robert Clay

Prim (1921 - ) - chyba ˙zyj

,

acy, bo Wikipedia podaje tylko dat

,

e urodzenia. A wi

,

ec czytamy to

nazwisko po angielsku. Dowiedzia lem si

,

e tak˙ze innych, ciekawych rzeczy (w [3] - to naprawd

,

e

´

swietna ksi

,

a ˙zka!). Ot´

o˙z znacznie przed Kruskalem i Primem blisko podania algorytm´

ow znaj-

dowanie dendryt´

ow optymalnych byli czeski matematyk Otakar Bor ˙uvka (1899-1995, nad u jest

k´

o lko, nie kropka, ale nie umiem) oraz Jan Czekanowski (1882-1965). W tym drugim przypadku

najciekawsze jest nie to, ˙ze Czekanowski byl Polakiem (innym te ˙z to si

,

e zda˙za), lecz fakt, ˙ze to

antropolog (cho´

c matematyk

,

e te ˙z studiowa l - ciekawe informacje o nim w Wikipedii).

30

A. PAWE L WOJDA

13. Wyk lad 13 - 9.VI.2010

13.1. Kolorowanie wierzcho lk´

ow grafu

Liczba

chromatyczna. Kolorowaniem

wierzcho lk´

ow grafu (prostego

22

)

G = (V ; E) nazywamy dowoln

,

a funkcj

,

e

c : E → C

gdzie C jest sko´

nczonym zbiorem, nazywanym zbiorem kolor´

ow.

Kolorowanie jest w la´

sciwe je´

sli spe lnia warunek xy ∈ E ⇒ c(x) 6= c(y).

Liczba chromatyczna grafu G:

χ(G) = min{k : ∃c : E → [1, k], c - kolorowanie w la´

sciwe grafu G}

Przyk lad 4. χ(C

2k

) = 2,

χ(C

2k+1

) = 3, χ(K

n

) = n

Problem i twierdzenie o 4-kolorowalno´

sci graf´

ow planarnych (historia problemu

czterech kolor´

ow).

Przyk lady...

Definicja 7. κ(G) = max{k : G jest k − sp´

ojny}

∆(G) = max{d

G

(v) : v ∈ V }

Twierdzenie 61 (???

23

). Dla dowolnego grafu prostego G prawdziwa jest nier´

owno´

s´

c

χ(G) ≤ ∆(G).

Dow. ...

Twierdzenie 62 (Brooks). Je´

sli G jest grafem sp´

ojnym i nie jest ani cyklem

nieparzystym ani grafem pe lnym, to χ(G) ≤ ∆(G)

Dow´

od twierdzenia Brooksa nie poda lem podczas wyk ladu.

13.2. Wielomiany chromatyczne. Oznaczmy przez d

i

liczb

,

e pokolorowa´

n w la-

´

sciwych wierzcho lk´

ow grafu (prostego) G rz

,

edu n. W´

owcza wierzcho lki G mo˙zna

pokolorowa´

c (w spos´

ob w la´

sciwy) d

i

λ

i

kolorami. St

,

ad oczywi´

scie istnieje

(7)

P

G

(λ) =

n

X

i=1

d

i

λ

i



r´

o˙znych pokolorowa´

n w la´

sciwych wierzcho lk´

ow grafu G. Zauwa˙zmy, ˙ze nie istnieje

pokolowanie 0 kolorami ani wi

,

ecej ni˙z n kolorami, st

,

ad rzeczywi´

scie we wzorze (7)

sumowanie mo˙zna rozpocz

,

a´

c od i = 0 i zako´

nczy´

c na i − n. P

G

(λ) zdefiniowane

wzorem (7) nazywamy wielomianem charakterystycznym grafu G

24

Przyk lad.

22

Mo ˙zna m´

owi´

c o kolorowaniu wierzcho lk´

ow, a tak ˙ze kraw

,

edzi, graf´

ow niekoniecznie pro-

stych, szczeg´

olnie ma to sens w przypadku kolorowania kraw

,

edzi multigraf´

ow, kraw

,

edzi i/lub

wierzcho lk´

ow graf´

ow skierowanych. O tego typu kolorowaniach nie b

,

ed

,

e jednak m´

owi l w trakcie

wyk lad´

ow.

23

To twierdzenie jest powszechnie znane, nie wiadomo kto je jako pierwszy udowodni l. W

literaturze angielskoj

,

ezycznej pisze si

,

e w takich przypadkach folclore. Mo˙ze mi kto´

s podpowie,

jak to mo ˙zna okre´

sli´

c po polsku?

24

We wzorze (7) λ oznacza r´

ownocze´

snie liczb

,

e kolor´

ow i zmienn

,

a nieokre´

slon

,

a wielomianu

(zazwyczaj oznaczan

,

a przez x). Ta podw´

ojna rola, kt´

or

,

a odgrywa tu λ formalnie jest niezupe lnoie

poprawna, nie prowadzi jednak do nieporozumie´

n.

MATEMATYKA DYSKRETNA 2010

31

Twierdzenie 63. P

K

n

(λ) = λ(λ − 1) · ... · (λ − n + 1)

Dow. ...

Twierdzenie 64. P

P

n

(λ) = λ(λ − 1)

n−1

Niech a i b b

,

ed

,

a dwoma wierzcho lkami nie po l

,

aczonymi w grafie G. Przez G

0

oznaczmy graf powsta ly z G przez po l

,

aczenie wierzcho lk´

ow a i b kraw

,

edzi

,

a, za´

s przez

G

00

graf powsta ly przez zast

,

apienie w G wierzcho lk´

ow a i b jednym wierzcho lkiem

c po l

,

aczonym z wszystkimi wierzcho lkami po l

,

aczonymi w G z a lub z b.

Twierdzenie 65 (Whitney).

P

G

(λ) = P

G

0

(λ) + P

G

00

(λ)

Dow. ...

Przyk lad...
Zauwa˙zyli´

smy, ˙ze twierdzenie Whitneya daje metod

,

e (co prawda kompletnie algo-

rytmicznie nieefektywn

,

a) znajdowania wielomianu chromatycznego grafu.

13.3. Kolorowanie kraw

,

edzi. Kolorowaniem krw

,

edzi grafu prostego G =

(V ; E) nazywamy dowoln

,

a funkcj

,

e

c : E → C

Kolorowanie kraw

,

edzi jest w la´

sciwe je´

sli kraw

,

edzie incydentne s

,

a r´

o˙znych kolor´

ow.

Minimaln

,

a liczb

,

e kolor´

ow konieczn

,

a do pokolorowania w la´

sciwego kraw

,

edzi grafu

G nazywamy indeksem chromatycznym i oznaczamy przez χ

0

(G).

Twierdzenie 66 (Twierdzenie Vizinga). Dla dowolnego grafu prostego

∆(G) ≤ χ

0

(G) ≤ ∆(G) + 1

Dow´

od twierdzenia Vizinga nie by l podany podczas wyk ladu.

13.4. Grafy skierowne i turnieje.

Definicja 8. Grafem prostym skierowanym nazywamy G = (V ; E), gdzie
E ⊂ V × V − {(x, x) : x ∈ V }.
Elementy zbioru V nazywamy wierzcho lkami za´

s elementy zbioru E lukami grafu

G.
Turniejem nazywamy graf skierowany w kt´

orym dowolne dwa wierzcho lki po l

,

aczone

s

,

a dok ladnie jednym lukiem.

Przyk lady.

Definicja 9. ´

Scie ˙zka o pocz

,

atku w x i ko´

ncu w y, to ci

,

ag

(x = a

1

, e

1

, a

2

, e

2

, ..., a

k−1

e

k−1

, a

k

= y)

wierzcho lk´

ow a

1

, ..., a

k

i luk´

ow e

1

, ..., e

k−1

takich, ˙ze e

i

= (a

i

, a

i+1

) dla i = 1, ..., k

oraz a

i

6= a

j

dla i 6= j.

´

Scie˙zk

,

e nazywamy hamiltonowsk

,

a (albo Hamiltona) je´

sli zawiera wszystkie wierz-

cho lki grafu.

Twierdzenie 67 (R´

edei). Ka˙zdy turniej zawiera ´

scie˙zk

,

e (skierowan

,

a) Hamiltona.

Dow. ...

32

A. PAWE L WOJDA

14. Wyk lad 14 - 16.VI.2010

Terminy egzamin´

ow:

I (i oby ostatni): 22 czerwca godz. 9.00 w U2 - pisemny

Dla tych, kt´

orzy z pisemnej cz

,

e´

sci egzaminu b

,

ed

,

a zwolnieni, cz

,

e´

s´

c

ustna w B7, tak ˙ze 22-go od (zapewne) 9.00

szczeg´

o ly og losz

,

e, gdy b

,

ed

,

e wiedzia l dok ladnie kto jest zwolniony

II i III termin: 20 o 9.00 i 27 wrze´

snia o 13.30 w B7

Szczerze, troch

,

e egoistycznie, ˙zycz

,

e powodzenia!!!

14.1. Turnieje -ci

,

ag dalszy.

Definicja 10. W dowolnym grafie skierowanym G oznaczamy d

+
G

(v) = |{u ∈ V :

(v, u) ∈ E}|. i nazywamy p´

o lstopniem wierzcho lka v. Je´

sli G jest turniejem,

w´

owczas wektor (a

1

≤ a

2

≤ ... ≤ a

n

) p´

o lstopni wierzcho lk´

ow G nazywamy wekto-

rem wynik´

ow turnieju G..

Twierdzenie 68 (Landau). Ci

,

ag niemalej

,

acy (a

1

≤ a

2

≤ ... ≤ a

n

) jest wektorem

wynik´

ow pewnego turnieju wtedy i tylko wtedy gdy

k

X

i=1

a

i

≤

n

k



dla ka˙zdego k, 1 ≤ k ≤ n, przy czym dla k = n zachodzi r´

owno´

s´

c.

Dowodu nie b

,

ed

,

e podaswa l, cho´

c ladny. Jako ciekawostk

,

e mog

,

e jednak poda´

c,

˙ze autor twierdzenia, Landau, nie by l matematykiem.

Nie jest to tak˙ze znany

fizyk o tym nazwisku. Chodzi o biologa. Twierdzenie Landaua bywa cytowane
w pracach biologicznych. Sam czyta lem kiedy´

s prac

,

e naukow

,

a o zachowaniu ma-

kak´

ow (to takie ma lpy). Turniejami w pracy o makakach by ly walki pomi

,

edzy

makakami. Uczony bada l, czy jest jaka´

s relacja pomi

,

edzy wynikami (niegro´

znych)

walk makak´

ow a cz

,

esto´

sci

,

a wzajemnych pieszczot (polegaj

,

acymi na wzajemnym

pozbawianiu si

,

e dokuczliwych insekt´

ow).

14.2. Liczba nieizomorficznych turniej´

ow rz

,

edu n.

Twierdzenie 69. Niech σ ∈ S

n

b

,

edzie permutacj

,

a typu d = 1

d

1

2

d

2

...n

d

n

dzia laj

,

ac

,

a

na zbiorze turniej´

ow rz

,

edu n. Je´

sli σ ma cykl

25

d lugo´

sci parzystej (czyli je´

sli d

2k

> 0

dla pewnego k) |F ix σ| = 0. W przeciwnym przypadku |F ix σ| = 2

t(d)

, gdzie

t(d) =

1

2





n

X

i,j=1

(i, j)d

i

d

j

−

n

X

i=1

d

i





Uwaga. (i, j) to, jak pami

,

etamy, NWD(i, j). W dowodzie s

,

a wykorzystywane

lemat Burnside’a oraz twierdzenie Cauchyego. Warto wi

,

ec sobie te twierdzenia

przypomnie´

c.

Dow.

Najpierw wyka˙zemy, ˙ze gdy jeden z cykli jest parzysty, w´

owczas |F ix σ| = 0. Rze-

czywi´

scie, przypu´

s´

cmy, ˙ze istnieje cykl (a

1

, a

2

, ..., a

2i

). Bez straty og´

olno´

sci mo˙zemy

25

Oczywi´

scie mowa tu o cyklach permutacji σ w rozk ladzie na cykle (permutacje cykliczne)

roz l

,

aczne. Pami

,

etamy, ˙ze taki rozk lad istnieje i jest jednoznaczny.

MATEMATYKA DYSKRETNA 2010

33

za lo˙zy´

c, ˙ze (a

1

, a

1+

i

2

) ∈ E(T ). Gdyby σ(T ) = T w´

owczas σ(a

1

, a

1+

i

2

) ∈ E(T ),

σ

2

(a

1

, a

1+

i

2

) ∈ E(T ), etc. W szczeg´

olno´

sci σ

i

2

(a

1

, a

1+

i

2

) ∈ E(T ). Tymczasem

σ

i

2

(a

1

, a

1+

i

2

) = (a

1+

i

2

, a

1

), a to jest sprzeczne z za lo˙zeniem, ˙ze T jest turniejem

(w turnieju dwa wierzcho lki s

,

a po l

,

aczone dok ladnie jednym lukiem, a nie dwoma,

przeciwnie skierowanymi lukami.

Od tego momentu b

,

edziemy zak ladali, ˙ze wszystkie cykle permutacji σ s

,

a niepa-

rzyste (inaczej: d

2

= d

4

= ... = 0).

Niech wi

,

ec b

,

edzie cykl (nieparzysty) (a

1

, ..., a

i

) permutacji σ. Na wierzcho lkach tego

cyklu mo˙zna zbudowa´

c 2

i−1

2

r´

o˙znych turniej´

ow T

i

(rz

,

edu i) takich, ˙ze σ(T

i

) = T

i

.

Bierze si

,

e to st

,

ad, ˙ze ka˙zd

,

a ci

,

eciw

,

e tego cyklu

26

a

1

, a

α

mo˙zna nada´

c jedn

,

a z dw´

och

orientacji (kt´

ore zostaj

,

a zachowane po wzi

,

eciu na nich warto´

sci permutacji σ i jej

kolejnych pot

,

eg).

Dla wszystkich cykli d lugo´

sci (nieparzystej!) i otrzymamy 2

d

i

i−1

2

turniej´

ow T

i

ta-

kich, ˙ze σ(T

i

) = T

i

. A dla wszystkich cykli permutacji lacznie 2

P

n
i=1

d

i

i−1

2

turniej´

ow

na kt´

orych permutacja σ jest sta la.

Teraz zajmijmy si

,

e mo˙zliw

,

a orientacj

,

a luk´

ow pomi

,

edzy cyklami tej samej d lugo´

sci

i (liczb

,

e tych cykli w turnieju oznaczyli´

smy przez d

i

. Mo˙zliwo´

sci wybnoru luk´

ow

pomi

,

edzy cyklami d lugo´

sci jest i, za´

s wszystkich par

d

i

2

. Mamy wi

,

ec 2(

dj

2

)

i

mo˙zliwo´

sci.

Rozpatrzmy teraz przypadek cykli o r´

o˙znych d lugo´

sciach i oraz j, powiedzmy

(a

1

, ..., a

i

) i (b

1

, ..., b

j

). Orbita dowolnego luku, powiedzmy, dla ustalenia uwagi,

(a

1

, b

1

) ma NWW(i, j) element´

ow. Poniewa˙z za´

s tych luk´

ow pomi

,

edzy {a

1

, ..., a

i

}

a {b

1

, ..., b

j

} jest i·j, to luk´

ow o kt´

orych orientacji mo˙zemy rozstrzyga´

c dowolnie jest

i·j

NWW

(i,j)

=NWD(i, j) = (i, j) (przypominam, ˙ze (i, j) to tylko inne oznaczenie

dla NWD). Mamy wi

,

ec 2

(i,j)

mo˙zliwo´

sci.

Ostatecznie turniej´

ow T spe lniaj

,

acych σ(T ) = T jest 2

t(d)

, gdzie

t(d) =

n

X

i=1

d

i

(i − 1)

2

+

n

X

i=1

d

i

2



i +

X

1≤i<j≤n

d

i

d

j

(i, j)

a po przeliczeniach ( latwych) otrzymamy, dla dowolnej permutacji σ typu 2

d

1

...n

d

n

,

(d = (d

1

, ..., d

n

) i d

2

= ... = 0):

t(d) =

1

2





X

i,j

d

i

d

j

(i, j) −

n

X

i=1

d

i





Twierdzenie 70 (Davis). Liczba nieizomorficznych turniej´

ow T (n) rz

,

edu n dana

jest wzorem

T (n) =

∗

X

d

2

t(d)

Q i

d

i

di!

(gdzie t(d) jest okre´

slone w twierdzeniu poprzednim, za´

s

P

∗
d

oznacza sum

,

e po

wszystkich d spe lniaj

,

acych d

1

+ 3d

3

+ 3d

+

... + nd

n

= n oraz d

2l

= 0 dla ka˙zdego l).

26

Tu dalej mamy do czynienia z cyklem permutacji (a

1

, ..., a

i

), co nie przeszkadza nam jednak

traktowa´

c {a

1

, ..., a

i

} jako wierzcho lk´

ow turniej´

ow i budowa´

c na nich cyklu z ci

,

eciwami!

34

A. PAWE L WOJDA

Dow´

od. W dowodzie wykorzystamy

• lemat Burnside’a
• twierdzenie Cauchy’ego o tym, ˙ze wszystkich permutacji typu d = 1

d

1

2

d

2

...n

d

n

jest

n!

1

d

1

d

1

!2

d

2

d

2

!...n

d

n

d

n

!

Rzeczywi´

scie, wykorzystuj

,

ac twierdzenie 69, lemat Burnside’a i twierdzenie Cau-

chy’ego (twierdzenie 13) otrzymujemy:

T (n) =

1

n!

X

σ∈S

n

|Fix σ| =

∗

X

d

n!

1

d

1

d

1

!...n

d

n

d

n

!

2

t(d)

=

∗

X

d

2

t(d)

Q

i

i

d

i

d

i

!

MATEMATYKA DYSKRETNA 2010

35

Literatura

[1] M. Aigner i G.M. Ziegler, Dowody z Ksi

,

egi, PWN, Warszawa 2002.

[2] W.J Gilbert, W.K. Nicholson, Algebra wsp´

o lczesna z zastosowaniami, WNT, Warszawa 2008.

[3] R.P. Grimaldi, Discrete and Combinatorial Mathematics - An Appiled Introduction, Addison-

Wesley 1994.

[4] N. Koblitz, Algebraiczne aspekty kryptografii, WNT, Warszawa 2000
[5] Zb. Palka i A. Ruci´

nski, Wyk lady z kombinatoryki, WNT 2004.

[6] K.A Ross i Ch.R.B. Wright, Matematyka dyskretna, PWN 2000.
[7] E.R. Scheinerman, Mathematics - Discrete Introduction, Brooks/Cole 2000.
[8] R.J. Wilson, Wprowadzenie do teorii graf´

ow, PWN 1998.