plik

MATEMATYKA DYSKRETNA 2010

A. PAWE L WOJDA

Spis tre´

sci

Wyk lad 1 - 3.III.2010

1.1.

Matematyka dyskretna

1.2.

Zasada indukcji matematycznej

1.3.

R´

ownania rekurencyjne

Wyk lad 2 - 10.III.2010

2.1.

Wyznacznik Vandermonde’a

2.2.

R´

ownania rekurencyjne liniowe

2.3.

Metody zliczania

Wyk lad 3 - 17.III.2010

3.1.

Metody zliczania c.d.

Wyk lad 4 - 24.III.2010

4.1.

Metody zliczania c.dc.d.

4.2.

Arytmetyka modularna

Wyk lad 5 - 31.III.2010

5.1.

Arytmetyka modularna c.d.

5.2.

Grupy

Wyk lad 6 - 21.IV.2010

6.1.

Grupy c.d.

Wyk lad 7 - 28.IV.2010

7.1.

Grupy c.d.c.d.

7.2.

Kwadratowe residua modulo

7.3.

Zasady kryptografii z kluczem publicznym

7.4.

Metoda Rabina

Wyk lad 8 - 5.V.2010

8.1.

Metoda RSA

8.2.

Grupy c.d.

Wyk lad 9 - 12.V.2010

9.1.

Lemat Burnside’a

9.2.

Teoria graf´

10.

Wyk lad 10 - 19.V.2010

10.1.

Grafy eulerowskie c.d.

10.2.

Grafy p laskie i planarne

11.

Wyk lad 11 - 26.V.2010

11.1.

Garfy planarne c.d.

11.2.

Drzewa i lasy

12.

Wyk lad 12 - 2.VI.2010

12.1.

Drzewa c.d.

12.2.

Drzewa jako przestrzenie metryczne

MATEMATYKA DYSKRETNA 2010

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

. 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-

a zegarka, za´

s matematyk

e dyskretn

a ze zmieniaj

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=k

(gdzie k jest pewn

a liczb

a naturaln

a).

• Je˙zeli zdanie T

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

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

u lo˙zone od najwi

ekszego na dole do najmniejszego na wierzchu). K´

o lka przek lada

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´

po lo˙zone na mniejszym.
Problem jest nast

epuj

acy: w ilu ruchach da si

e rozwi

aza´

c nasze zadanie?

Oznaczmy przez a

liczb

e koniecznych ruch´

ow przy n k´

o lkach. Z latwo´

sci

a stwier-

dzamy, ˙ze a

= 0, a

= 1 no i niezbyt trudno jest zauwa˙zy´

c, ˙ze a

= 2a

n−1

+ 1 (dla

n > 0). St

ad latwo obliczy´

c, ˙ze a

= 3, a

= 7, a

= 15. Te liczby sugeruj

a og´

olny

wz´

or. No i rzeczywi´

scie, indukcyjnie udowodnili´

smy, ˙ze

= 2

− 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

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.

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

) w nast

epuj

acy spos´

ob.

• Dane s

a warto´

sci a

, a

, ..., a

k−1

(a wi

ec k pierwszych wyraz´

ow ci

agu) oraz

wz´

• a

= f (a

n−1

, a

n−2

, ...a

n−k

), gdzie f jest pewn

a funkcj

Zdefiniowany w taki spos´

ob ci

ag (a

) nazywamy rekurencyjnym stopnia k.

1.3.1. Ci

ag Fibonacciego. Ci

ag Fibonacciego

to z pewno´

sci

a najs lynniejszy ci

rekurencyjny (drugiego stopnia). Pomijaj

ac tu anegdot

e o kr´

olikach, mo˙zna go

zdefiniowa´

c nast

epuj

aco:

• f

= 1

• f

= 1

• f

n+1

= f

+ f

n−1

dla n ≥ 2

Oczywi´

scie i tym razem mo˙zna z latwo´

sci

a wypisa´

c pierwszych kilka wyraz´

agu:

= 2, f

= 3, f

= 5, f

= 8, f

= 13, f

= 21, f

= 34, f

= 55, f

= 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´

poznamy obejmuje tak˙ze ci

ag Fibonacciego. Nie precyzuj

ac metody og´

olnej ci

