Matematyka dyskretna
Dr Marek Zakrzewski
Wykład 06
Symetrie własne
Na ile sposobów można pokolorować wierzchołki kwadratu za pomocą 2 kolorów?
Pokolorowań  16
Typów  6
Symetria własna figury to izometria (=ruch sztywny) figury przeprowadzająca tę figurę na
siebie.
Dla figury ograniczonej są 2 typy symetrii własnych: obroty i symetria zwierciadlana.
Uwaga: symetria środkowa to obrót!!! o 180o
Symetrie własne kwadratu:
1234
I =O0=O0o= =śą1źąśą 2źąśą3źąśą4źą
śą źą
1234
1234
O1=O90 = =śą1234źą
o
śą źą
2341
Obroty:
1234
O2=O180o= =śą13źąśą24źą
śą źą
3412
1234
O3=O270 = =śą1432źą
o
śą źą
4123
S1=śą1źąśą24źąśą3źą
S =śą12źąśą34źą
2
Symetrie:
S3=śą13źąśą 2źąśą 4źą
S =śą14źąśą 23źą
4
I =O0 ,O180 )
o o
ProstokÄ…t: 2 symetrie i 2 obroty (
{1,2 , ... , n}
Własności zbioru wszystkich permutacji na :
" zawiera permutacje identycznościowe
Ä…Ä…
" wraz z permutacjÄ… zawiera Ä…Ä…-1 (odwrotne)
ąą1 , ąą2 zawiera ąą1ąą2 (złożenie)
" wraz z permutacjami
Każdy zbiór permutacji spełniający te trzy warunki grupą permutacji.
{1,2 , ... , n}
Przykłady grup permutacji na :
Sn - zbiór wszystkich permutacji
Grupy symetrii własnych n-kąta foremnego
D2n - grupa wszystkich symetrii własnych
Cn - grupa obrotów
D8 - grupa symetrii kwadratu
2
C4 - grupa obrotów kwadratu (grupa cykliczna)( o o o o )
O180 =O90 O270 =O3 I =O90
90o
G
Mówimy, że dwa pokolorowania są równoważne ze względu na grupę (krócej G-
równoważne), jeżeli istnieje g"G przekształcające jedno pokolorowanie w drugie.
~G
Relacje równoważności ma trzy oczywiste własności:
" a ~G a
" a ~G b Ò!b ~G a
" [śąa ~G bźą &śąb~G cźą]Ò! a~G c
Lemat BURNSIDE'A
FIX - zbiór pokolorowań takich,
Dla ustalonego elementu g "G oznaczamy przez a
g
g śą aźą=a
że (punkty stałe pokolorowania)
Lemat Burnside'a
G
Niech będzie grupa permutacji działających na zbiorze kolorowań. Wówczas liczba
typów (tzn. pokolorowań parami nierównoważnych) wynosi:
#"FIX #"
"
g
g "G
#"G#"
Przykład: Kwadrat  grupa obrotów, 2 kolory.
o
#"FIX #"=16
O0
o o
#"FIX #"=2=#"FIX #"
- ten sam kolor wszędzie
O90 O270
o
#"FIX #"=4
O180
16ƒÄ…4ƒÄ…2ƒÄ…2
=6
4
Dopuśćmy także symetrię:
#"FIX #"=#"FIX #"=4
#"
Ä…
#"FIX #"=#"FIX #"=8
/ "
8ƒÄ…8ƒÄ…4ƒÄ…4ƒÄ…16ƒÄ…4ƒÄ…2ƒÄ…2
=6
8
Ile jest pokolorowań 3 kolorami 6-kata foremnego, jeżeli utożsamiamy pokolorowania
równoważne ze względu na obroty?
#"FIX #"=36
I
o o
#"FIX #"=3=#"FIX #"
O60 O300
o o
#"FIX #"=32=#"FIX #"
O120 O240
o
#"FIX #"=33
O180
36ƒÄ…3ƒÄ…3ƒÄ…32ƒÄ…32ƒÄ…33 =130
6
Na ile sposobów można pokolorować podobnie p-kąt 2 kolorami? (p  liczba pierwsza)
I =O0 ,O1 ,O2 , O3 ,O4 , ... ,O
p-1
p
#"FIX #"=2 , #"FIX #"=2 - dla pozostałych i
O
0o i
Z lematu Burnside'a mamy:
p p p
2 ƒÄ…śą p-1źą"2 śą2 -2źąƒÄ…2p -2
2
= = ƒÄ…2
p p p
p
a
To jest liczba całkowita, a więc dzieli -2 . Analogicznie dla kolorów pokażemy, że
2
p
p dzieli a -a .
WNIOSEK (Małe twierdzenie Fermata)
p
p p
Jeśli jest liczbą pierwszą to dzieli -a .
a
Relacje równoważności
śąa~a źą
Relacją równoważności nazywamy dowolną relację dwuargumentową zwrotną ,
śąa~b Ò! b~aźą śąa~b , b~a Ò! a~c źą
symetrycznÄ… i przechodniÄ… .
Każda relacja równoważności wyznacza rozbicie na niepuste rozłączne klasy złożone z
elementów parami równoważnych, każda z tych klas nazywa się klasą abstrakcji.
Relacje porzÄ…dku:
d" Ä…Ä…
Relacja (to nie jest zwykły znak tylko podobny) jest relacją porządku częściowego
(krócej porządku częściowego), jeśli:
ad"a (zwrotność)
[śąad"bźą &śąbd"cźą]Ò! ad"c
(przechodniość)
[śąad"bźą &śąbd"aźą]Ò! a=b
(słaba antysymetria)
Twierdzenie (ErdQ
s-Szekeresz)
Każdy ciÄ…g, różnych liczb rzeczywistych, dÅ‚ugoÅ›ci mr ƒÄ…1 zawiera ciÄ…g malejÄ…cy dÅ‚ugoÅ›ci
mƒÄ…1 lub rosnÄ…cy dÅ‚ugoÅ›ci rƒÄ…1 .
Dowód:
xm , xr
x
Dla każdego niech oznacza długość najdłuższego ciągu malejącego
x śąrƒÄ…1źą -
(odpowiednio rosnącego) zaczynającego się o . Załóżmy, że nie ma ciągów
xmd"m , xrd"r
śąmƒÄ…1źą - malejÄ…cych. To znaczy wszystkie
rosnących ani . Rozważmy
x Śą xr , xm
funkcję łatwo zauważyć, że funkcja jest różnowartościowa. Zatem róznych par
mr
musi być mrƒÄ…1 a jest .
Sprzeczność.
PorzÄ…dki:
A
ańcuch  każde dwa punkty są parami zależne.
Antyłańcuch  nie ma punktów parami zależnych.
Lemat DILWORTH'A
PorzÄ…dek częściowy zÅ‚ożony z alƒÄ…1 elementów zawiera Å‚aÅ„cuch dÅ‚ugoÅ›ci lƒÄ…1 oraz
antyÅ‚aÅ„cuch dÅ‚ugoÅ›ci aƒÄ…1 .