Fibonacciego jednak rozwi

azali´

smy. Okaza lo si

e, ˙ze

√





1 +

√

n+1

−

1 −

√

n+1





Tak skomplikowane rozwi

azanie oczywi´

scie wyja´

snia, dlaczego nie byli´

smy w

stanie odgadn

a´

c og´

olnego wzoru.

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

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

...

n−1
1

n−1
2

...

n−1

1≤i≤j≤n

− x

)

2.2. R´

ownania rekurencyjne liniowe. R´

ownaniem rekurencyjnym linio-

wym jednorodnym stopnia k nazywamy r´

ownanie postaci

(1)

= f (a

n−1

, ..., a

n−k

)

gdzie f : R

→ R jest pewn

a funkcj

a liniow

a, oraz zadane s

a warto´

sci pierwszych

k wyraz´

ow ci

agu (a

), a

, a

, ..., a

k−1

. Przy tych zamych za lo˙zeniach r´

ownanie

(2)

= 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)

= α

n−1

+ α

n−2

+ ... + α

n−k

za´

s r´

ownanie

(4)

= α

n−1

+ α

n−2

+ ... + α

n−k

+ g(n)

nazywamy r´

ownaniem rekurencyjnym liniowym o sta lych wsp´

o lczynnikach

niejednorodnym.

Dla r´

ownania (3) r´

ownanie

(5)

= α

k−1

+ α

k−2

+ ... + α

k−1

r + α

nazywamy r´

ownaniem charakterystycznym.

Podczas wyk ladu zauwa˙zyli´

smy nast

epuj

ace fakty.

• Je´sli dane s

a ci

agi b

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

ag´

ow rzeczywistych).

• Warunki pocz

atkowe (czyli warto´

sci ci

agu dla pierwszych k indeks´

ow) nale˙z

do k-wymiarowej podprzestrzeni przestrzeni wszystkich ci

ag´

ow rzeczywi-

stych.

• Dla ka˙zdego rozwi

azania r r´

ownania charakterystycznego (5) ci

ag (r

) jest

rozwi

azaniem r´

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

runki pocz

atkowe).

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

, r

, ..., r

w´

owczas rozwi

azanie (1) ma (jedyne) rozwi

azanie postaci

0
n

= c

+ c

+ ... + c

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

Powiedzieli´

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

sli r

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

, nr

, ..., n

l−1

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

• Przewidujemy rozwi

azanie postaci

00
n

= An

l−1

gdzie l jest krotno´

sci

a pierwiastka charakterystycznego q (czyli przewidu-

jemy rozwi

azanie postaci a

= Aq

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

, c

, ..., c

= a

0
n

+ a

00
n

spe lnia ly warunki pocz

atkowe problemu, czyli tak, by

0
i

+ a

00
i

= a

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

Przyk lad 2. R´

ownania

− 3a

n−1

= 5 · 7

− 3a

n−1

= 5 · 3

= 4.

2.3. Metody zliczania.

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

2.3.1. Zasada w l

aczania-wy l

aczania (metoda sita).

Twierdzenie 2. (Formu la Sita

lub Zasada W l

aczania i Wy l

aczania) Niech

, A

, ..., A

a zbiorami sko´

nczonymi. W´

owczas zachodzi wz´

∪ A

∪ ... ∪ A

| =

1≤i

<...<i

≤n

(−1)

k+1

∩ A

∩ ... ∩ A

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

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,

(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

≥ 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.

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!

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

= {f : A → B}. Wwczas

| = |B|

|A|

(dow. indukcyjny ze wzgl

edu na |A| ).

3.1.3. —Wariacje bez powt´

orze´

|{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

= {B ⊂

A : |B| = k}.

|A|

k!(n − k)!

Wniosek 4.

(1) (a + b)

n
k=0

n
k

n−k

(2)

n
k=0

n
k

= 2

3.1.5. Wz´

or Cauchy’ego.

Twierdzenie 5.

p + q

k=0

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

rozwi

aza´

n ca lkowitych nieujemnych

r´

ownania

+ x

+ ... + x

= r

3.1.7. Zasada Go l

ebnika (szufladkowa Dirichleta).

Twierdzenie 7. Niech A i B b

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

Wniosek 8 (Twierdzenia Erd˝

osa-Szek´

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

ag r´

o˙znych

+ 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

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]

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

[x]

k=0

s(n, k)x

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

nazywamy typu 1

. . . n

je˙zeli ma λ

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

. . . n

, w´

owczas zacho-

dzi:

1λ

+ 2λ

+ · · · + nλ

= n

Twierdzenie 13 (Cauchy’ego). Je´

sli 1λ

+ 2λ

+ · · · + nλ

= n, w´

owczas liczba

permutacji typu 1

. . . n

jest r´

owna

h(λ

, ..., λ

) =

. . . n

!λ

!...λ

Dow. ...

A. PAWE L WOJDA

4.1.3. Liczba podzia l´

ow zbioru.

Definicja 2. Rodzina

}

i=1,...,n

jest podzia lem zbioru X je˙zeli:

(1) X =

i=1,...,n

(2) A

∩ A

dla i 6= j.

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

...n

je´

sli zawiera λ

zbior´

ow liczno´

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

Uwaga: Je´

sli istnieje podzia l n-elementowego zbioru typu 1

...n

, w´

owczas

1λ

+ 2λ

+ ... + nλ

= n.

Twierdzenie 14. Je´

sli 1λ

+ 2λ

+ ... + nλ

= n w´

owczas liczba podzia l´

ow typu

...n

dana jest wzorem

P (λ

, ..., λ

) =

!λ

!...λ

!(1!)

(2!)

. . . (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) =

+...+λ

=k; λ

+...+nλ

!λ

!...λ

!(1!)

(2!)

. . . (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´

pami

eta ze szko ly

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

Inaczej: zbi´

or zbior´

ow.

Sprawd´

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

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

∈ G spe lniaj

acy

g ∗ g

= g

∗ g = e

(element odwrotny elementu g).

Je´

sli dzia lanie ∗ jest w G przemienne, w´

owczas G nazywamy przemienn

a lub

abelow

Przyk lady: grupa Kleina, Z

(dla r´

o˙znych n).

5.2.2. Grupy Z

∗

. D lu˙zsz

a chwil

e po´

swi

ecili´

smy zbiorowi Z

(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

jest 1. Latwo si

e okaza lo, ˙ze dla niekt´

orych n do niekt´

orych

element´

ow Z

nie ma element´

ow odwrotnych. Tak wi

ec, cho´

c dla dodawania Z

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

, by jednak grup

multyplikatywn

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

c. Rych lo okaza lo si

e, ˙ze

z Z

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

ma w Z

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

∗

edzie zbiorem element´

ow Z

wzgl

ednie pierwszych z

n. W´

owczas Z

∗

jest grup

a przemienn

a z mno˙zeniem.

Uwaga. Znowu, dzi

eki algorytmowi Euklidesa, umiemy do dowolnego elementu

a ∈ Z

∗

efektywnie znale´

z´

c element odwrotny.

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

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

3 k → k ∈ Z

nie jest homomorfizmem, za´

ψZ 3 k → k

[5]

∈ Z

homomorfizmem jest

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 ∗

(czyli z dzia lanie ∗ zacie´

snionym do zbioru H) jest grup

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

a grupy Z

(addytywnej).

Q, Z s

a podgrupami addytywnej grupy R.

Przyk lad. Sprawdzili´

smy, ˙ze grupa Kleina jest izomorficzna z pewn

a podgrup

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

−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

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

Przez k

[n]

oznaczamy reszt

e z dzielenia k przez n (inaczej m´

owi

ac, obcinamy k modulo n).

MATEMATYKA DYSKRETNA 2010

(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

= 1

1 oznacza tu oczywi´

scie element neutralny grupy H.

(2) Dla n ∈ N:

n+1

= a · a

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

= (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

DOM!

Podgrup

e pot

eg elementu a (w grupie multyplikatywnej) nazywamy podgrup

generowan

a przez ten element. Oczywi´

scie rz

ad elementu i rz

ad podgrupy gene-

rowanej przez ten element s

a identyczne.

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

= 1}

Zauwa˙zyli´

smy, ˙ze w Z

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. ...

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

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

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)

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

acy dzielnikiem rz

edu

grupy G.

Twierdzenie 31 (Eulera). Je´

sli liczby naturalne a, n s

a wzgl

ednie pierwsze, w´

owczas

ϕ(n)

≡ 1 (mod n)

Twierdzenie 32 (Ma le Twierdzenie Fermata). Je´

sli p jest liczb

a pierwsz

a, a ∈ Z,

≡ a( mod p)

7.2. Kwadratowe residua modulo.

Twierdzenie 33. Niech p b

edzie liczb

a pierwsz

a i niech a ∈ Z

. W´

owczas a ma

co najwy˙zej dwa pierwiastki kwadratowe w Z

Niech n ∈ N, a ∈ Z

. M´

owimy, ˙ze a jest kwadratowym residuum modulo

n, je˙zeli istnieje b ∈ Z

takie, ˙ze a = b

(mod n).

Twierdzenie 34. Niech p ∈ N b

edzie liczb

a pierwsz

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

edzie residuum kwadratowym w Z

. W´

owczas pierwiastkami kwadratowymi a z Z

a a

p+1

(mod p) oraz −a

p+1

(mod p).

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

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

. 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

wszyscy go znaj

a, a w ka˙zdym razie wiedz

a jak sie w niego zaopatrzy´

c. Tak wi

Alicja i Bob b

a musieli przesy lane dane zaszyfrowa´

c (funkcj

e szyfruj

a oznacza´

edziemy przez E

, 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

a post

epowali wed lug nast

epuj

acego sche-

matu:

Bob znajduje funkcj

e koduj

a (szyfruj

a) E oraz dekoduj

a D,

a wi

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

Bob przesy la tekstem otwartym (Ewa widzi przekaz) funkcj

e E Alicji

Alicja koduje informacj

e kt´

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)

Alicja wysy la Bobowi m

(Ewa oczywi´

scie tak˙ze widzi przesy lan

a informacj

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

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

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

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´

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

. Na dodatek, gdyby wynaleziono komputery o

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

ekszy´

c liczb

e cyfr znacz

acych n

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?

E od angielskiego encoding

A przede wszystkiem niebezpieczn

a dla Alicji i Boba!

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.

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

mo˙zna opisa´

c nast

epuj

aco.

Niech n b

edzie ustalon

a, wystarczaj

aco du˙z

a (powiedzmy 300-cyfrow

a) liczb

Funkcj

a koduj

a jest

E(l) = l

( mod n)

Oznacza to tyle, ˙ze Bob prze´

sle Alicji liczb

e n i funkcj

e koduj

a. Alicja obliczy

(mod n), prze´

sle t

e informacje Bobowi. Ewa, pods luchiwaczka, b

edzie zna la

zar´

owno l

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)

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´

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

(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

(mod p), b =

−m

p+1

(mod p), c = m

q+1

(mod q) oraz d = −m

q+1

(mod q), a nast

epnie

rozwi

azuj

ac cztery uk lady r´

owna´

n modularnych:

≡

(mod p)

≡

(mod q)

≡

(mod p)

≡

(mod q)

≡

(mod p)

≡

(mod q)

≡

(mod p)

≡

(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

edzie dla Boba bardzo proste. Po przej´

sciu z kodu ASCII na litery otrzyma jedn

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

= 225 ≡ 16 (mod 209)

i przesy

a Bobowi, kt´

ory oblicza:

11+1

= 16

≡ 5

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

19+1

= 16

·16

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

(mod 19)

Nazwa od tw´

orcy metody: Michaela Rabina

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

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)).

−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

(mod n)

(b) Wysy la l Bobowi.

Bob: Liczy

(6)

= (m

)

≡ 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

1+kϕ(n)

= m(m

ϕ(n)

)

≡ 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

Za l´

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

Mamy teraz: m

= 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

ec m

≡ m · 1

k(p−1)

= m (mod q).

Ostatecznie otrzymali´

smy

≡ m (mod q)

Mamy tak˙ze

≡ m (mod p)

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

nskiego twierdzenia o resztach m jest jedy-

nym rozwi

azaniem uk ladu r´

owna´

m ≡ l

(mod q)

m ≡ 0 (mod p)

(tak czy inaczej mamy m ≡ l

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

czy te˙z nie).

Nazwa metody od pierwszych liter nazwisk jej tw´

orc´

ow: Rivest, Shamir i Adleman.

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

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

, g

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

· g

)(x) = g

(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

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´

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

ϕ : 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

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

−1

(x) = (f h)

−1

(x) ⇒ g

−1

(x) = (h

−1

)(x) = h

−1

(x))

Ale f ∈ H, za´

s H jest stabilizatorem x, czyli f

−1

(x) = x i otrzymujemy ostatecznie

−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

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 na zbiorze sko´

nczonym X. W´

owczas liczba N orbit zbioru X ze wzgl

edu na G

wynosi

N =

|G|

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

(v)) w grafie G.

Twierdzenie 39. Je´

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

nczonym, w´

owczas

k G k=

v∈V

(v)

Wniosek 40. W dowolnym grafie sko´

nczonym liczba wierzcho lk´

ow stopni stopni

nieparzystych jest parzysta.

Twierdzenie 41 (O podawaniu r

). 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. ...

Handshaking Theorem

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

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

kraw

ed´

z e tworzonego cyklu eulerowskiego, kt´

a z kolei wyrzucamy ze

zbioru kraw

edzi grafu, tworz

ac w ten spos´

ob bie˙z

acy graf G

. 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

. Niech e b

edzie kraw

edzi

a G

tak

a, ˙ze

• jednym z jej ko´

nc´

ow jest v a drugim, powiedzmy, w.

• G

− {e} jest dalej sp´

ojny (chyba, ˙ze stopie´

n v w G

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

(graf bie˙z

acy) zast

epujemy przez G

− {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

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

nie ma ju˙z kraw

edzi, a wi

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

wybra´

c tak

a kraw

ed´

z e o ko´

ncu w v, ˙ze G

− {e} jest sp´

ojny

chyba, ˙ze v w G

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

usuwamy i w dalszym

agu mamy, rzecz jasna, graf sp´

ojny)

W tym celu zauwa˙zmy, ˙ze graf G

jest sp´

ojny (z konstrukcji) oraz, ˙ze w G

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

now

a kraw

ed´

z l

acz

a u i v (wierzcho lki stopni

nieparzystych).
W dugim przypadku nie robimy nic

W obu przypadkach w efekcie otrzymujemy graf, kt´

ory jest sp´

ojny (bo G

taki

Zamiast m´

owi´

c (pisa´

c) multigraf najcz

e´

sciej m´

owimy i piszemy graf

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.

Czyli to, co lubimy najbardziej!

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

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

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

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

, v

, . . . , v

oraz kraw

edzi e

, e

, . . . , 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

, ..., v

i−1

kraw

edzi

a e

Przyk lad...

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´

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

(a, b) r´

own

a d lugo´

sci

najkr´

otszej ´

scie˙zki z a do b.

dist

spe lnia warunki metryki.

Ekscentryczno´

sci

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

= max{dist

(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

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.

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

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

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

li´

sci i

k =

n−3

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

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.

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

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).

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

)

G = (V ; E) nazywamy dowoln

a funkcj

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

) = 2,

χ(C

2k+1

) = 3, χ(K

) = 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

(v) : v ∈ V }

Twierdzenie 61 (???

). Dla dowolnego grafu prostego G prawdziwa jest nier´

owno´

s´

χ(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

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

kolorami. St

ad oczywi´

scie istnieje

(7)

(λ) =

i=1

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

(λ) zdefiniowane

wzorem (7) nazywamy wielomianem charakterystycznym grafu G

Przyk lad.

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

e jednak m´

owi l w trakcie

wyk lad´

ow.

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?

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´

a odgrywa tu λ formalnie jest niezupe lnoie

poprawna, nie prowadzi jednak do nieporozumie´

MATEMATYKA DYSKRETNA 2010

Twierdzenie 63. P

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

Dow. ...

Twierdzenie 64. P

(λ) = λ(λ − 1)

n−1

Niech a i b b

a dwoma wierzcho lkami nie po l

aczonymi w grafie G. Przez G

oznaczmy graf powsta ly z G przez po l

aczenie wierzcho lk´

ow a i b kraw

edzi

a, za´

s przez

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

(λ) + P

(λ)

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

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 χ

(G).

Twierdzenie 66 (Twierdzenie Vizinga). Dla dowolnego grafu prostego

∆(G) ≤ χ

(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

a dok ladnie jednym lukiem.

Przyk lady.

Definicja 9. ´

Scie ˙zka o pocz

atku w x i ko´

ncu w y, to ci

(x = a

, e

, a

, e

, ..., a

k−1

, a

= y)

wierzcho lk´

ow a

, ..., a

i luk´

ow e

, ..., e

k−1

takich, ˙ze e

= (a

, a

i+1

) dla i = 1, ..., k

oraz a

6= a

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. ...

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

a zwolnieni, cz

e´

s´

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

szczeg´

o ly og losz

e, gdy b

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

≤ a

≤ ... ≤ a

) p´

o lstopni wierzcho lk´

ow G nazywamy wekto-

rem wynik´

ow turnieju G..

Twierdzenie 68 (Landau). Ci

ag niemalej

acy (a

≤ a

≤ ... ≤ a

) jest wektorem

wynik´

ow pewnego turnieju wtedy i tylko wtedy gdy

i=1

≤

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

owno´

s´

Dowodu nie b

e podaswa l, cho´

c ladny. Jako ciekawostk

e mog

e jednak poda´

˙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

edzie permutacj

a typu d = 1

...n

dzia laj

na zbiorze turniej´

ow rz

edu n. Je´

sli σ ma cykl

d lugo´

sci parzystej (czyli je´

sli d

> 0

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

t(d)

, gdzie

t(d) =





i,j=1

(i, j)d

−

i=1





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´

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

, a

, ..., a

). Bez straty og´

olno´

sci mo˙zemy

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

za lo˙zy´

c, ˙ze (a

, a

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

owczas σ(a

, a

) ∈ E(T ),

, a

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

olno´

sci σ

, a

) ∈ E(T ). Tymczasem

, a

) = (a

, a

), 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

= d

= ... = 0).

Niech wi

ec b

edzie cykl (nieparzysty) (a

, ..., a

) permutacji σ. Na wierzcho lkach tego

cyklu mo˙zna zbudowa´

c 2

i−1

r´

o˙znych turniej´

ow T

(rz

edu i) takich, ˙ze σ(T

) = T

Bierze si

e to st

ad, ˙ze ka˙zd

a ci

eciw

e tego cyklu

, 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

i−1

turniej´

ow T

ta-

kich, ˙ze σ(T

) = T

. A dla wszystkich cykli permutacji lacznie 2

n
i=1

i−1

turniej´

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

. Mo˙zliwo´

sci wybnoru luk´

pomi

edzy cyklami d lugo´

sci jest i, za´

s wszystkich par

. Mamy wi

ec 2(

)

mo˙zliwo´

sci.

Rozpatrzmy teraz przypadek cykli o r´

o˙znych d lugo´

sciach i oraz j, powiedzmy

, ..., a

) i (b

, ..., b

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

, b

) ma NWW(i, j) element´

ow. Poniewa˙z za´

s tych luk´

ow pomi

edzy {a

, ..., a

}

a {b

, ..., b

} 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) =

i=1

(i − 1)

i=1

i +

1≤i<j≤n

(i, j)

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

...n

(d = (d

, ..., d

) i d

= ... = 0):

t(d) =





i,j

(i, j) −

i=1





Twierdzenie 70 (Davis). Liczba nieizomorficznych turniej´

ow T (n) rz

edu n dana

jest wzorem

T (n) =

∗

t(d)

Q i

di!

(gdzie t(d) jest okre´

slone w twierdzeniu poprzednim, za´

∗
d

oznacza sum

e po

wszystkich d spe lniaj

acych d

+ 3d

... + nd

= n oraz d

= 0 dla ka˙zdego l).

Tu dalej mamy do czynienia z cyklem permutacji (a

, ..., a

), co nie przeszkadza nam jednak

traktowa´

c {a

, ..., a

} jako wierzcho lk´

ow turniej´

ow i budowa´

c na nich cyklu z ci

eciwami!

A. PAWE L WOJDA

Dow´

od. W dowodzie wykorzystamy

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

...n

jest

!...n

Rzeczywi´

scie, wykorzystuj

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

chy’ego (twierdzenie 13) otrzymujemy:

T (n) =

σ∈S

|Fix σ| =

∗

!...n

t(d)

∗

t(d)