Matematicko-fyzikálna fakulta Univerzity Komenského
Martin Knor
"'
KOMBINATORIKA A TEORIA GRAFOV
l
2000
Univerzita Komenského Bratislava
Predhovor
Učebný text je určený študentom prvého ročníka odboru matematika a študen­
tom druhého ročníka odboru management na Matematicko-fyzikálnej fakulte Univerzity
Komenského. Predstavuje autorove prednášky z predmetu úvod do diskrétnej matema­
tiky, časť kombinatorika. Teória grafov je búrlivo sa rozvíjajúcou disciplínou, a pr�to
sa postupne menia aj osnovy pre úvodné prednášky k tejto časti matematiky. Z toho
vyplynula aj nutnosť napísať úplne nový učebný text.
Po formálnej stránke je text upravený tak, že každá kapitola predstavuje jednu pred­
nášku. Cvičenia, pripojené na záver každej kapitoly, tvoria osnovu pre cvič.enie z pred­
metu úvod do diskrétnej matematiky.
Po obsahovej stránke možno rozdeliť učebnicu na dve časti. Prvých šesť kapitol je
venovaných kombinatorike. Postupne sa zaoberáme Dirichletovým princípom, základ­
nými enumeračnými princípmi, binomickými koeficientami, princípom inklúzie a exklú­
zie, riešením rekurentných vzťahov a vytvárajúcimi funkciami. Ďalších päť kapitol je
venovaných kombinatorickým štruktúram. V siedmej kapitole sa zaoberáme systémami
rozličných reprezentantov a v ôsmej blokovými plánmi. Posledné tri kapitoly sú venované
základným problémom teórie grafov. V deviatej kapitole sa zaoberáme prechádzkami na
grafoch, v desiatej dokážeme vetu o päťfarbiteľnosti rovinných grafov a v záverečnej de­
siatej demonštrujeme použitie získaných poznatkov na Petersenovej a Konigovej vete.
Predmet úvod do diskrétnej matematiky, časť kombinatorika, sa vyučuje v druhom,
respektíve v treťom semestri, keď už študenti získajú základné vedomosti z analýzy a
z algebry. Poznatky z analýzy využívame v kapitolách 3 a 4 (Mc Laurinov rad) a 3 a
6 (konvergencia radov, derivovanie a integrovanie funkcií) . Poznatky z algebry v kapi­
tolách 5 (Vandermondova matica a determinanty) a 8 (konečné polia) .
Autor
3
l. DIRICHLETOV PRINC1P
1.1. Slabá forma Dirichletovho princípu
V tejto kapitole sa budeme zaoberať veľmi jednoduchým princípom. Obrazne pove­
dané, ak máme priveľa holubov a málo hniezd, tak v aspoň jednom hniezde sú aspoň
dva holuby.
Veta 1 . 1 (Dirichletov princíp, slabá forma) . Ak máme n+l objektov rozde­
lených do n skupín, tak v aspoň jednej skupine sú aspoň dva objekty.
Dôkaz. Sporom predpokladajme, že v každej skupine je nanajvýš jeden objekt . Keďže
skupín je iba n, tak spolu je vo všetkých skupinách nanajvýš n objektov, čo je v spore
s naším predpokladom. O
Všimnite si, že Dirichletov princíp nám nedáva žiadnu informáciu, ako nájsť skupinu,
ktorá obsahuje aspoň dva naše objekty. Zaručuje iba existenciu takej skupiny. To zna­
mená, že ak aplikujeme Dirichletov princíp v dôkaze existencie nejakej štruktúry, tak
tento dôkaz nám nedá návod, ako takú štruktúru zostrojiť.
l. Majme n prirodzených čísel a1 , a2 ,
, an. Potom existujú k a l, l �k�
také, že súčet ak+ak+l+···+az je deliteľný číslom n.
Príklad
�l � n ,
.
.
•
Riešenie. Uvažujme nasledujúcich n súčtov: a11 a1 + a2 , a1 +a2 +ag , ... , a1+
+a2 +···+an. Ak by bol niektorý z týchto súčtov deliteľný n , tak niet čo dokazovať.
Predpokladajme teda, že všetky tieto súčty majú nenulový zvyšok po delení n. Keďže
súčtov jen a nenulových zvyškov iba n 1, tak podľa Dírichletovho princípu aspoň dva
tieto súčty, povedzme a1 + a2 +'··+ai a a1 +a2 +···+aj , majú rovnaký zvyšok po
delení n. Nech i < j. Potom je súčet ai+l +ai+2 + ··· +aj deliteľný n.
Príklad 2. Dokážte, že ak je x reálne číslo, tak aspoň jedno z čísel x, 2x, 3x, ...
.. . , (n-l )x sa líši od celého čísla nanajvýš o �.
Riešenie. Rozdeľme interval ( 0, l) na n intervalov ( 0, �), ( �, �), ... , ( 1, l) a uva­
žujme necelé časti čísel kx, čiže čísla kx - lkx J, kde k l , 2, ... , n-l. Ak niektorá
z týchto častí, povedzme lx-llxj, leží v intervale ( 0, � ) , alebo
1 ) , tak lx sa líši od
=
celého čísla nanajvýš o
�
a niet čo dokazovať. Predpokladajme teda, že všetky necelé
5
). Keďže
časti čísel x, 2x, 3x, . . . , (n-l )x ležia v intervaloch( � , � ) ,( � , � ) , ,
necelých častí je n-1 a intervalov n-2, tak podľa Dirichletovho princípu aspoň dve
necelé časti, povedzme z čísel ix a jx, ležia v rovnakom intervale. Nech i < j. Potom
platí
.
.
.
- .!_ � (jx - lJxJ) - (ix - lixJ ) � .!_
.
n
n
_.!_ � (j-i)x-(lJxJ-lixJ)
�
.!..
n
n
Keďže l� j-i < n -1, tak (j-i)x sa líši od celého čísla lJxJ-lixJ nanajvýš o
�-
Šachový veľmajster má na prípravu na turnaj ll týždňov. Rozhodol sa,
že každý deň bude hrať aspoň jednu partiu, ale aby sa nepreťažil, tak v žiadnom prípade
nechce odohrať viac ako 12 partií za týždeň. Dokážte, že existuje postupnosť následných
dní, počas ktorých odohral presne 21 hier.
Riešenie. Nech je a1 počet partií, ktoré odohral v prvý deň, a2 počet partií, ktoré
odohral za prvé dva dni, . . . , až a77 nech je počet partií ktoré odohral za prvých
77 dní. Keďže každý deň odohral aspoň jednu partiu, tak a1 < a2 <
< a77.
V každom týždni odohral nanajvýš 12 partií, a preto a77 � 12·11
132. Uvažu­
jme čísla a1, a2, . . . , a77, a1 +21, a2 +21, . . . , a77+21. Všetky sú celými číslami medzi l a
132+21 153. Ich počet je však 77+77 154, a preto sú podľa Dirichletovho princípu
aspoň dve z nich rovnaké. Nemôžu byť rovnaké žiadne dve čísla typu a i a aj, ani ai+21
a aj+21, a preto sa musia rovnať ai +21 a aj pre nejaké i < j. Preto veľmajster počas
dní i+l,i+2,... ,j odohral presne 21 hier.
Príklad
3.
·
·
·
=
=
=
1.2. Silná forma Dirichletovho princípu
Veta 1.2 (Dirichletov princíp, silná forma). Nech sú q1, q2, , Qn prirodzené
čísla. Ak máme q1 + q2 +
+ Qn + l objektov rozdelených do n skupín, tak buď prvá
skupina obsahuje aspoň q 1 + l objektov, alebo druhá skupina obsahuje aspoň q2 + l
objektov, ... , alebo n-tá skupina obsahuje aspoň Qn + l objektov.
.
·
·
•
.
·
Dôkaz. Sporom predpokladajme, že v i-tej skupine je nanajvýš Qi objektov, i
l, 2, . . . , n. Potom je vo všetkých skupinách spolu nanajvýš q1 + q2 + +qn objektov,
=
=
·
čo je v spore s predpokladom.
D
·
·
Ak zvolíme q1
l, tak dostávame slabú formu Dirichletovho
Q2
Qn
princípu. Dirichletov princíp sa používa aj v iných tvaroch, ktoré uvádzame ako dôsledky
vety 1.2.
=
6
=
·
·
·
=
=
Dôsledok l. Ak máme n· r + l objektov rozdelených do n skupín, tak aspoň jedna
skupina obsahuje aspoň r + l objektov.
Dôsledok 2. Nech sú r a k 1 , k2 , . . . , kn prirodzené čísla. Ak pre priemer týchto čísel
> r, tak aspoň jedno z čísel k 1 , k2 , . . . , k n je aspoň r + l.
platí
Dôkaz. Majme už umiestnené objekty do n skupín tak, že v i-tej skupine je ki objek­
> r, tak k1 + k2 +· · · + kn > n· r a keďže všetky
t �v, i= l, 2, ... , n. Keďže
čísla sú prirodzené, tak k1 +k2 +· · · +kn � n·r +l. To znamená, že v n skupinách máme
aspoň n·r +l objektov. Teda podľa dôsledku l vety 1 . 2 aspoň jedna skupina obsahuje
aspoň r +l objektov, čiže aspoň jedno z čísel k b k2 , . . . , kn je aspoň r +l. O
Príklad 4. Dva kruhové disky, jeden menší než druhý, sú rozdelené každý na 200
rovnakých výsečí. Na väčšom disku sme vybrali náhodne 1 00 výsečí, ktoré sme zafarbili
na červeno a ostatné výseče sme zafarbili na modro. Na menšom disku sme výseče farbili
na červeno a na modro úplne náhodne. Dokážte, že je možné priložiť tieto disky na seba
tak, aby bolo aspoň 100 výsečí súhlasne zafarbených.
Riešenie. Umiestnime väčší disk pevne v priestore. Máme presne 200 možností pri­
loženia malého disku na velký tak, aby výseče malého disku korešpondovali s výsečami
velkého disku. Týchto 200 možností spolu dáva 20 000 výsečí zafarbených súhlasne, keďže
každá výseč malého disku má takú farbu ako 100 výsečí velkého. Keďže priemerný počet
= 100 > 99 , tak podľa Dirichletovho princípu
súhlasne zafarbených výsečí je
(dôsledku 2) musí existovať pozícia, v ktorej je súhlasne zafarbených aspoň 100 výsečí.
Príklad 5. Daný je systém 1562 množín Ab A2 , . . . , A1sa2 , pričom každá z týchto
množín má práve 40 prvkov a l A i nA; l l pre každú dvojicu i a j, i =J j. Dokážte, že
potom existuje prvok spoločný všetkým týmto množinám.
=
Riešenie.
Nech A 1 = {ab a2 , . . . , a4o } . Rozdeľme množiny A2 , A 3 , . . . , A 1 sa2 do 40
skupín tak, že v i-tej skupine budú práve tie množiny, ktoré majú s A 1 spoločný prvok
ai, i = l , 2 , . . , 40. Keďže v týchto skupinách je 1561 množín a
> 39, tak podľa
Dirichletovho princípu (dôsledku 2) existuje skupina, v ktorej je aspoň 40 prvkov. Bez
újmy na všeobecnosti predpokladajme, že je to prvá skupina a patria do nej množiny
A2 , A 3 , . . . , A41 · Teda množiny A1 , A2 ,
A41 majú spoločný jediný prvok a 1 a všetky
ostatné prvky majú rôzne. Sporom predpokladajme, že a1 fj. Ak pre nejaké k > 41 .
Keďže Ak má spoločné prvky s Ab A2 , . . . , A4 1 , tak má aspoň 4 1 prvkov, čo je spor
s predpokladom. Preto a1 E Ak pre každé k= l , 2, . . . , 1 562.
.
.
Príklad
6
.
.
,
(Erdos, Szekeres). Dokážte, že každá postupnosť ab a2 . . . , an2+1 reál­
nych čísel obsahuje buď neklesajúcu podpostupnosť (t.j . vybranú postupnosť) dfžky
n +l, alebo nerastúcu podpostupnosť dfžky n +l.
Riešenie.
Pre každé i= l , 2, . . . , n 2+l nech je mi dfžka najdlhšej neklesajúcej pod­
postupnosti začínajúcej číslom ai. Ak mi � n + l pre nejaké i, l ::; i ::; n 2+ 1 , tak niet
čo dokazovať. Predpokladajme preto, že pre všetky i platí mi ::; n. Keďže máme n 2+ 1
čísel mi , tak podľa Dirichletovho princípu (dôsledku l) existuje aspoň n + l rovnakých
7
čísel mi . Nech sú to mrl = mr2 =
= mrn+l' pncom rl < T2 < ... < Tn+l · Ak
by platilo ar; :: ari pre nejaké i < j, tak existuje neklesajúca podpostupnosť dfžky
mr; začínajúca v ari a ak ako prvý prvok doplníme ar;, tak dostávame neklesajúcu
pod postupnosť dfžky mr; + l začínajúcu v ar;, čo je v spore s definíciou mr;. Preto
ar
> ar2 > . . . > arn+l a teda arl'ar2' ...'arn+l je nerastúca pod postupnosť dfžky
n +l
.
.
.
.
l
1.3. Ramseyova veta
Nasledujúca veta je zovšeobecnením Dirichletovho princípu a uvedieme ju bez dôkazu.
Veta 1. 3 {Ramseyova). Nech sú q1, q2 ,
, Qn a t kladné prirodzené čísla také,
že Qi � t pre i
l, 2, . . . , n . Potom exist uje najmenšie prirodzené číslo, označme ho
N(q1, Q2 , . . . , Qn; t) , také, že ak je S lubovolhá množina s aspoň N(q 1 , q2 ,
, Qn; t) ob­
jektami a všetky t-prvkové podmnožiny S sú rozdelené do n skupín, tak buď existuje q 1
objektov, ktorých všetky t-prvkové podmnožiny patria do prvej skupiny, alebo existuje
Q2 objektov, ktorých všetky t-prvkové podmnožiny patria do druhej skupiny, . . . , alebo
existuje Qn objektov, ktorých všetky t-prvkové podmnožiny patria do n-tej skupiny.
.
•
.
=
•
.
•
(ql + Q2 +
+ Qn ) - n + l
Všimnite si, že ak t = l, tak N(q1, Q2 , . . . , Qn; l)
podľa vety 1.2. Ramseyova veta má "zaujímavé dôsledky a presne určiť hodnoty zaručené
vetou je ťažké dokonca pre N(q, q; 2). Je známe, že N(3, 3; 2) 6 a N(4, 4; 2) = 18.
Žiadne ďalšie presné hodnoty tohoto typu nie sú určené. Keď Pál Erdos, jeden z naj­
významnejších matematikov 20. storočia, populárnym spôsobom vysvetľoval náročnosť
presného výpočtu čísel N(q, q; 2), uviedol nasledujúci príklad. Predstavme si, že na
Zem zaútočia mimozemšťania a povedia, že nás nezničia, len ak vypočítame presne
hodnotu N(5, 5; 2). Ak zhromaždíme všetkých vynikajúcich matematikov na planéte
a zapojíme do výpočtu všetky výkonné počítače, ktoré máme, tak by sa nám mohlo
podariť presne určiť hodnotu N(5, 5; 2). Ak nám však mimozemšťania dajú za úlohu
určiť presnú hodnotu N(6, 6; 2), tak jediným riešením pre nás je ·vymyslieť nové zbrane
a začať zbrojiť.
Rozoberme si, čo to znamená, že existuje číslo N(q, q; 2). Uvažujme množinu S bodov
v rovine, z ktorých žiadne tri nie sú kolineárne. Potom každá dvojica bodov určuje je­
dinú úsečku a všetky takto získané úsečky sú rôzne. Zafarbíme tieto úsečky červenou,
respektíve modrou farbou. Úsečky zafarbené červenou farbou (t.j . dvojprvkové pod­
množiny S) budú predstavovať jednu skupinu a úsečky zafarbené modrou farbou budú
predstavovať druhú skupinu. Ramseyova veta tvrdí, že ak je počet bodov v S dosť velký
(t .j. ak ich je aspoň N(q , q; 2) ) , tak bez ohľadu na to, ako sme úsečky farbili, existuje q
bodov takých, že buď sú všetky úsečky medzi týmito bodmi zafarbené červenou farbou,
=
·
=
8
·
·
alebo sú všetky zafarbené modrou farbou. Uvedomte si, čo to znamená, ak napríklad
q
l 000, prípadne q l 000 000 ap.
Túto kapitolu ukončíme dôkazom tvrdenia N(3, 3; 2) 6.
=
=
=
Veta 1 .4. N(3, 3; 2 )
=
6.
· Dôkaz. Na obrázku l je znázornené rozdelenie dvojprvkových podmnožín (t.j . úse­
čiek) päťprvkovej množiny do dvoch skupín (dvojice bodov spojené plnou čiarou patria
do jednej skupiny a dvojice spojené prerušovanou čiarou patria do druhej skupiny).
Žiadna skupina neobsahuje všetky dvojprvkové podmnožiny žiadnej trojprvkovej mno­
žiny (čiže trojuholník) , a preto N(3, 3; 2) > 5.
Obrázok
l
Zostáva nám dokázať, že N(3 , 3; 2) � 6. Majme ľubovoľnú šesťprvkovú množinu S a
v nej si vyberme jeden konkrétny prvok a. Nech sú všetky dvojprvkové podmnožiny S
rozdelené do dvoch skupín. Keďže S obsahuje okrem prvku a ešte päť ďalších prvkov, tak
aspoň tri dvojprvkové podmnožiny S tvaru {a, x} (teda obsahujúce a) patria do jednej
skupiny podľa Dirichletovho princípu (dôsledku l vety 1.2) . Nech sú to podmnožiny
{a, u} , {a, v} a {a, w} a nech sa skupina do ktorej patria volá červená skupina. Ak aspoň
jedna z množín {u, v} , {v, w} a { w, u} , povedzme {u, v} , patrí do červenej skupiny, tak sú
v nej všetky dvojprvkové podmnožiny množiny {a, u, v}. Ak však všetky množiny {u, v} ,
{v, w} a {w, u} patria do druhej skupiny, tak táto zasa obsahuje všetky dvojprvkové
podmnožiny množiny {u, v, w}. D
Cvičenia
Cvičenie 1 . 1 . Majme vybraných 101 čísel z množiny { 1 , 2, .. . , 200}. Dokážte, že
medzi týmito číslami sú dve také, z ktorých jedno je deliteľom druhého.
9
Ukážte, že existuje taký výber 100 čísel z množiny { 1 , 2, . . . , 200} , že
medzi týmito číslami nie je žiadna dvojica čísel, z ktorých jedno je deliteľom druhého.
Cvičenie 1. 2 .
študent má 37 dní na prípravu na skúšku. Podľa svojich skúseností
vie, že mu stačí, ak sa bude spolu učiť 60 hodín, ale určite sa chce učiť aspoň h >dinu
denne. Dokážte, že bez ohľadu na to, aký si urobí plán, existuje postupnosť následných
dní, počas ktorých sa bude učiť presne 13 hodín. (Predpokladáme, že každý deň sa učí
celočíselný počet hodín . )
Cvičenie 1. 3.
·
Dokážte, že medzi ľubovoľnými 52 prirodzenými číslami existuje dvo­
jica, ktorej súčet alebo rozdiel, je deliteľný 100.
Cvičenie 1. 4.
Dokážte, že ak vyberieme n+ l čísel z množiny {2, 3 , . . . , 2n+ l} tak
tieto čísla obsahuj ú dvojicu nesúdeliteľných čísel.
Cvičenie 1. 5.
Predpokladajme, že v skupine 6 ľudí je každá dvojica buď priateľmi,
alebo nepriateľmi. Dokážte, že buď existuje trojica ľudí, ktorí sú navzájom priatelia,
alebo trojica ľudí, ktorí sú navzájom nepriatelia (predpokladá sa, že relácia "byť pria­
teľom" je symetrická, čiže ak je a priateľom b, tak aj b je priateľom a) .
Cvičenie 1. 6.
Cvičenie l. 7. Majme skupinu n ľudí, z ktorých sa každá dvojica buď pozná alebo
nepozná. Dokážte, že v tejto skupine sú dvaja ľudia, ktorí majú rovnaký počet známych.
Dokážte nasledujúce tvrdenia.
a) Ak je 9 bodov zvolených vo štvorci o strane 2, tak existuje trojica bodov, ktorých
vzájomné vzdialenosti sú nanajvýš J2.
b) Ak je 82 bodov zvolených v kocke o strane 3 , tak existuje štvorica bodov, ktorých
vzájomné vzdialenosti sú nanajvýš v'3.
c) Ak je 9 bodov zvolených v rovnostrannom trojuholníku o strane 2, tak existuje
trojica bodov, ktorých vzájomné vzdialenosti sú nanajvýš l .
Cvičenie 1.8.
LO
2. ZÁKLADNÉ ENUMERAČNÉ PRINCÍPY
2.1. Dva základné princípy
V tejto časti uvedieme dva základné princípy, sčítavací a násobiaci. Tieto princípy
sú také elementárne, že ich dôkazy prenechávame čitateľovi. Poznamenajme, že pod
partíciou množiny rozumieme je� rozklad na disjunktné podmnožiny.
Veta 2. 1 (sčítavací princíp). Ak systém S1, S2 ,
, Sm tvorí partíciu množiny S,
tak počet prvkov v s je určený súčtom počtov prvkov v si, i= l, 2, ... ' m.
•
•
•
Počet študentov na matematicko-fyzikálnej fakulte môžeme určiť tak,
že zistíme, kolko je študentov na všetkých rôznych kombináciách a potom tieto čísla
sčítame.
Príklad
Veta
l.
(násobiaci princíp). Ak sú Ab A2 , ... , A n množiny majúce po rade
prvkov, tak počet usporiadaných n- tíc prvkov, kde prvý prvok je z A 1 1
A2, . . . , n-tý je z An, je a 1 a2
an
2. 2
a 1 , a2, ... , an
druhý je
z
Príklad
rôzne?
·
2.
·
.
.
.
·
.
Kolko nepárnych čísel medzi l 000 a 9 999 má všetky cifry navzájom
Riešenie. Číslo medzi l 000 a 9 999 možno chápať ako usporiadanú štvoricu. Preto
budeme voliť postupne jednotky, tisícky, stovky a desiatky. Keďže čísla majú byť nepár­
ne, tak máme päť možností na volbu jednotiek: l, 3 , 5, 7 a 9 . Na volbu tisícok však
máme nie deväť možností, ale už len osem, lebo všetky cifry musia byť navzájom rôzne.
Podobne na volbu stoviek máme osem možností a na volbu desiatok sedem. Podľa
násobiaceho princípu máme spolu 5 8 8 7 2 240 možností.
·
·
·
=
ll
2.2. Permutácie, variácie a kombinácie
Definícia. Permutácia n-prvkovej množiny je ľubovoľné usporiadanie prvkov tejto
množiny do postupnosti.
Veta 2. 3 . Počet permutácií n-prvkovej množiny je n!
=
n·(n- l )·(n-2)· . . . ·2·1.
Dôkaz. Zjavne na výber prvého prvku máme n možností, na výber druhého máme
možností, . . . , až na výber posledného n-tého prvku máme už len jedinú možnosť.
Teda podľa násobiaceho princípu máme n! permutácií. O
n- l
Poznamenajme, že O ! = l , čo odpovedá predstave, že existuje jediné usporiadanie
prvkov prázdnej množiny.
l
Príklad 3 . Známa je hra, pozostávajúca zo škatulky 4 x 4, v ktorej je 1 5 štvorčekov
l očíslovaných číslami l, 2, . . . , 1 5 a jedno políčko je prázdne. Teraz nás nebude
x
zaujímať, čo je cieľom tejto hry. Stačí nám vedieť, že škatulka je vždy natočená tak, že
názov hry je uvedený hore a štvorčeky nemožno preklápať, ani otáčať. Určte, kolko je
možných rozložení 1 5 štvorčekov l x l v škatulke.
Riešenie. Keďže v zaplnenej škatulke sú všetky štvorčeky navzájom rôzne (buď je na
nich jedno z čísel l, 2, . . . , 1 5 , alebo ide o jediné prázdne políčko) , tak máme práve tolko
rozložení, kolko je usporiadaní 1 6 prvkov, čiže 16! = 20 922 789 888 000.
Príklad 4. Kolko je usporiadaní desiatich dievčat do kruhu?
Riešenie. Do radu usporiadame dievčatá 10 ! spôsobmi, avšak pri usporiadavaní do
kruhu bude tento počet menší. Nerozlišujeme totiž pootočenia kruhu. Keďže jedno us­
poriadanie do kruhu odpovedá 10 usporiadaniam do radu (máme 10 pootočení kruhu) ,
= 9! = 3 62 880.
tak počet usporiadaní lO dievčat do kruhu je
Císla n!, nazývané tiež faktoriály, majú mnohostranné využitie v matematike. Často
potrebujeme odhadovať čísla, v ktorých sa faktoriály vyskytujú, teda potrebujeme po­
znať diferencovateľnú krivku, ktorá dobre aproximuje n!. Bez dôkazu uvádzame nasle­
dujúcu dôležitú vetu.
Veta 2.4 ( Stirlingova formula) . Platí n! "' y'21ľn (; r, čiže
lim
n
-+oo
12
n.l
v'21ľn . e
nn n
=
l.
z
=
Definícia. Variácia r-tej triedy z n prvkov je ľubovoľný usporiadaný výber r prvkov
danej n-prvkovej množiny.
Veta 2 . 5 . Ak r � n, tak počet variácií r-tej triedy z n prvkov je
n· (n- 1 )· . . . · (n- r + l ) .
. Dôkaz. Dôkaz je analogický dôkazu vety
2 . 3.
O
Príklad 5 . Kolkými spôsobmi možno umiestniť šesť rôznych šachových figúrok na
šachovnicu?
Riešenie. Nech sú danými figúrkami kráľ, dáma, veža, strelec, jazdec a pešiak. Úlohe
odpovedajú usporiadané výbery 6 polí šachovnice zo 64, pričom prvé vybrané pole
53 981 544 960
predstavuje pozíciu pre kráľa, druhé pre dámu atď. Preto má úloha
riešení.
=
Definícia. Kombinácia r-tej triedy z n prvkov je ľubovoľný výber r-prvkovej pod­
množiny z danej n-prvkovej množiny.
Veta
2.6.
Ak r � n, tak počet kombinácií r-tej triedy z n prvkov je (; ) =
Dôkaz. Nech je S n-prvková množina. Ľubovoľná kombinácia r-tej triedy z S môže
byť usporiadaná r! spôsobmi podľa vety 2 .3. Keďže každú variáciu r-tej triedy z S
môžeme získať jediným usporiadaním prvkov jedinej kombinácie, tak počet kombinácií
je r! krát menší, ako počet variácií r-tej triedy z n prvkov. Teda podľa vety 2.5 sa počet
kombinácií r-tej triedy z n prvkov rovná r.' ( r.) O
n
''
rovine máme 25 bodov, z ktorých žiadne tri nie sú ko lineárne. Kolko
priamok a kolko trojuholníkov určuje týchto 25 bodov?
Príklad
6. V
Riešenie. Keďže každá dvojica bodov určuje jedinú priamku, tak priamok je tolko,
kolko je dvojíc bodov. Teda ich je tolko, kolko je kombinácií druhej triedy z 2 5 prvkov,
čiže e25)
300. Podobne trojuholníkov je tolko, kolko je kombinácií tretej triedy z 25
prvkov, čiže (2i) 2 300.
=
=
Kombinačné čísla (; ) , nazývané tiež binomické koeficienty, splňajú množstvo
identít, ktorými sa budeme zaoberať v tretej kapitole.
13
2.3. Permutácie, variácie a kombinácie s opakovaním
Definícia. Permutácia
s
opakovaním n prvkov z
k druhov, pričom máme k dis­
pozícii n1 prvkov prvého druhu, n2 prvkov druhého druhu, . . . , až nk prvkov k-teho
druhu a n1 + n2 + · · · + nk n, je ľubovoľné usporiadanie týchto n prvkov do radu.
=
Veta 2. 7. Počet permutácií s opakovaním n1 prvkov prvého druhu, n2 prvkov
druhého druhu, . . . , až nk prvkov k-teho druhu, kde n1 + n2 + · · · + nk = n, je
n!
Dôkaz. Predstavme si rad s n pozíciami, na ktoré budeme umiestňovať naše prvky. Na
umiestnenie prvkov prvého druhu máme (�) možností, lebo (,:) spôsobmi môžeme vy­
brať n1 pozícií z n-prvkového radu podľa vety 2 .6. Na umiestnenie prvkov druhého druhu
na zostávajúce voľné miesta máme (n��1) možností, . . . , až na umiestnenie prvkov k­
teho druhu na zvyšné voľné miesta máme (n-n1-n�� .. ·-nk-l) možností. Preto sa počet
permutácií s opakovaním podľa násobiaceho princípu rovná
(n1n ) . (n -n2n1 ) . . . . . (n - n1 - n2nk- · · · - nk -1 ) =
(n - nl) !
(n - n1 - n 2 - · · · - nk- 1 ) !
. ···
nk!O!
n2! (n - n1 - n2) !
Príklad
7.
n!
.
n1 !(n - nl)!
n!
n 1 ! ·n 2! · . . . ·nk! ·
o
Kolko rôznych jedenásťpísmenkových slov možno vytvoriť z písmen slova
ABRAKADABRA?
Riešenie. Zjavne ide o permutácie s opakovaním, pričom máme k dispoozícii
2 R, lK a lD. Teda počet jedenásťpísmenkových slov je
Definícia. Variácia
s
opakovaním n prvkov z
=
83 160.
5A, 2B,
k druhov je ľubovoľné uloženie n
prvkov do radu, pričom každý z prvkov je jedného z k druhov (predpokladá sa, že prvkov
každého druhu je dostatočne veľa, teda aspoň n) .
Veta 2 .8. Variácií s opakovaním n prvkov z
Dôkaz.
k druhov je kn.
Ide o jednoduchú aplikáciu násobiaceho princípu.
O
Kolko je rôznych šestnásťkových čísel s nanajvýš piatimi ciframi?
Riešenie. Každé číslo s nanajvýš piatimi ciframi môžeme doplniť vpredu nulami na
"päťciferné" číslo. Takýchto "päťciferných" čísel je potom tolko, kolko je variácií s opako­
vaním piatich prvkov zo 16 druhov číslic, teda 16 5 l 048 576 .
Príklad
8.
=
14
Príklad 9 . Kolko rôznych podmnožín má n-prvková množina?
Riešenie. Majme n-prvkovú množinu {a11 a2,
, a n } (všimnite si, že očíslovaním
prvkov sme túto množinu usporiadali) . Tvoriac jej podmnožiny každý prvok buď vy­
berieme alebo nevyberieme. Preto je podmnožín (=výberov) tolko, kolko je variácií
s opakovaním n prvkov z dvoch druhov (vybrať, nevybrať) , čiže 2 n .
•
•
•
Definícia. Kombinácia s opakovaním n prvkov z k druhov je ľubovoľný (neuspo­
riadaný) výber n prvkov, pričom každý z prvkov je jedného z k druhov (predpokladá
sa, že prvkov každého druhu je dostatočne veľa, teda aspoň n) .
Veta 2 . 9. Kombinácií s opakovaním
n
prvkov z k druhov je
( nk��1).
Dôkaz. Predstavme si, že už máme vybraných n prvkov a uložili sme ich do radu.
Keďže v kombináciách nezáleží na poradí (výbery {x, a, x} a {x,x,a} sú rovnaké) , tak
uložme prvky prvého druhu na začiatok, potom budú nasledovať prvky druhého druhu,
. . . , až na koniec uložíme prvky k-teho druhu. Aby sme tieto prvky rozlíšili, tak medzi
prvky rôznych druhov vložme nejaké zvláštne objekty, "oddeľovače", ktorých použi­
jeme k- l . (Teda napríklad
l l l predstavuje kombináciu s opakovaním, kde máme
dva prvky prvého druhu, jeden prvok druhého druhu, žiaden prvok tretieho druhu a
jeden prvok štvrtého druhu.) Teraz je už zrejmé, že počet kombinácií s opakovaním n
prvkov z k druhov sa rovná počtu umiestnení k - 1 oddeľovačov na n+k - 1 miest , teda
o o
(nk��l).
o
o
O
Príklad
. . . ' 10?
10.
Kolko neklesajúcich postupností dfžky
r
možno zostaviť z čísel
l, 2
.
Riešenie. Zjavne každému výberu r prvkov z 10 druhov čísel l, 2, . . . , 10 odpovedá
jediná neklesajúca postupnosť. Preto je týchto postupností tolko, kolko je kombinácií
s opakovaním r prvkov z 10 druhov, čiže (r!9). (Všimnite si, že keď tieto výbery us­
poriadame do neklesajúcej postupnosti, tak dostaneme presne ten model kombinácií
s opakovaním, ktorý sme použili v dôkaze vety 2.9.)
Príklad
ll.
Kolko je usporiadaných rozkladov čísla 50 na 6 nenulových sčítancov?
Riešenie. Keby v zadaní nebola požiadavka nenulovosti sčítancov, tak úlohe by od­
povedal model kombinácií s opakovaním 50 prvkov zo 6 druhov z dôkazu vety 2.9. To
preto, lebo 50 si môžeme predstaviť ako rad 50 jednotiek oddelených 5 " oddeľovačmi"
na šesť (možno nulových) sčítancov. Avšak úlohu ľahko prevedieme na tento prípad.
Odoberme z 50 jednotiek šesť a rozdeľme po l medzi sčítance. Tým sme zaručili, že sú
nenulové a zostáva medzi ne rozdeliť 50 - 6 = 44, na čo máme (44:�;1) (�) možností.
Teda požadovaných rozkladov je (4i) = 1 906 884.
=
15
Cvičenia
Cvičenie 2 .1. Kolka deliteľov má číslo 620?
Cvičenie 2 . 2 . Konečné tabulky futbalovej ligy sú "v podstate rovnaké" , ak sú rov­
naké družstvá na prvom, na druhom, na treťom mieste a ak je rovnaká aj štvorica zos­
tupujúcich. Kolka je "v podstate rôznych" výsledných tabuliek, ak ligu hrá 16 družstiev?
Cvičenie 2 . 3 . Kolkými spôsobmi možno uložiť 8 rovnakých veží na šachovnicu tak,
aby sa navzájom neohrozovali?
Cvičenie 2 . 4 . Kolkými spôsobmi možno uložiť 5 bielych a 3 čierne veže na šachov­
nicu 8 x 8 tak, aby sa navzájom neohrozovali? Vyriešte túto úlohu aj pre šachovnicu
12 x 12.
Cvičenie 2 . 5 . Kolkými spôsobmi môžeme usadiť okolo okrúhleho stola alternujúco
IO
dám a 10 pánov?
Cvičenie 2 .6. Kolkými spôsobmi môžno usadiť okolo okrúhleho stola
pánov tak, aby žiadne dve dámy nesedeli vedľa seba?
5 dám a 12
Cvičenie 2 . 7. John pracuje v typickom americkom meste, ktorého plán je tvorený
cestami vytváraj úcimi šachovnicu. John býva na velkej križovatke a pracuje tiež na
križovatke, ale o desať " streets" a osem " avenues" ďalej . Kolka má rôznych najkratších
ciest, ktorými môže chodiť z domu do práce?
Cvičenie 2 .8. Výbor štyroch ľudí má byť zvolený z 10 dám a
12 pánov, pričom
nutne v ňom musí byť aspoň jedna dáma. Kolka je možností na volbu takéhoto výboru?
Cvičenie 2 .9. Do manéže nastupuje v rade za sebou 18 zverov, z ktorých je 5
levov, 6 tigrov a 7 leopardov. Kolka je rôznych nástupov, ak žiadne dva tigre nesmú
ísť bezprostredne za sebou? (Predpokladajte, že všetky zvery sú navzájom od seba
rozlíšiteľné a potom úlohu vyriešte v prípade, keď zvery rovnakého druhu nevieme od
seba odlíšiť.)
16
3. BINOMICKÉ KOEFICIENTY
3.1. Pascalova formula
V tejto kapitole sa budeme zaoberať vlastnosťami binomických koeficientov. Bi­
nomické koeficienty sme zatiaľ definovali pre prirodzené n a k , pričom (�) = O pre
pre n ;: k. Všimnite si, že ak n ;: k , tak (�) =
n < k a (�) =
=
= ( �k) a teda (�) = ( �k).
=
n
n
Veta 3 . 1 ( Pascalova formula) . Nech sú n a k kladné prirodzené čísla. Potom platí
(n) (n - 1 ) + (n- 1 ) .
k
=
k-1
k
Dôkaz. Vetu možno dokázať jednoduchým rozpísaním kombinačných čísel, avšak tu
uprednostníme kombinatorický dôkaz. Nech je S n-prvková množina a nech je x prvok
množiny S . Rozdeľme všetky kombinácie k-tej triedy z S do dvoch skupín. Do skupiny
A dáme tie kombinácie, ktoré obsahujú x a do B dáme tie, ktoré x neobsahujú. Podľa
vety 2.6 je v skupine A (�=:i) kombinácií, lebo k x treba ešte " dovyberať " k-l prvkov
rôznych od x. V skupine B je (nk"1) kombinácií, lebo tam patria všetky kombinácie k-tej
tr iedy z S- {x}. Teda podľa sčítavacieho princípu sa počet kombinácií k-tej triedy z S
r ovná (�=:i)+ (nk"1), čiže (�)=(�=:i)+ (nk"1). O
Predošlú vetu možno názorne ilustrovať na Pascalovom trojuholníku , ktorý dos­
taneme, ak uložíme do (n+ l )-teho riadku postupne kombinácie O, l, . , n -tej triedy z n
prvkov, pozri obrázok 2. Pascalova formula tvrdí, že súčet dvoch kombinačných čísel u­
miestnených tesne vedľa seba sa rovná kombinačnému číslu umiestnenému bezprostredne
pod nimi.
.
Príklad
r
l.
čiže určte Ľ
i=O
.
Spočítajte kombinačné čísla pozd fž diagonály Pascalovho trojuholníka,
(nt).
.
17
Riešenie. Pripočítajme k danej sume ešte (k�1). Potom podľa Pascalovej formuly
Teda
r n i
( k+ ) = (nk+l
+r+l) _ (knl).
+
(�)
(�) (�)
(�) (�) (�)
(�) (�) (�) (�)
(�) (�) (�) (:) (!)
(�) (�) (�) (�) (�) (�)
Obrázok 2
n
r=l
Riešenie. Najprv nájdeme a a b také, aby pre každé prirodzené číslo r platilo r2 =
=a(�)+ bG). Keďže a(�)+ b(�)=
+ br , tak a= 2 a b= l, pričom tento vzťah
platí aj pre r= l. Teda
Príklad 2 . Spočítajte E r2.
n
podľa príkladu l . Preto L r2 =
r=l
+
=
n
Je zrejmé, že uvedeným spôsobom možno nájsť súčet E rk pre ľubovoľné k
r=l
k
= l , 2, .... Označme ck,t koeficienty, pre ktoré platí r k= E Ck,t (�) pre ľubovoľné r E
t=O
Čísla Sk,t =
nazývame Stirlingove čísla druhého druhu.
18
=
N.
3.2. Binomická veta
Veta 3.2 {binomická) . Nech je n kladné prirodzené číslo. Potom pre ľubovoľné x
a y platí
Dôkaz. Platí
(x + y)n
=
(x + y)(x + y) ...(x + y). Keď tieto výrazy roznásobíme tak,
aby už neostala žiadna zátvorka, tak dostaneme množstvo súčinov, pričom každý z nich
obsahuje z každej zátvorky buď x, alebo y. Preto súčiny môžu mať len tvar x k yn k , kde
k= U, l, ... , n. Zostáva určiť, kolkými spôsobmi môžeme súčin xkyn -k dostať. V tomto
súčine je k-krát x a zvyšné prvky sú y. Teda koeficient pri xkyn-k sa rovná počtu
spôsobov, kolkými môžeme vybrať z n zátvoriek k prvkov x (zo zvyšných už musíme
vyberať y), čiže počtu kombinácií k-tej triedy z n prvkov, t e d a (�). O
Príklad 3 . Spočítajte
n
k=O
E (�) 2k.
Riešenie. Podľa binomickej vety platí
n
E (�1) (n�2k).
k
(x + l)m1 (x + l)m2 = (x + 1)�1+m2•
Príklad 4. Spočítajte
=O
Určime koeficienty pri xn vo
výrazoch na obidvoch stranách tejto rovnosti. Podľa binomickej vety (x + l)m1 (x +
Riešenie. Platí
+
l)m2
= ( � (�1 )xi ) ( � (j2)xi ). Výraz xn v súčine týchto súm môžeme dostať len
1=0
J=O
tak, že z prvej sumy vyberieme xk a z druhej xn -k, k
pri :i;n je
=
O, l, . . . , n . Preto koeficientom
Na druhej strane koeficient pri xn vo výraze (x + l)m1+m2 sa podľa binomickej vety
n
rovná (m1 �m2), a preto platí E (�1) (n�2k) (m1 �m2).
k=O
=
19
n
k=O
Príklad 5 . Spočítajte L (�) k2•
n
k=O
Riešenie. Podľa binomickej vety platí L (�)xk
=
(x+ l)n. Výrazy na obidvoch
stranách tejto rovnosti môžeme chápať ako funkcie v premennej x. Zderivovaním týchto
funkcií, následným vynásobením x (x=/= O) a opätovným zderivovaním dostávame
; ) k . xk -1
(
t
k=1
; ) k · xk
(
t
k=1
;) k2 · xk-1
(
t
k=1
=
=
=
n(x + l)n -1
n·x(x +l)n-1
n(x+ l)n-1+ n(n-l)x(x+ l)n-2.
Po dosadení x = l dostávame
Príklad
6.
n
k=O
Spočítajte L (�)
n
k=O
Riešenie. Podľa binomickej vety .platí L (�)xk = (x+ l)n. Zintegrovaním obidvoch
strán dostávame
n xk+l
(
)
k
k+ l
k=O
n
1
-- = --
n +l
(x+ l)n+1+ c.
n+1+ c, čiže c = Táto rovnosť platí pre každé x, teda aj pre x = O. Preto O =
Po dosadení konštanty do predošlého výrazu pri volbe x = l dostávame
k=O k k +l-n +l
n +l- n+ l
·
Vo zvyšku tej to kapitoly uvedieme dve zovšeobecnenia binomickej vety.
20
3.3. Mult inomická veta
Veta 3 . 3 (multinomická). Nech je n kladné prirodzené číslo. Potom pre ľubovoľné
X1, X2,: . . , Xt platÍ
n.l
xn1 n2 . . . Xtnt ,
n1.l ·n2.l · . . . ·nt.1 1 X2
kde suma ide cez všetky nezáporné t-tice nb n2, . . . , nt, pre ktoré n1+ n2 + · ··+ nt= n.
Dôkaz. Dôkaz je obdobou dôkazu binomickej vety. Platí (x1 + x2 +
+ Xt)n =
(x1+ x2 +· · · +xt)(x1 +x2 +· +xt ) . . . (x1 +x2+ +xt ) Keď tieto výrazy roznásobí­
me tak, aby už neostala žiadna zátvorka, tak dostaneme len také výrazy x�1x�2 x�t,
v ktorých n1 + n2 +
+ nt = n. Avšak výraz x�1x�2 x�t môžeme dostať tolkými
spôsobmi, kolkými môžeme usporiadať do radu n1 prvkov XI, n2 prvkov x2, . . . , až nt
prvkov Xt (pozícia týchto prvkov v rade indikuje, z ktorých zátvoriek sme ich vybrali) .
Podľa vety 2. 7 je takýchto permutácií s opakovaním práve n 1 ... ·nt 1 • D
1
(X1+ X2+
·
·
·
+ Xt)n =
·
=
·
·
·
·
·
·
·
·
•
·
·
·
•
•
•
•
•
Príklad 7. Určte koeficient pri x4 vo výraze (l - x+ 2x2)5
•
Riešenie. Najprv určíme, pre ktoré trojice n1, n2, n3 také, že n1 + n2 + n3=
5, platí
ln1xn2x2n3 = x4 (voľte postupne n2 = 4, 3, 2, l, O a určujte n3 a následne n1). Možno
zistiť, že podmienky splňajú len trojice l, 4, O; 2, 2, l a 3, O, 2. Preto koeficient pri x4 je
= 105.
+
+
3.4. Newtonova binomická veta
x
Veta 3 .4 (Newtonova binomická). Nech je
a y také, že 1�1 < l, platí
a reálne číslo.
Potom pre ľubovolné
y
... (a-k+l) pre k > O.
k de (�) = l a (: ) =
Náznak dôkazu. Upravme (x+ y)a= ya(� + l)a a zaveďme substitúciu z=
rozvinieme funkciu (z+ l)a do McLaurinovho radu, dostávame
( z+ l
()
k
a
a(a 1 ) . . . (a k+l) z ((z+ l )a )( ) (O ) z O ) k_
(
k!
k!
k=O k
k=O
k=O
_
�x
Keď
k y-k '
21
čiže
(x + y)a
CXl
=
Ľ
k=O
(�)x k ya k . Zostáva dokázať konvergenciu tohoto radu. Nahliadnite,
CXl
(�)z k konvergujú k nule a ukážte, že od toho člena, ktorý je v absolútnej
hodnote menší ako l, možno rad majorizovať radom ci , kde O < c < l. O
že členy radu Ľ
k=O
Dôsledok. Nech je
a
reálne číslo. Ak
Ix l < l,
tak
= kĽ=O (�)xk .
(x + l)a
CXl
Príklad 8. Aproximujte J2Q.
Riešenie. Je očividné, že suma v predošlom dôsledku sa počíta ľahšie, než suma
Newtonovej binomickej vete. Upravme si preto výraz tak, aby sme umocňovali (x+ l)t
pre nejaké x také, že lxl < l. Platí
v
= (4+ 16) t = 4 ( l4 + l)t = 4t; ( 1/2) (4l ) k = 4[l(!4)o + �l (!4)l + 2 (!4)2+ 2·3 (!4)3 + . . . l=
= 4[l + �. � - �. 116+ . 614 - .. ·l·
CXl
J20
k
tento výraz (len so štyrmi členmi) sa líši od presnej hodnoty J20 o menej ako šesť
desaťtisícin.
Už
Cvičenia
Cvičenie 3 . 1 . Dokážte, že platí (�) (�)
r n
( ii) .
i=O
Cvičenie 3 . 2 . Spočítaj te Ľ
= G:=;) (;).
n
Cvičenie 3 . 3 . Spočítajte Ľ r3.
n
r=O
Cvičenie 3 . 4 . Spočítajte kombinačné čísla v riadku Pascalovho trojuholníka, čiže
určte Ľ (�). Výsledok porovnajte s príkladom
=O
k
n
Cvičenie 3 . 5 . Spoč ítajte Ľ ( l)k(�).
k=O
22
9 z kapitoly 2.
2
f:
(�) .
k=O
Cvičenie
3.6.
Spočítajte
Cvičenie
3. 7.
Spočítajte Ľ
Cvičenie
3.8.
Spočítajte Ľ (�)
n
k=O
n
k=O
(�) k( - 3) k.
)k
(súčet nie je
0) .
Spočítajte
.. .....nt., , kde suma ide cez všetky nezáporné t-tice
n.
n1. n2, ... , nt, pre ktoré n +n2 +···+nt
1
Cvičenie
3.9.
Cvičenie
3.10.
Cvičenie
3.11.
=
Určte koeficient pri x8 vo výraze (2- 3x2 + 2x3)6•
Pomocou Newtonovej binomickej vety aproximujte .J30 a �-
23
4. PRINC1P INKLÚZIE A EXKLÚZIE
4.1. Princíp inklúzie
a
exklúzie
Majme množinu S a vlastnosti p1,p2, . . . , pn , ktoré môžu mať prvky S. Pre i =
= l , 2, . . . , n označme Ai podmnožinu tých prvkov S, ktoré majú vlastnosť Pi. Potom je
A1 nA2 množina tých prvkov S, ktoré majú vlastnosti P1 aj P2 ap. Podmnožinu prvkov
S, ktoré nemajú žiadnu z vlastností p17p2,... ,pn označme A1 n A2 n···nAn. Platí
nasledujúca veta.
Veta 4 . 1 (princíp inklúzie a exklúzie) . Pre počet prvkov množiny
nemajú žiadnu z vlastností Pl!P2, . . . ,pn platí
S, ktoré
IA1 nA2 n . . nAnl = IBI - L lAil + L lAi nAj 1- L lAi nAj nAkl+ ..· + (-l)niA1 nA2 n.. nAni ,
·
·
pričom prvá suma ide cez všetky i z množiny {l, 2, . . . , n}, druhá cez všetky kombinácie
{i, j} druhej triedy množiny { 1 , 2, . . . ,n}, tretia cez všetky kombinácie {i , j, k} tretej
triedy množiny { 1 , 2, . . . , n} atd:
Dôkaz. Vetu dokážeme, ak nahliadneme, že prvok, ktorý nemá žiadnu z vlastností
Pl,P2, ...,pn pripočítavame na pravej strane práve raz, zatiaľ čo prvok majúci nejakú
z týchto vlastností pripočítavame nulakrát. Je zrejmé, že prvok, ktorý nemá žiadnu
z vlastností Pl,P2, . . . , pn prispieva na pravej strane jednotkou, pretože sa vyskytuje len
v S a v žiadnej zo súm sa už nevyskytuje. Uvažujme teraz prvok x, ktorý má práve
t ;: l z uvedených vlastností. Prvok x započítavame v IBI raz; vo výraze Ľ IAil ho
započítavame t = (D krát, pretože má práve t vlastností; vo výraze Ľ lAi n Aj l x
započítavame (;) krát, pretože má (;) dvojíc vlastností; . . . ; posledná suma, v ktorej x
započítavame je Ľ IAil nAÍ2 n... nAit l (suma t-tic ) a tu x započítavame práve (!) l
krát. Teda x pripočítame k pravej strane
=
m-m+m
. . . + (-I)'
krát podľa binomickej vety. O
24
G) = t. m ( -I)'I·-· = ( -!+I)'=
o
Príklad
číslami 4,
6,
Kolko kladných prirodzených čísel menších ako lO 000 nie je deliteľných
ani 10?
l.
Riešenie. Označme p1 vlastnosť " číslo je deliteľné 4" , p2 vlastnosť " číslo je deliteľné
6" a p3 vlastnosť " číslo je deliteľné lO". Pomocou princípu inklúzie a exklúzie nájdeme
počet prvkov množiny S {l, 2 , . . . , 9 999} , ktoré nemajú žiadnu z vlastností Pli P2,
J 2 499, IA2I
ani P3· Platí IA1 I
J 999. Číslo
J
1666 a IA31
l9 J 833,
je deliteľné 4 aj 6 práve vtedy, keď je deliteľné 1 2 . Preto IA1 nA2l
166.
J 499, IA2 nA3l
IA1 nA3l
J
J 333 a IA1 nA2 nA3l =
Teda práve 9 999 - (2 499 + 1666 +999) +(833 +499 +333) - 166 6 334 kladných
prirodzených čísel menších ako 10 000 nie je deliteľných 4, 6, ani 10.
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
V kapitole 2 sme ukázali, ako možno určiť počet kombinácií s opakovaním, keď je
prvkov každého druhu dostatočne veľa. Pomocou princípu inklúzie a exklúzie možno
vyriešiť aj prípad, keď je týchto prvkov menej .
k
Príklad 2 . Kolko je kombinácií s opakovaním 1 0 prvkov z troch druhov, ak máme
dispozícii 3 prvky prvého druhu, 4 prvky druhého druhu a 5 prvkov tretieho druhu?
Riešenie. Uvažujme množinu S všetkých kombinácií s opakovaním
10 prvkov troch
druhov. Označme p1 vlastnosť " kombinácia obsahuje viac ako tri prvky prvého druhu",
P 2 vlastnosť " kombinácia má viac ako štyri prvky druhého druhu" a p3 vlastnosť " kom­
binácia má viac ako päť prvkov tretieho druhu" . Nech je Ai množina tých kombiná­
cií, ktoré majú vlastnosť Pi, i = l, 2, 3. Platí IB I = C0i!�1) = 66. Množina Al po­
zostáva z tých kombinácií, v ktorých sa vyskytujú aspoň štyri prvky prvého druhu.
Každú takúto kombináciu si môžeme predstaviť ako množinu štyroch prvkov prvého
druhu, ku ktorým treba ešte " dovyberať " šesť prvkov z troch druhov. Preto jA1j =
1
1
1
= (6�:� ) = 28, IA21 = e�:� ) = 21, IA31 = (4�:� ) = 1 5 . Podobne možno určiť
IA1 nA2l = C!:�1) = 3, IA1 nA3l = (0!:�1) = l , IA2 nA3l = o a IA1 nA2 nA3l = o .
Teda práve 66- (28 +21 + 15) + (3 +l +O) - O = 6 kombinácií sp!ňa požiadavky úlohy.
V predošlom príklade sme vlastne riešili úlohu, kolko celočíselných riešení má rovnica
10, ak 0 � Xl � 3, 0 � X2 � 4 a 0 � X3 � 5 .
X1 + X2 +X3
=
4.2. Modifikácie princípu inklúzie
a
exklúzie
S a predpokladajme,
l
l.le podmnožiny sp ňajúce tieto vlastnosti sú označené rovnako ako vo vete 4.1. Potom
Veta 4.2. Majme vlastnosti Pl,P2, ...,pn prvkov z množiny
25
pre počet prvkov, ktoré majú aspoň jednu z vlastností Pl,P2 , .
. . ,p n platí
IAl UA2 u . . . u Ani = L IAil- L lAi n A; I+
+L lAi nA; nAkl - . . ·+ (- It-11Al nA2 n ..·nAni,
pričom prvá suma ide cez všetky i z množiny { l , 2, ... , n } , druhá cez všetky kombinácie
{i, j} druhej triedy množiny {l, 2, ... , n } , tretia cez všetky kombinácie {i, j, k} tretej
triedy množiny {l, 2, ... , n } atd:
Dôkaz. Stačí si uvedomiť, že
aplikovať vetu
4. 1. D
IA1 U A2 U ···U Ani = IS I - IA1 n A2 n ···nAni a
Príklad 3 . Kolko kladných prirodzených čísel menších ako 2 000 je deliteľných aspoň
jedným z čísel 4, 10 a 15?
P2 vlastnosť "číslo je deliteľné
J = 4 99 , IA2I =
J=
1
= 1 99 , IA31 =
= 99 , IA1 n A3l =
= 33,
= 133, IA1 n A2l =
1
1
IA2 n A3l = l J = 66 a IA1 n A2 nA3l = l J = 33. Teda podľa vety 4. 2 práve
(4 9 9 +1 9 9 + 133) - ( 99 +33 +66) +33 = 666 čísel menších ako 2000 je deliteľných
aspoň jedným z čísel 4, 10, alebo 15 .
Riešenie. Označme p1 vlastnosť "číslo je deliteľné 4",
10" a P3 vlastnosť "číslo je deliteľné 15" . Platí IA I =
V predošlých príkladoch neboli všetky množiny, ktoré sa vyskytovali v jednej sume,
rovnako velké. V prípadoch, keď takéto množiny sú rovnako velké, môžeme využiť nasle­
dujúcu vetu.
Veta 4 . 3 . Majme vlastnosti PbP2, . . . , p n prvkov množiny S a predpokladajme, že
podmnožiny spfňajúce tieto vlastnosti sú označené rovnako ako vo vete 4.1. Naviac,
nech sú množiny Ai1 nAi2 n n Ait a A;1 nAh n ···n A;t rovnako velké pre každé
t a ľubovoľné výbery množín Ai1, Ai2,
, Ait a A;1, Ah, . .. , A;t také, v ktorých sú
z 1 , z2, .. . , it navzájom rôzne a aj j1, i 2, ... , it sú navzájom rôzne. Potom pre počet
prvkov, ktoré nemajú žiadnu z vlastností PllP2, ..., p n platí
·
·
·
•
•
•
(�) IA1I +(;) IA1 nA2l­
( ;) IA1 nA2 nA3l+ · +( l) n (:) IA1 n A2 n ···nAni·
IA1 nA2 n ···nAni = I BI ·
·
IA1nA2n···nAni = IBI - E IAil + E lAinA; l E IAin
n
nA;nAkl+· ·+(- 1) iA1nA2n···nAni·Keďže k-tie vlastností je ( � ) a všetky množiny
vyskytujúce sa v k-tej sume sú rovnako velké, dostávame požadované tvrdenie. D
Dôkaz. Podľa vety 4. 1 platí
·
26
l,
Príklad 4 . Kolko prirodzených čísel menších ako l 000 000 obsahuj e každú z cifier
2, 3 a 4?
Riešenie. Nech je S množina všetkých prirodzených čísel menších ako l 000 000.
Zjavn� IBI = l 000 000. Označme Pi vlastnosť " číslo neobsahuje cifru i " a Ai množinu
tých čísel z S , ktoré majú vlastnosť Pi, i = l , 2, 3, 4. Potom IA1l = IA2I = IA3I = IA41 =
= 96; pre ľubovoľné i aj, l � i < j � 4, platí lAi n Ajl = 86; pre ľubovoľné i j a k ,
l � i <j < k � 4, platí lAi nAj nAkl = 76; a IA1 nA2 nA3 nA4l = 66 .Podľa vety 4. 3
platí
IA1 nA2 nA3 n A4l = 106 - (�)96 +(�)86- (�)76 +(!)66 = 2 3 160.
Príklad 5 . Sedem pánov navštívilo divadelné predstavenie a všetci si odložili svoje
klobúky v šatni. Kolkými spôsobmi im môže roztržitá šatnárka vydať klobúky späť tak,
aby žiaden pán nedostal svoj vlastný klobúk?
Riešenie. Nech je S množina všetkých rozdaní klobúkov pánom. Potom S má 7!
prvkov podľa vety 2 . 3. Označme Pi vlastnosť " i-ty pán dostane svoj vlastný klobúk"
a Ai množinu tých prvkov z S , ktoré majú vlastnosť Pi, i = l , 2, . . . , 7. Je zrejmé, že
všetky množiny Ai majú rovnako veľa prvkov, podobne všetky množiny Ai n Aj majú
pre l � i <j � 7 rovnako veľa prvkov atď. Teda podľa vety 4. 3 platí
(�)
(�)
(�)
IA1 nA2 n· ·· nA1l = IBI IA1 n A2 nA3l +...
IA1I+ I A1 n A2l!
7
7
···+( - 1) 7 7 IA1nA2n···nA71 = 7! - 6 1_! 116!+ 57!1_215!- 471_314! +. ..
. . +( - 1) 7 7!_ 0 ! = 7! l - l + l - l +. . . +(- 1) 7 l = 1 854.
0 171
O ! l ! 2 1 3!
7!
Teda páni môžu dostať klobúky naspäť l 854 spôsobmi pri splnení podmienok úlohy.
()
·
[
l
Predošlá úloha má aj abstraktnejšiu formuláciu: Kolko permutácií sedemprvkovej
množiny nenecháva žiaden prvok na svojom mieste? Rozvinutím funkcie e-x do McLau-
(E
)
rinovho radu v bode l dostávame nlim
(- l ) i� = e-1. Teda pre n dostatočne
�oo
i =O
velké, približne n!e-1 permutácií n-prvkovej množiny nenecháva žiaden prvok na svo­
( - 1) 7 sa líši od presnej
jom mieste. (Poznamenajme, že výraz
hodnoty e -1 o menej ako tri stotisíciny. )
Po púšti ide karavána 6 tiav. Idú už veľmi dlho v rovnakom poradí, a
preto sa chcú vymeniť tak, aby pred každou ťavou išla iná, ako doteraz. Každá ťava chce
bezprostredne pred sebou vidieť inú ťavu. Kolko je možných preusporiadaní, z ktorých
si môžu vybrať?
Riešenie. Nech je S množina všetkých usporiadaní šiestich tiav. Potom S má 6!
prvkov podľa vety 2. 3. Predpokladajme, že doteraz išli ťavy v poradí l , 2, . . . , 6. O­
značme Pi vlastnosť " i-ta ťava ide bezprostredne pred (i+ l)-tou ťavou" a označme Ai
Príklad
6.
27
i=
množinu tých prvkov z S , ktoré majú vlastnosť Pi ,
l , 2, ..., 5. Množina A1 má tolko
prvkov, kolko je usporiadaní 6 tiav, v ktorých je l bezprostredne pred 2. Takéto usporia­
dania odpovedajú permutáciám množiny {(l , 2), 3, 4, 5, 6}, ktorých j e 5! podľa vety 2.3.
Podobne možno nahliadnúť, že každá z množín Ai má 5! prvkov, každá z množín Ai nAj
má 4! prvkov atď. Teda podľa vety 4.3 platí
= IB I- (�) IA1 I+ (�) IA1 n A2l(�) IA1 n A2 n A3l + ... + (-1)5 (�) IA1 n A2 n· · · n A5l =
IA1 n A2 n· · · n A5l
_
5! 4!- 5! 3! + 5! 2! - -1
5! ! = 309
6! - 1!5! 5! + '
5!·0!
4!· 1!
2!· 3! 3!·2!
·4!
čiže vybrať si môžu z 309 možností.
=
Cvičenia
Cvičenie 4 . 1 . Kolko šesťpísmenkových slov možno vytvoriť z písmen slova tik-tak,
ak žiadne dve rovnaké písmená nesmú nasledovať bezprostredne za sebou?
Kolko prirodzených čísel medzi
mocninami prirodzených čísel?
Cvičenie 4 . 2 .
i= 1, 2,3?
Cvičenie 4 . 3 .
pre
l a 10 000 nie je druhými ani tretími
Kolko celočíselných riešení má rovnica x1 +x2+x3
Kolko celočíselných riešení má rovnica x1 + x2 + X3 =
� X2 � 6 a 2 � X3 � 5?
Cvičenie 4.4.
� X1 � 4,
0
= 16,ak O �Xi � 7
12 ak - l
�
Cvičenie 4 . 5 . Desať manželských párov cestuje vlakom v štyroch vagónoch. Kolký­
mi spôsobmi môže týchto 20 ľudí cestovať, ak v každom vagóne musí sedieť aspoň jeden
z nich a žiaden manželský pár nechce cestovať v spoločnom vagóne?
Cvičenie 4 . 6 . Desať trojčlenných rodín cestuje vlakom v piatich vagónoch. Kolkými
spôsobmi môže týchto 30 ľudí cestovať, ak v každom vagóne musí sedieť aspoň jeden
z nich a všetci príslušníci jednej rodiny musia cestovať v rôznych vagónoch?
Kolko permutácií množiny
Cvičenie 4 . 8 .
Kolko permutácií množiny
na svojom mieste?
práve štyri čísla?
28
{l , 2, ..., 8} nenecháva žiadne párne číslo
Cvičenie 4. 7.
{l , 2,
.
.
.
, 8} necháva na svojom mieste
Cvičenie 4 . 9 . Dvaja učitelia skúšajú súčasne skupinu
12 študentov, každý jeden
predmet. Každý študent odpovedá z jedného predmetu 30 minút. Kolko existuje rozvr­
hov skúšania, ak požadujeme, aby skúšky skončili za šesť hodín?
a
Cvičenie 4 . 1 0 . Kolkými spôsobmi možno usadiť do radu 3 Angličanov, 3 Francúzov
3 Talianov tak, aby žiadni traja krajania nesedeli vedľa seba?
Cvičenie 4. 1 1 . Kolkými spôsobmi možno usadiť okolo okrúhleho stola 3 Angliča­
nov, 3 Francúzov a 3 Talianov tak, aby žiadni traja krajania nesedeli vedľa seba?
Cvičenie 4 . 1 2 . Na kolotoči sa vozí desať detí. Pred ďalšou j azdou chcú zmeniť po­
radie tak, aby pred každým dieťaťom bolo iné, ako doteraz. Kolko je možných preuspo­
riadaní, z ktorých si môžu vybrať?
29
5 . REKURENTNÉ VZŤAHY
5 . 1 . Iterácie
Definíca.
Majme úlohu, ktorá má Pn riešení pri vstupe velkosti n. Nech sú Fi (x) ,
i = O , l , . . . , k , funkcie v premennej x . Rovnica
ktorá platí pre každé n :;: n 0 , sa nazýva rekurentný vz ťah (rekurentná relácia)
pre Pn ·
Príklad l . Sach vznikol pravdepodobne v Indii, pričom génius, ktorý vymyslel túto
nádhernú hru si vraj zapýtal len " skromnú" odmenu. Žiadal, aby mu radža vyplatil za
prvé políčko zrnko obilia, za druhé dve zrnká a za každé ďalšie políčko dvojnásobok
predošlého. Kolko obilia mu mal radža vyplatiť?
Označme Pn počet zrniek obilia, ktoré mal vynálezca dostať za n-té políčko.
Priamo zo zadania plynie rekurentná relácia Pn = 2 · Pn - l ! ktorá platí pre každé n :;: 2.
Postupným iterovaním dostávame Pn = 2 · Pn - l = 2 2 · Pn - 2 = · · · = 2n - l · P 1 = 2 n - l .
Teda za všetky polia šachovnice spolu dostane
·
Riešenie.
64
i =l
=
63
i =O
4-l
= 26
=
264 - l > 16· 1 0006 = 16· 10 1 8
zrniek obilia (využili sme, že 2 10 = l 024 > l 000 ) . Kilogram ryže, ktorý sa bežne predáva
v obchodoch, je balený v sáčkoch o rozmeroch približne 15 x 10 x 5 cm3 . Ak má zrnko ryže
5mm3 , tak vynálezca žiadal za svoj geniálny vynález viac, ako 16·10 1 8· 7505000 · 1 >
> 100 000 000 000 ton obilia, čo, samozrejme, nedostal.
Príklad 2 . V rovine je n priamok, pričom žiadne tri sa nepretínajú v spoločnom
bode, ale každé dve už majú spoločný priesečník. Na kolko častí týchto n priamok delí
rovinu?
Označme Pn počet častí, na ktoré delí rovinu n priamo k. Zrejme p0 = l ,
P 1 2, P2 = 4, avšak PJ = 7. Odvodíme rekurentný vzťah pre Pn · Postupne vložme
do roviny n priamok. Potom každá priamka pretína poslednú n-tú priamku a každá ju
Riešenie.
=
30
pretína v inom bode. Teda prvých n - l priamok delí n-tú priamku na n častí. Každá
z týchto n častí delí jednu oblasť, ktorá vznikla vložením n - l priamok do roviny. Keďže
n l priamok delí rovinu na Pn-l častí, tak Pn = Pn-l +n pre n 2: l . Ciže
Pn = Pn-l +n = Pn-2 +n + (n - l) = ···= po +n +(n- l ) +···+l =
(n l)n 1 n ; l
.
= 1+
= +
( )
Majme dané reálne čísla a0 , a b . . . , a n . Kolkými spôsobmi môžeme zo­
strojiť ich súčin?
Riešenie. Je zrejmé, že tento súčin bude vždy rovnaký, ale čísla môžeme násobiť
v rôznom poradí a môžeme ich rôzne uzátvorkovať. (Pre n = 2 možno súčin zostrojiť
2 ·3 ! = 12 spôsobmi.) Označme Pn počet súčinov n+
l čísel a o , a b . . . , a n . Odvodíme
rekurentný vzťah pre Pn· Uvažujme všetky súčiny čísel a o , ab . . . , a n-l · Ak budeme
číslom a n násobiť až na záver súčin týchto čísel, tak dostaneme 2 ·Pn- l súčinov, lebo
číslom a n môžeme násobiť buď zľava, alebo zprava. Avšak a n možno použiť aj skôr.
Použime a n v k-tom z n - l násobení čísel ao , a b . , a n- l· Tu môžeme a n použiť 4
spôsobmi, lebo buď číslom a n vynásobíme prvý, alebo druhý činiteľ a to zprava, alebo
zľava. Preto Pn = (4n - 2)·Pn-1 pre n 2: 2, pričom PI = 2. Postupným iterovaním
dostávame
Príklad 3 .
.
.
Pn = (4n - 2) P
· n-1 = (4 n - 2)·(4(n- l ) - 2)·Pn- 2 =
·· · = (4n - 2)·(4n - 6)·(4n - 10)· . . . ·6·p 1 = (4n - 2)·(4n - 6)·(4 n - 10) ·... ·6· 2.
.
.
.
Teda
Pn = 2n ·(2n - 1)·(2n - 3) ·(2n - 5) · . . .·3· 1 =
2 n(2n) !
2n
2 n(2n) !
(2n)
= 2n(2n - 2) . . . ·4·2 = 2 nn(n - l) . . . ·2 · 1 = nl! = n ! n ·
( )
Čiže súčin čísel
ao , ab .. . , a n môžeme zostrojiť n !e:) spôsobmi.
Pokiaľ by nás zaujímal len počet rozličných uzátvorkovaní súčinu čísel ao , ab . . ., a n,
(2:) . Čísla
tak tento počet sa podľa predošlého rovná
n !e:) =
e:) sa
nazývajú Katalanove čísla.
V predošlých príkladoch sme sa neuspokojili s rekurentným vzťahom, ale pomocou
neho sme našli explicitné vyjadrenie pre Pn · Takéto vyjadrenie sa nám nemusí vždy
podariť nájsť. To nás však nemusí odrádzať, pretože z hľadiska zložitosti (ak by sme
úlohu riešili na počítači) môže byť rekurentná formula oveľa výhodnejšia, ako explicitné
vyjadrenie Pn (pozri príklad 4) .
V nasledujúcich častiach ukážeme, ako možno nájsť explicitné vyjadrenie v prípade ,
keď je rekurentná relácia lineárna a homogénna.
31
5 . 2 . Lineárne homogénne rekurentné vzťahy
s konštantnými koeficientami - prípad rôznych koreňov
Definíca. Majme úlohu, ktorá má Pn riešení pri vstupe velkosti
. . . , ak l reálne čísla a nech Pn vyhovuje rovnici
Pn + ak l 'Pn 1 + · · · + ao ·Pn k
n.
Nech sú a 0 , a 1 .
=O
(*)
pre každé n � k. Vzťah (*) sa nazýva lineárny homogénny vz ťah s konštantnými
koeficientami. Tento vzťah je k-teho stupňa ak a 0 =l= O.
V ďalšom budeme hľadať riešenia vzťahu (*) v tvare Pn = qn pre komplexné číslo q.
Definícia. Rovnicu x k + ak_ 1 x k l +
rovnica rekurentnej relácie (*) a jej korene
·
·
+
=
a0
O nazývame charakteristická
nazývame charakteristické korene.
·
Lema 5.1. Nech je q reálne alebo komplexné číslo, q =l= O. Potom q n je riešením
rekurentnej relácie (*) práve vtedy, keď je q charakteristickým koreňom.
Dôkaz. Výraz q n je riešením relácie (*) práve vtedy, keď platí
qn
pre každé
n
+
ak l q n
-1
+
·
·
·
+
aoq
n-k
=
0
� k. Keďže je q =l= O, tak predošlá rovnica je ekvivalentná rovnici
Ciže qn je riešením rekurentnej relácie (*) práve vtedy, keď je q charakteristickým ko­
reňom. O
Veta 5.2. Nech sú q 1 , q2 , . . . , qk korene charakteristickej rovnice rekurentnej relácie
(*) , pričom všetky sú navzájom rôzne. Potom je
všeobecné riešenie rekurentného vzťahu (*) .
Dôkaz. Naj prv ukážeme, že uvedený výraz je nesením rekurentného vzťahu (*) .
Keďže qi sú charakteristické korene, tak podľa lemy 5.1 platí
pre každé i = l, 2, . . , k. Teda aj
.
32
pričom sčítaním všetkých takýchto rovníc pre i = l , 2 , . . . , k dostávame , že c1 q? + c2p2 +
+ · · · + Ck QÍ: je riešením vzťahu (* ) .
Zostáva dokázať, že toto riešenie je všeobecné , teda, že pre každú volbu hodnôt
Po , PI ;
. , Pk - l existuje riešenie daného typu (uvedomme si, že hodnoty Pn sú vzťa­
hom (>.' ) a prvými k hodnotami Po , P l l · . , Pk - l určené jednoznačne) . Teda potrebujeme
ukázať, že existujú také konštanty c1 , c2 , . . . , ck , že platí
.
.
.
= c1 c2 +
= C1Q1 C2 Q2
P2 = C1 Q � C2Q�
Po
···+
+
Pl
Tieto rovnice tvoria systém k
tohoto systému je
ck ,
CkQk ,
· · · + CkQ� ,
+
+···+
+
+
lineárnych rovníc s k neznámymi c1 , c2 , . . . , ck.
l
l
Ql
qľ
Maticou
l
Q2
q�
Qk
q�
1
qlk - 1 q2k- 1
qkkčo je známa Vandermondova matica. Jej determinant sa rovná TI ( Qj - Qi ) , kde súčin ide
cez všetky dvojice Qj a Qi , pre ktoré j > i. Keďže korene sú všetky navzájom rôzne, tak
determinant je nenulový a teda existuje jediné riešenie daného systému rovníc. D
V
roku 1 202 publikoval Leonardo z Pisy, nazývaný tiež Fibonacci, nasledujúci prob­
lém.
Príklad 4. Dajme na začiatku roka do velkej klietky párik králikov . Tento párik
vrhne každý mesiac dva králiky, ktoré budú opäť tvoriť párik. Každý ďalší párik , ktorý
sa v klietke objaví, vrhne už dva mesiace po narodení ďalší párik. Kolka párov králikov
bude v klietke na konci roka?
Riešenie. Označme In počet párov králikov na začiatku n-tého mesiaca. Našou úlo­
hou je nájsť fi3 . Keďže v n-tom mesiaci sa môžu reprodukovať len tie králiky, ktoré boli
v klietke na začiatku (n
1 )-tého mesiaca, tak ln+ l
In + In - l · Čiže počty párikov
sp fňaj ú lineárnu homogénnu rekurentnú reláciu s konštantnými koeficientami In
In l
2
l a h = 2 . Charakteristickou rovnicou je x
x
l
O
-fn 2 = O , pričom h
s koreňmi q1
1+2v's a Q2 = 1-2v's . Teda všeobecné riešenie má tvar
=
=
=
fn
=
-
'
Cl
n
2
+ C2
(
l -
2
JS
)
n
33
Aby sa nám ľahšie počítalo, dodefinujme fo tak, aby rekurentná relácia platila aj pre
f2 . Potom fo = l. Sústava rovníc
fo = l = C1+ C2 ,
fi = l = C1 l +2 vÍ5 + C2 l -2 vÍ5 ,
má riešenie
c1
=
·
�a 2=
c
·
-
1- . Preto
2../5
Dosadením možno overiť, že !13 = 3 77.
Všimnite si, že v explicitnej formule vystupovala druhá odmocnina. V tejto formule
sa môžu vyskytovať dokonca komplexné čísla, a to napriek tomu, že rekurentný vzťah .
bude veľmi jednoduchý.
Čísla fn z predošlého príkladu sa nazývajú Fibonacciho čísla.
5 . 3 . Lineárne homogénne rekurentné vzťahy
s konštant nými koeficientami - prípad rovnakých koreňov
Veta 5.3. Nech sú q1 1 q2 ,
, Qt všetky navzájom rôzne charakteristické korene re­
kurentnej relácie (*) . Potom časť všeobecného riešenia odpovedajúca koreňu Qi je
•
•
•
kde si je násobnosť koreňa Qi v charakteristickej rovnici, i
riešenie rekurentného vzťahu (*) má tvar
=
l, 2, . . . , t .
Všeobecné
Pn = P i n + P ; n + · · · + P ; n ·
'
'
'
Označme p(x) = xk + a k_ 1x k- l + . . . , +a0 , čiže p(x) = O je charak­
teristická rovnica vzťahu ( * ) . Nech je Qi Si-násobný koreň tejto rovnice. Potom je Qi
Si-násobný koreň rovnice
Náznak dôkazu.
34
čiže Pn = qf je riešením rekurentného vzťahu ( * ) . Keďže Qi je si-násobným koreňom
predošlej rovnice, tak je (si - 1)-násobným koreňom jej derivácie. Po vynásobení tejto
derivácie x dostávame, že Qi je (si - 1 )-násobným koreňom rovnice
čiže Pn = nqf je riešením rekurentného vzťahu ( * ) . Podobne možno pokračovať aj ďalej ,
pričom každú deriváciu hneď vynásobíme x. Na záver, Qi je jednoduchým koreňom
čiže Pn = ns; l qi je riešením rekurentného vzťahu ( * ) . Z toho plynie, že Pi n a teda aj
Pi,n + P Í, n + + P;, n je riešením rekurentného vzťahu ( * ) . K tomu, aby s �e dokázali,
že ide o všeobecné riešenie zostáva nahliadnúť (analogicky, ako v dôkaze vety 5. 2 ) , že
determinant matice lineárnej sústavy k rovníc s k neznámymi je nenulový. Bez dôkazu
poznamenajme, že táto matica je zovšeobecnenou Vandermondovou maticou a jej de­
terminant je naozaj nenulový. O
·
Príklad
5.
·
·
Určte determinant nasledujúcej trojdiagonálnej matice rádu
An =
4 4 o
l 4 4
o l 4
o
o
o
o
o
o
o
o
4
4
4
o
o
o
o
l
n
Riešenie.
Zjavne IA1 I = 4 a IA2 I = 12. Keď rozvinieme determinant podľa prvého
riadku, tak po malej úprave dostávame IAn l = 41An-l l - 4 1An- 2 1, čiže IAn l - 4 1An l l +
+41-An- 2 1 = O. Táto rovnica je lineárnou homogénnou rekurentnou reláciou s konštant­
nými koeficientami. Jej charakteristická rovnica x 2 - 4x + 4 = O má dvojnásobný ko­
reň 2. Teda všeobecné riešenie má tvar I An l = c 1 2 n + c2 n2n . Aby sa nám ľahšie počítalo,
dodefinujme IAo l tak, aby rekurentná relácia platila aj pre IA2 I · Potom !Ao l = l . Sústava
rovníc
I Ao l
IA1 I
= l = c1
4 = c 1 2 + c2 2
má riešenie c1 = l a c 2 = l , čiže IAn l = 2 n + n 2 n = (n + 1) 2 n .
=
35
Cvičenia
Cvičenie 5 . 1 {Hanojské veže) . Majme tri palice, jedným koncom zastoknuté do
dosky. Na jednej z palíc máme nastoknutých n kruhových diskov rôznych polomerov
usporiadaných tak, že dolu je najväčší disk, potom menší, . . . , až navrchu leží najmenší
disk. Disky možno po jednom prekladať z palice na palicu, avšak nikdy nesmieme položiť
väčší disk na menší. Na aký najmenší možný počet preložení možno preložiť všetky disky
na inú palicu?
Cvičenie 5 . 2 . Majme v priestore n rovín, z ktorých každé tri sa pretínajú v jedinom
spoločnom bode, ale žiadne štyri nemajú spoločný priesečník. Na kolko častí nám týchto
n rovín delí priestor?
l
Cvičenie 5 . 3 . Zafarbíme polia šachovnice
tromi farbami. Kolko je takých
zafarbení, pri ktorých nie sú žiadne dve susedné polia zafarbené rovnakou farbou?
x n
Cvičenie 5 .4. Kolko postupností dfžky n zložených z núl a jednotiek neobsahuje
žiadne dve jednotky bezprostredne za sebou?
Cvičenie 5 . 5 . Kolko slov d fžky n zložených z troch písmen a, b a c neobsahuje
dvojicu bezprostredne za sebou nasledujúcich a?
Cvičenie 5 . 6 . Určte determinanty trojdiagonálnych matíc An , Bn a Cn rádov
An =
5 2 o
3 5 2
o 3 5
o
o
o
o o o
5
2k k o
k 2k k
o k 2k
Cn =
o
Bn =
o
l l o
l l l
o l l
o
o
o
o o o
l
o
o
o
2k
o
Cvičenie 5. 7. Určte determinanty trojdiagonálnych matíc An a Bn rádov
An =
3
2
o
o
o -l o
3 o -l
2 3 o
o 2 3
o o
o o
o o
36
o
o
o
o
o
o
o
o
o
o
o o
o o
o o
o o
3 o l
2 3 o
o 2 3
Bn =
l
2
o
o
o
l
2
o
l
o
l
2
o
l
o
l
o o o o
o o o o
o o o o
o
o
o
o
n
o
o
o
o
o
o
o
o
l o l
2 l o
o 2 l
n
Cvičenie
o rozmeroch
šachovnice a
konci.)
5.8.
l
x
Qn
Kolkými spôsobmi možno pokryť šachovnicu 3 x 2n kockami domina
2? (Návod: Nájdite rekurentné vzťahy pre Pn počet pokrytí 3 x 2n
počet pokrytí 3 x ( 2n 1 ) šachovnice s pridaným jedným poľom na
-
-
37
6 . VYTVÁRAJÚCE
FUNKCIE
6 . 1 . Obyčaj né vytvárajúce
funkcie
Definíca. Obyčajná vytvárajúca funkcia pre číselnú postupnosť {an }� 0 je rad
.
oo
L a n x n = ao + a 1x + a2x 2 + a3 x 3 + · · · + an xn + . .
n =O
Samozrejme, ak by sme za x dosadili nejaké číslo, tak aby mal uvedený výraz zmysel,
mal by tento rad konvergovať. My sa však nebudeme zaoberať jeho konvergenciou. Pre
nás je tento rad len formálny zápis, pomocou ktorého možno vyjadriť celú postupnosť
{ an }� 0 jednou funkciou v premennej x, pričom jednotlivé jej členy od seba môžeme
odlíšiť ako koeficienty pri rôznych mocninách x.
Obyčajné vytvárajúce funkcie sú vhodné na počítanie kombinácií s opakovaním.
=
Veta 6 . 1 . Majme prvky k druhov. Pre l :S i :S k a j 2: O nech ai ,j l ak sa prvok
i-teho druhu môže vyskytovať vo výbere práve j krát a ai, j O inak. Potom obyčajná
vytvárajúca funkcia pre počet Pn výberov n prvkov je
=
čiže počet povolených výberov n prvkov sa rovná koeficientu pri x n v súčine
)
�
lJl c
O
a ; , j Xj ,
Dôkaz. Platí
/Jl c�. a;,;xj ) = (a l ,O + a! , ! X + a l ,,x 2 + ' ' . ) (a,,o + a,, l x + a,,, x' +
.
+ . . . ) . . . (ak ,o + ak, 1x + ak ,2 x 2 + . . . ) V tomto súčine môžeme x n dostať tolkými spô­
sobmi, kolkými možno povyberať zo zátvoriek nenulové hodnoty ai , j xi (teda hodnoty
l · xi ) tak, aby sa súčet mocnín xi rovnal n. Každému takému výberu l · xi1 , l · xh , . . .
. . . , l · xi k odpovedá povolený výber j1 prvkov prvého druhu, }2 prvkov druhého druhu,
38
. . . , až Jk prvkov k-teho druhu. Keďže l ·xÍl · l·xh · ...· l·xi" = l ·x n , tak každý povolený
výber prispieva ku koeficientu pri x n jednotkou, a preto sa počet povolených výberov n
prvkov rovná koeficientu pri x n . O
Príklad l . Majme 6 jabfk, 7 hrušiek, 5 marhúľ a 50 čerešní. Kolkými spôsobmi
môžeme vybrať 8 kusov ovocia, ak počet čerešní musí byť párny a určite nechceme, aby
boli vo výbere práve štyri marhule?
Riešenie. Použijeme vetu 6. 1 . Jabfk môžeme vybrať buď O kusov, alebo l , 2, . . . , až
6 kusov. Preto povoleným výberom jabfk odpovedá polynóm {l + x + x 2 + x 3 + x4+
tx5 + x6). Hruškám odpovedá polynóm {l + x + x 2 + x 3 + x4 + x 5 + x6 + x7), marhuliam
(1 + x + x 2 + x 3 + x5) a čerešniam {l + x 2 + x4 + x6 + x 8 + . . . ) . Ich súčin sa rovná
{l + x + x 2 + x 3 + x 4 + x5 + x6) (1 + x + x 2 + x3 + x 4 + x5 + x6 + x7) (1 + x + x 2 +
+x3 + x5){1 + x 2 + x4 + x6 + x8 + ...) = {l + 2x + 3x2 + 4x3 + 5x4 + 6x5 + 7x6+
+7x7 + 6x8 + ...){l + x + 2x2 + 2x3+2x4 + 3x5 + 2x6 + 3x7 + 2x8 + ...) .
Je zrejmé, že koeficient pri x8 v tomto súčine je 1·2 + 2·3 + 3·2 + 4·3 + 5·2 + 6·2 + 7·2+
+7· 1 + 6·1 = 75. Teda máme 75 výberov 8 kusov ovocia pri splnení podmienok úlohy.
predošlom príklade nás zaujímal výber konkrétneho počtu 8 kusov ovocia. Vý­
znam vytvárajúcich funkcií je však v tom, že pomocou nich môžeme dostať riešenie pre
ľubovoľný počet n kusov. Avšak najprv potrebujeme získať istú zručnosť v narábaní
s mocninnými radmi. Platí
V
oo
L x n = l + x + x 2 + x 3 + · · · = {l - x) -1 ,
n=O
pre postupnosť { a n } �= O • kde a n = l pre n = O , l , . . . ,
môžeme zapísať v " kompaktnom" tvare {l - x) -1 . { Bolo by vhodné poznamenať, že
uvedená rovnosť platí pre - l < x < l .) Po zderivovaní podľa x dostávame
teda obyčajnú vytvárajúcu funkciu
oo
L nx n - 1
=
n =O
a
po
{l - x) - 2
opätovnom zderivovaní
oo
L n(n- l)x n - 2
n =O
=
2(1 -
x) - 3 •
Keďže pre nás je výhodné uvažovať o koeficientoch pri x n ,tak po vynásobení predošlých
vzťahov x, respektíve x 2 , dostávame
oo
nx n
=
X
{1 - x) 2
a
� n (n-l)xn
oo
=
2
2
x)3 .
39
Na pošte majú tri druhy známok. Známky prvých dvoch druhov sú za
l korunu a známky tretieho druhu sú za 2 koruny. Kolkými spôsobmi možno nakúpiť
známky za n korún?
Peniaze, ktoré zaplatíme za známky, si môžeme predstaviť ako koruny troch
typov. Koruny prvého typu sa použijú na známky prvého druhu a týchto korún môžeme
minúť O, l, 2, 3 , . . . Koruny druhého typu použijeme na známky druhého druhu a aj
týchto korún môžeme minúť O, l, 2, 3, . . . . Nakoniec koruny tretieho typu použijeme na
známky tretieho druhu a týchto korún môžeme minúť O, 2, 4, 6, . . . . Podľa vety 6. 1 sa
počet výberov n korún rovná koeficientu pri x n v súčine
Príklad 2.
Riešenie.
.
( 1 + x + x2 + x 3 + . . . ) 2 ( 1 + x2 + x4
t
+
l
l
= (l - x) 2 · (l - x 2 )
+ x6 + . . . ) =
l
l
= (1 x) 3 · (1 + x) "
l
l
o vyraz mozeme
na parc1a'l ne z lomky � ·
= A'
+
Podľa úvah pred príkladom nám však viac vyhovuje tvar
,
A V
•
l
l
+
B'
+
Bx
2Cx2 + D .
+
+
(1
(l - x) 2 ( 1 - x) 3 (l + x )
x)
( 1 + x)
Po úprave na spoločného menovateľa dostávame A( 1 x - x2 + x3) + B (x - x 3 ) + 2C ( x2 +
+x3 ) +D(l - 3x+3x2 - x3 ) = l. Táto sústava štyroch rovníc (v x0, x1 , x2 a x 3 ) o štyroch
neznámych má jediné riešenie A = � , B = 18° , C = i a D = � . Teda
00
00
00
00
l
l = 7L
n + 10 L nx n + -2 L n( n -l ) x n + -1 L ( - l ) n x n =
x
8 n= O
(l + x) 8 n=O
8 n=O
8 n=O
2 l
7 lO 2
- + n + -n 2 - -n + - ( - l ) n x n .
8
8
8 8
n= O 8
C iže známky za n korún možno vybrať -!n2 + n + � + � (- l ) n spôsobmi.
-
= (1
(
A
)
6 . 2 . Exp onenciálne vytváraj úce funkcie
Definíca. Exponenciálna vytvárajúca funkcia pre číselnú postupnosť { a n } �= O
je rad
Exponenciálne vytvárajúce funkcie sú vhodné na počítanie variácií s opakovaním.
40
Veta 6 . 2 . Majme prvky k druhov. Pre l � i � k a j � O nech ai,i = l ak sa
prvok i-teho druhu môže vyskytovať vo výbere presne j krát a ai,i = O inak. Potom
exponenciálna vytvárajúca funkcia pre počet Pn usporiadaných výberov n prvkov je
( oo
)
čiže počet povolených usporiadaných výberov
k
v sucme
' ... .TI
1= l
ai,i zi'!
n
prvkov sa rovná koeficientu pri
.
Dôkaz. Uvažujme výbery n prvkov. Nech má jeden z povolených výberov j 1 prvkov
prvého druhu, h prvkov druhého druhu, . . . , až jk prvkov k-teho druhu, pričom il +
+h + · · · + jk = n . Potom sa súčin odpovedajúcich výrazov zo zátvoriek rovná
x 1
xh
x"
x 1 xh
xi"
1· - . 1· - . .... 1· - = - . - . . . . .
i
i
jl !
h!
l
j 1 ! · h ! · . . · · jk !
.
jk !
xn =
i
jl !
-
h!
jk !
n
n!
.x ·
j 1 ! · h ! · . . · · jk ! n !
=
To znamená, že tento výber prispeje ku koeficientu pri n. počtom permutácií s opakovaním n prvkov z k druhov, v ktorých máme j 1 prvkov prvého druhu, h prvkov druhého
druhu, . . . , až jk prvkov k-teho druhu. Teda každý povolený výber prispeje ku ko­
eficientu pri n. počtom usporiadaní tohoto výberu, a preto sa počet usporiadaných
D
výberov n prvkov rovná koeficientu pri
Skôr, ako uvedieme príklad poznamenajme, že exponenciálnu vytvárajúcu funkciu pre
postupnosť { a n }�= O ' kde a n = l pre n = O, l , . . . , môžeme zapísať v " kompaktnom"
tvare e z ' čiže
a exponenciálnu vytvárajúcu funkciu pre postupnosť { ( - l ) n }�= O môžeme zapísať
Kolkými spôsobmi možno zafarbiť rad n štvorcov tromi farbami, čer­
venou, zelenou a modrou, ak počet štvorcov zafarbených červenou farbou musí byť
párny?
Príklad
3.
41
Riešenie. Exponenciálnou vytvárajúcou funkciou pre požadovaný počet zafarbení je
( l + x + 2Tx2 + x33! + . . . ) 2 ( l + 2Tx2 + x44! + x6 + . . . ) = (e:z: ) 2 "21 (e:z: + e :z: ) =
) -x" .
l
x" ) - L
( 3x ) " L
oo
- l ( e 3 :z: + e ) - -l
-- oo - ( 3 " +
2
2
n!
n!
2
n!
B
z
+
n =O
C iže rad n štvorcov možno zafarbiť
n =O
n =O
l
4 (3" + l ) spôsobmi pri splnení podmienok úlohy.
Všimnite si rozdiel medzi príkladmi 2 a
6.3.
!
3.
Binárne stromy
Vytvárajúce funkcie môžeme chápať aj ako úplne formálne rady bez kombinatorické­
ho významu. V tejto časti určíme počet binárnych stromov na n vrcholoch pre ľubovoľné
n � l pomocou obyčaj nej vytvárajúcej funkcie.
Definícia. Binárny strom je štruktúra s koreňom, kde každý prvok môže mať buď
pravého, alebo ľavého syna, ktorí sú opäť prvkami tejto štruktúry. Prvky binárneho
stromu nazývame vrcholy.
Na obrázku 3 sú graficky znázornené všetky binárne stromy na troch vrcholoch. Koreň
je vyznačený plným krúžkom.
v
Obrázok 3
Príklad 4 . Kolko je binárnych stromov na n vrcholoch?
Riešenie. Označme Pn počet binárnych stromov na n vrcholoch. Ak uvažujeme, že
existuje jediný prázdny binárny strom, tak Po = P 1 = l , P 2 = 2, P3 = 5 atď. Každého
syna koreňa môžeme považovať za koreň menšieho podstromu, ktorý je opäť binárnym
n 1
stromom ( hoci prázdnym ) . Preto Pn = E Pk · Pn l k pre n
k =O
42
� l.
Nech je p(x) obyčajná
vytvárajúca funkcia pre postupnosť
oo
E Pn X n .
n=O
{Pn }�=O • čiže p(x)
Keď vynásobíme
rekurentný vzťah x n a potom sčítame všetky takto získané rovnice pre n
dostávame
(
�
oo
= l , 2,
.
.
.
, tak
n-1
Pn = L Pk · Pn- l -k
k=O
n 1
n-1
n
n
.
.
Pn X = L Pp Pn l k x = x L Pk X k .Pn 1 kX n-l k
k=O
k =O
oo n
oo
oo n-1
k · Pn-k X n k
n=X
k Pn- -kX n - 1-k = X
1
n=l
n=l k=O
n=O k=O
oo
oo
oo
oo
k
k
n
k
n
Pn X n Pn - kX - x PkX
Pn X - l - X PkX
)
_
{; �
·
_
oo
{; �
_
p(x) - l = x L PkX k · p(x) = x · p(x) · p(x) = x (p(x))2
k=O
l±
4x
p (x ) =
.
2x
oo
E Pn X " , tak p(O) = Po = l . Preto vyhovuje iba riešenie p (x) =
n=O
(overte si, že limita v nule je naozaj l , teda funkcia má v nule odstrániteľný bod nespojitosti) . Podľa Newtonovej binomickej vety pre dostatočne malé x (ak lxl < i) platí
Ked'že p(x) =
f
f(�)
1 2 (-4x)" l +
(- 1)" 4" x " =
(- 4x + l) ! =
=
n=O
n=l
oo l 1 5
n2
00 1 . 3. 5. . . . {2n 3) " "
3
3
2 2 2 2 .. .
2 n-1 2" 2" x"
2x=
{-1)
n!
n!
n=l
n=l
1
"
2 (n - l ) ! - � x " =
= 1 _ 1· 3·5·(n... l !
(n l)! n
)
1
3)·2·4·6· ...·{ 2n-2) - � x " =
= _ 1· 3·5· . .. ·(2nn
(n - l)! · (n - l)!
2n
2 � x " = 1 _ 2x
=1_
n=O n n + l
n=l n l n
.
Preto
p(x) =
( l - l + 2x n�O (�)
)
y"
) = n�O e:)
( )
x " ' čiže Pn
l
ntl ( 2n")·
Teda počet binárnych stromov sa rovná Katalanovmu číslu.
43
Cvičenia
ak
Cvičenie 6. 1 .
x
::;
8,
y
Kolko nezáporných celočíselných riešení má rovnica
� 2 a z =/= 3?
x + y + 3z
=
15,
Cvičenie 6 . 2 . Máme 7 cukríkov jedného druhu, 8 druhého druhu a 9 tretieho druhu;
Kolkými spôsobmi ich môžeme rozdeliť dvom deťom tak, aby každé z nich dostalo 1 2
cukríkov?
Cvičenie 6 . 3 .
Kolkými spôsobmi možno zaplatiť 2 koruny slovenskými mincami?
Cvičenie 6 . 4. Na trhu maj ú dostatočne veľa j abfk po l korune, hrušiek po 2 koruny
a sliviek po 2 koruny. Kolko je rôznych nákupov ovocia za n korún?
Cvičenie 6 . 5 . Kolkými spôsobmi možno zafarbiť rad n štvorcov štyrmi farbami ,
červenou, zelenou, modrou a žltou, ak párny počet štvorcov musí byť zafarbený červenou
farbou a párny počet modrou farbou?
Kolko čísel s n ciframi , zložených len z cifier l ,
kladný párny počet výskytov l aj 3?
Cvičenie 6 . 6 .
Kolko čísel s n ciframi 4, 5 ,
sa v nich vyskytuje aspoň raz?
Cvičenie 6. 7.
pričom 5 aj
44
7
6, 7, 8
a
9
3,
5, 7 a 9,
obsahuj e
má párny počet cifier 4 aj
6,
7. SYSTÉMY
ROZLIČNÝCH REPREZENTANTOV
7. 1 . Hallova veta
Na zoznamovaciom večierku sa stretlo niekolko slobodných dievčat a slobodných mlá­
dencov. Všetky slečny sa chcú vydať, pričom partnera si chcú vybrať už na tomto
večierku. Pokiaľ by si nekládli žiadne podmienky, tak všetky sa môžu vydať práve vte­
dy, keď je mládencov aspoň tolko, ako dievčat. Avšak ani vydajachtivé slečny sa nehrnú
do manželstva až tak unáhlene. Každej z dievčat sa páčia len niektorí z mládencov, teda
každá má zoznam možných nápadníkov. Za akých podmienok je možné vydať všetky
slečny za mládencov z ich zoznamov?
Definícia. Nech je A1 1 A 2 , . . . , A n systém podmnožín množiny X . Potom x 1 , x2,
. . . , X n nazývame systém rozličných reprezentantov (transverzála) , ak Xi E Ai
pre i = l , 2, . . . , n a Xi # Xj pre l � i < j � n.
V predošlom príklade množine X odpovedá množina mládencov, Ai je zoznam mož­
ných nápadníkov pre i-tu slečnu a systém rozličných reprezentantov (ak existuje) odpo­
vedá sobášom, pričom i-ta slečna sa vydá za Xi-teho mládenca.
Nasledujúcu vetu dokázal P. Hall v roku 19 35. Táto veta dáva úplné riešenie pre­
došlého príkladu, a preto sa niekedy nazýva " sobášna veta" .
Veta 7. 1 (Hallova veta) . Systém A1 1 A 2 , . . . , A n podmnožín množiny X má transverzálu práve vtedy, keď pre každé k = l , 2, . . . , n a pre každý výber i 1 1 i 2 , . . . , ik taký,
že l � i 1 < i2 < · · · < ik � n platí
Dôkaz. Ak má systém A1 1 A2 , . . . , A n transverzálu x l ! x2 , . . . , X n , tak podmienka je
istotne splnená, keďže I A i1 U Ai2 U U Aik l � l { Xi1 , Xi2 , , Xik } l = k . Matematickou
indukciou podľa n dokážeme, že keď systém A1 , A 2 , . . . , A n sp fňa podmienku Hallovej
·
·
·
•
•
•
vety, tak má transverzálu.
l 0 Ak n = l , tak l A 1 l � l , lebo systém sp fňa podmienku vety. Teda existuje prvok
x 1 E A1 , ktorý je transverzálou jednomnožinového systému A 1 .
45
2° Nech n > l a nech má transverzálu každý systém, ktorý má menej ako n množín a
spfňa podmienku Hallovej vety. Rozlíšime dva prípady.
(i) Pre každé k = l , 2, . . . , n- l a pre každý výber i 1 , i2 , . . . , Ík taký, že l � i 1 <
< i2 < · · · < i k � n platí I Ai1 U Ai 2 U · · · U Ai k l � k + l .
To znamená, že podmienka j e splnená pre každý výber s rezervou. Keďže
podmienka je splnená, tak l An i � l . Vyberme Xn E A n a uvažujme systém
A 1 - { xn } , A2 - { xn } , . . . , An- 1 - { xn } · Dokážeme, že tento systém spfňa pod·
mienku Hallovej vety. Nech l � k � n- l a nech pre i 1 , i2 , . . . , Ík platí l �
� i 1 < i2 < · · · < ik � n- l . Potom
I ( Ai1 - { Xn } ) U ( Ai 2 - { Xn } ) U · · · U ( Ai k - {xn } ) l = I ( Ai1 U Ai 2 U · · · U Aik ) - { xn } l �
� I Ai l u Ai 2 u . . . u Ai k 1 - l � ( k + l) - l = k .
Teda systém A 1 - {xn } , A2 - {xn } , . . . , An- 1 - {xn } spfňa podmienku Hallovej ve·
ty a podľa indukčného predpokladu má transverzálu XI , x2 , . . , Xn- b ktorú
možno doplniť prvkom X n na transverzálu systému Ab A 2 , . . . , A n - l ! An .
(ii) Pre nejaké p také, že l � p � n - l a pre nejaký výber i 1 , i2 , . . , Íp taký, že
l � i1 < i2 < · · · < ip � n platí I Ai1 U Ai2 U · · · U Aip l = p .
To znamená, že pre tento výber je podmienka Hallovej vety splnená tesne.
K vôli jednoduchšiemu zápisu predpokladajme, že p množín tohoto výberu tvo­
ria množiny A 1 1 A2 , . . . , Ap . Systém A 1 1 A2 , . . . , Ap je podsystémom systému
A1 1 A2 , . . . , An , a preto A1 1 A2 , . . . , Ap sp fňa podmienku Hallovej vety. Keďže
p � n- l , tak podľa indukčného predpokladu má A 1 1 A2 , . . . , Ap transverzálu
x 1 , x2 , . . . , Xp · Všimnime
si, že platí A1 U A 2 U · · · U Ap = { x l ! x2 , . . . , Xp } · Oz­
·
{
načme Y = x l , x2 , . . . , xp } a uvažujme systém n - p množín Ap+1 - Y, Ap+2 - Y,
. . . , An - Y . Nech l � k � n- p a nech pre JI , J2 , . . . , jk platí p + l � J I <
< h < . . · < J k � n. Potom
.
.
I ( Aj l - Y ) u ( Ah - Y ) u . . . u ( Ajk - Y ) I = I ( Ail u Ah u . . . u Ajk ) - Y l =
= I ( Y u Aj1 u Ah u · · · u Aik ) - Y l = I ( A1 UA2 u . . . uAp u Aii uAh u . . . u Aik ) - Y l =
= l A I u A2 u . . . u Ap u Ah u Ah u . . . UAjk 1 I Y I � (p +k) - p = k .
Teda systém Ap+ l - Y, Ap+2 -Y, . . . , An - Y spfňa podmienku Hallovej vety.
Keďže p � l , tak n-p � n - l a podľa indukčného predpokladu má systém
Ap+ I - Y, Ap+ 2 - Y, . . . , An - Y transverzálu Xp+ b Xp+2 • . . . , Xn · Túto transverzá­
lu možno doplniť transverzálou x1 , x2 , . . . , Xp systému A1 . A2 , . . . , Ap na trans­
verzálu x 1 , x2 , . . . , Xp , Xp+b Xp+2 • . . . , Xn systému A b A 2 , . . . , An . O
Podmienka z Hallovej vety sa nazýva Hallovou podmienkou.
Príklad
l.
Majme päť dievčat a päť mládencov. Mládenci sú označení číslami
=
za mládencov, ktorí sa im páčia?
l, 2, . . . , 5 a prvej slečne sa páčia mládenci s číslami l a 4, teda A 1 = { 1 , 4 } , ďalej
A2
{ l , 3 } , A 3 = { l , 2, 4, 5} , A4 = { l , 3, 4} a A5 = {3, 4 } . Možno vydať všetky slečny
46
Riešenie. Keďže I A 1 U A2 U A4 U A5 I 1 { 1 , 3 , 4} 1 3 , tak podľa Hallovej vety systém
A1 , A2 , . . . , As nemá transverzálu. Teda nemožno všetky slečny vydať tak, aby mali za
=
=
manželov mládencov, ktorí sa im páčia.
Definícia. Latinský obdfžnik typu r x n je obdlžniková tabulka s r riadkami a
n sdpcami, v ktorej je v každom poli zapísaný prvok z množiny { l , 2, . . . , n } , pričom
v každom riadku a v každom stlpci sa každý prvok z množiny { l , 2, . . . , n} vyskytuje
nanajvýš raz. Latinský obdlžnik typu n x n nazývame latinský štvorec.
Na obrázku 4 sú príklady latinských štvorcov typu 4
2
3 4
2 3 4 l
3 4 l 2
4 l 2 3
l
4.
x
2
3 4
2 l 4 3
3 4 l 2
4 3 2 l
l
Obrázok 4
Veta 7 . 2 . Každý latinský obdfžnik možno doplniť na latinský štvorec.
Dôkaz. Majme latinský obdlžnik C typu r x n, kde r < n . Vetu dokážeme, ak nahliad­
neme, že C možno rozšíriť pridaním nového riadku na latinský obdlžnik typu ( r+ l ) x n.
Nech množina Ai obsahuje tie prvky z { 1 , 2, . . . , n}, ktoré sa nevyskytujú v i-tom sdpci
latinského obdlžnika .C, l :: i :: n. Dokážeme, že systém A 1 . A2 , . . . , An podmnožín
množiny { l , 2, . . , n} splňa Hallovu podmienku. Nech l :: k :: n a nech pre ·Í 1 . i2 , . . . , Í k
platí l :: i1 < i2 < · · · < ik :: n. Potom
.
Keďže všetky prvky v riadku C sú rôzne, tak každý prvok z množiny { l , 2, . . . , n} sa
vyskytuje v C práve r krát. To znamená, že každý takýto prvok chýba v r množinách
systému A 1 , A2 , . , A n a teda vyskytuje sa v n r množinách tohoto systému. Teda
každý prvok z množiny { l , 2, . . . , n} sa vyskytuje v množinách A i1 , Ai 2 , , Ai k nanajvýš
n r krát . Preto
.
.
•
I A · U A 1· 2 U
'l
.
.
·
u A '· k l
>
-
k (n r)
n-r
=
k
•
•
'
čiže systém A1. A2 , . . . , An splňa Hallovu podmienku. Podľa Hallovej vety má tento
systém transverzálu X1 , x2 , , Xn a dopísaním prvkov transverzály pod latinský obdlž­
nik C dostávame latinský obdlžnik typu (r+ l ) x n. O
.
.
•
47
7. 2 . Zovšeobecnenie Hallovej vety
Ako sme videli v príklade l, nie vždy sa nám podarí uspokojiť všetky vydajachtivé
slečny. V takom prípade je vhodné zistiť, aký najväčší počet dievčat môžeme vydať.
Veta 7. 3 . Nech je A 1 , A2 , . . . , An systém podmnožín množiny X a nech r spfňa
l :: r :: n. V systéme A 1 , A2 , . . . , An existuje r-množinový podsystém s transverzálou
práve vtedy, keď pre každé k = l, 2, . . . , n a pre každý výber i 1 , i2 , . . . , ik taký, že
l :: i 1 < i2 < · · < ik :: n platí
·
Dôkaz. Nech je Y množina n-r prvkov taká, že X n Y = 0. Potom Ai n Y = 0
pre každé i = l, 2 , . . . , n, keďže Ai � X . Uvažujme systém A1 U Y, A 2 U Y, . . . , An U Y
podmnožín množiny X U Y .
Najprv ukážeme, že A 1 , A2 , . . . , A n má r-množinový podsystém s transverzálou práve
vtedy, keď má systém A1 U Y, A2 U Y, . . . , An U Y transverzálu. Predpokladajme, že
r-množinový podsystém systému A1 , A2 , . . . , A n má transverzálu. Nech tento podsystém tvoria množiny A1 , A2 , . . . , Ar s transverzálou x1 , x2 , . . . , Xr . Nech Y = { y 1 , y 2 , . . .
. . . , Yn -r } . Potom je x 1 , x2 , . . . , Xr , Yl , Y2 , . . . , Yn -r transverzála systému A 1 U Y, A 2U
U Y, . . . , An U Y . Teraz naopak predpokladajme, že A1 U Y, A 2 U Y, . . . , An U Y má
transverzálu w 1 , w2 , . . . , Wn · Keďže Y má n-r prvkov, tak aspoň r prvkov z w1 . w2 , . . .
. . . , Wn patrí do X. Nech sú to prvky w1 , w2 , . . . , Wr · Potom w1 EA1 . w2 EA2 , . . . , Wr EAr ,
čiže systém A 1 , A2 , . . . , An obsahuje r-množinový podsystém A1 , A2 , . . . , Ar , ktorý má
tr ansverzál u.
Podľa Hallovej vety má systém A1 U Y, A2 U Y, . . . , A n U Y transverzálu práve vtedy,
keď pre každé k l, 2 , . . . , n a pre každý výber i 1 , i2 , . . . , ik taký, že l :: i 1 < i2 < · <
< ik :: n platí
(*)
=
·
·
Keďže
/ (A i 1
U
Y) U (Ai2 U Y) U · · · U (A i k U Y) / / (Ai1 U Ai2 U · · · U Aik ) U Y /
/ Ai1 U Ai 2 U · · · U A i k / + / Y / / Ai1 u Ai2 U · · · U Ai k / + n -r,
=
=
=
=
tak ( * ) platí práve vtedy, keď / Ai1 U Ai2 U · · · U Aik l ;: k - ( n-r ) . O
Nech je zo šachovnice typu 4 x 7 vyrezaných ll polí podľa obrázku 5.
Na dve susedné políčka, z ktorých žiadne nie je vyrezané, môžeme položiť kocku domina
o rozmeroch 2 x l . Aký najväčší počet bielych políčok môžeme pokryť kockami domina
tak, aby sa tieto navzájom neprekrývali?
Príklad
48
2.
bl
b2
Čl
bJ
bs
Č6
b4
b6
Č4
.
.
.
.
.
.
.
.
.
·
.
.
.
.
.
.
.
.
.
·
.
.
.
.
.
.
.
.
.
·
.
.
.
.
.
.
.
.
.
·
.
.
.
.
.
.
.
.
.
·
.
.
.
.
.
.
.
.
.
·
.
.
.
.
.
.
.
.
.
·
.
.
.
.
.
.
.
.
.
·
.
.
.
.
.
.
.
.
.
·
.
.
.
.
.
.
.
.
.
·
.
.
·
.
.
.
·
.
.
.
.
.
·
.
.
.
·
.
.
.
.
.
·
.
.
.
·
.
.
.
.
.
·
.
.
.
·
.
.
.
.
.
·
.
.
.
·
.
.
.
.
.
·
.
.
.
·
.
.
.
.
.
·
.
.
.
·
.
.
.
.
.
·
.
.
.
·
.
.
.
.
.
·
.
.
.
·
.
.
.
.
.
·
.
.
.
·
.
.
.
Obrázok
ČJ
Č2
b7
čs
ba
Č7
bg
čs
5
Riešenie. Označme biele a čierne polia tak, ako je to naznačené na obrázku 5 . Každá
kocka domina pokrýva vždy jedno biele a jedno čierne políčko. Pre každé biele pole
bi označme Ai množinu čiernych nevyrezaných polí susedných s bi , i = l , 2 , . . . , 9. Po­
tom A1 = {0} , A2 = {č l } , AJ = {č4 } , A 4 = {č1 1 č2 } , As = {č4 , č5 } , A 6 = { č4 } ,
A7 = {č2 , čs , č7 } , As = {čJ , čs , čs } a Ag = {čs , č7, čs } . Je zrejmé, že maximálny
počet pokrytých bielych políčok odpovedá transverzále najväčšieho podsystému sys­
tému A1 , A2 , . . . , Ag. Keďže IA1 U AJ U As U A6 1 2 = 4 - (9-7) , tak podľa vety 7. 3
nemôžeme pokryť viac, ako 7 bielych polí. Po niekolkých ďalších pokusoch zistíme, že
asi už každý k-prvkový podsystém systému A1 1 A2 , , Ag obsahuje aspoň k - 2 prvkov,
l :: k :: 9. To však znamená, že by sme mali dokázať pokryť sedem bielych polí podľa
vety 7. 3. Jedným z takých pokrytí je pokrytie b2 - č1 1 bJ - č4, b4 - č2 , bs - č5 , b7 - čs ,
=
.
•
•
ba - ČJ , bg - Č7 .
Všimnite si, ž e z deviatich bielych polí s a nám v predošlom príklade podarilo pokryť
iba sedem napriek tomu, že sme mali k dispozícii osem čiernych polí.
Cvičenia
Cvičenie 7. 1 . Nech je A 1 , A2 , . . . , An systém množín, ktorý má transverzálu, a nech
sa x nachádza aspoň v jednej z množín Ab A2 , . . , An · Dokážte, že potom existuje
.
transverzála systému Ab A2 , , A n obsahujúca x. Ďalej ukážte, že ak x E Ab tak
systém Ab A2 , AJ , . . . , An ešte nemusí mať transverzálu tvaru x, x2 , XJ , . . , Xn , čiže nie
je vždy možné predurčiť, ktorú množinu bude prvok x reprezentovať.
.
.
•
.
Cvičenie 7 . 2 . Nech je A1 , A2 , . . . , A n systém množín, v ktorom pre každé k =
< ik � n platí
= l , 2, . . . , n a pre každý výber i1 , i2 , . . . , Ík taký, že l � i1 < i2 <
I Ai1 U Ai2 U · · · U Aik l � k + l . Nech x E A1 . Dokážte, že potom existuje transverzála
·
·
·
x, X2 , XJ , . . . ' Xn systému A l , A2 , AJ , . . ' A n .
.
49
Firma potrebuje obsadiť 7 rôznych pracovných činností Pb P2 , . . . , p7,
pričom má k dispozícii 8 zamestnancov ab a2 , . . . , a8 . Každý zamestnanec môže vykoná­
vať len niektoré činnosti. Prvý má kvalifikáciu pre {Pl , P4 , Ps } , druhý pre {P2 , P6 , P7 } a
ďalší postupne pre { p3 , p4 } , { Pb Ps } , {p3 } , {p2 , p3 } , { Pb P3 } a posledný len pre {p l } .
Aký najväčší počet činností môže firma kvalifikovane obsadiť týmito zamestnancami?
Cvičenie
7. 3.
Na zoznamovaciom večierku je n slobodných dievčat a n slobodných
mládencov. Predpokladajme, že existuje číslo p také, že každej slečne sa páči práve p
mládencov a každý mládenec sa páči práve p slečnám. Dokážte, že potom možno každej
slečne priradiť nápadníka, ktorý sa jej páči.
Cvičenie
7. 4.
Cvičenie 7. 5 . Na tanečnom večierku je n dievčat a n mládencov. Predpokladajme,
že existuje číslo p také, že každej slečne sa páči práve p mládencov a každý mládenec sa
páči práve p slečnám. Dokážte, že možno zorganizovať p tanečných kôl tak, aby v každom
kole tancovalo každé dievča len s takým chlapcom, ktorý sa jej páči, a aby počas týchto
p kôl tancovalo každé dievča so všetkými p mládencami, ktorí sa jej páčia.
Cvičenie 7.6. Majme šachovnicu typu
n, pričom m aj n sú nepárne čísla.
Predpokladajme, že pole v ľavom hornom rohu je biele. Dokážte, že ak z tejto šachovnice
vyrežeme ľubovoľné biele pole, tak deravú šachovnicu, ktorú takto dostaneme, možno
úplne pokryť kockami domina.
m x
Cvičenie 7.7. Určte počet transverzál systému množín A1 , A2 , . . . , A n , kde A 1 =
= { 1 , 2} , A2 = {2, 3} , . . . , A n - l = { n- 1 , n} , A n = { n, 1 } .
Cvičenie 7.8. Nech n � 2 a nech je Ab A2 , . . . , A n taký systém podmnožín množiny
,
{ 1 2, . . . , n } , v ktorom A i = { 1 , 2, . . . , n} - {i} pre i = l , 2, . . . , n . Kolko rôznych
transverzál má tento systém?
Cvičenie 7.9. Nech je Ab A2 , . . . , A n systém podmnožín množiny { 1 , 2, . . . , n } ,
n � 2, pričom A 1 = { 1 , 2} , A n = {n- l , n} a A i = {i- l , i, i + l } pre i = 2, 3 , . . . , n- 1 .
Kolko rôznych transverzál má tento systém? ( Návod: Odvoďte rekurentný vzťah pre
počet Pn transverzál systému A 1 , A2 , . . . , A n .)
50
8 . BLOKOVÉ PLÁNY
8 . 1 . Blokové plány
V roku 1850 reverend Thomas P. Kirkman položil nasledujúci problém. Vychováva­
telka chodí so svojou triedou, v ktorej je presne 1 5 dievčat, každý deň na vychádzku.
Dievčatá sa prechádzajú vždy v piatich radoch po trojiciach, čiže každé z dievčat má dve
spoločníčky. Je možné naplánovať vychádzky na celý týždeň tak, aby sa každé dievča
prechádzalo v trojici s každou svojou spolužiačkou práve raz?
Kirkmanov problém školáčok sa považuje za jeden z prvých problémov teórie blo­
kových plánov. Táto teória má aplikácie v plánovaní experimentov, teórii kódovania a
mnohých ďalších matematických disciplínach.
Definícia. Nech je B systém podmnožín konečnej množiny V . Usporiadanú dvojicu
D = ( V, B) nazývame blokový plán typu (n, k) , ak platí
(dl ) I V I = n, čiže V má n prvkov;
(d2) I B I = k pre každé B E B;
(d3) ak sú u , v E V , u =j:. v , tak existuje jediné B E B také, že u , v E B .
Ak je D = ( V, B ) blokový plán, tak prvky množiny V nazývame body a prvky B
nazývame bloky.
Veta 8 . 1 . Nech je D = (V, B) blokový plán typu (n, k) . Potom platí
(i) každý bod leží v práve
..
n(n- 1)
( ll ) I B I = k(k 1 ) .
blokoch;
Dôkaz. V dôkaze využijeme " double counting" metódu, čiže dvoma rôznymi spô­
sobmi spočítame prvky jednej množiny. Nech v E V. Uvažujme všetky body blokového
plánu, okrem v . Podľa (dl) platí I V- { v } l = n - l . Nech sú Bb B2 , . . . , B1 všetky
bloky z B, ktoré obsahujú v . Podľa (d3) prienik ľubovoľných dvoch blokov z B obsahuje
nanajvýš jeden bod a opäť podľa (d3) každý bod z V - { v } leží v jednom z blokov
, B, . To znamená, že každý bod z V- {v} leží v práve jednom z blokov
B 1, B2 ,
7
B2
,
,
B, . Keďže každý blok má k bodov podľa (d2) , tak V - { v } obsahuje l(k- 1 )
B1
blokoch. Keďže v bol ľubovoľný
bodov. Teda n- 1 = l ( k - 1 ) , a preto v leží v práve
bod z V, tak tvrdenie platí pre každý bod blokového plánu D .
•
.
.
•
•
•
51
Druhé tvrdenie dokážeme tak, že spočítame všetky usporiadané dvojice ( v , B) , kde
Na
blokoch, a preto je takýchto dvojíc n
v E B. Podľa (i) leží každý bod v
druhej strane, každý blok obsahuje k bodov podľa (d2) , a preto je požadovaných dvojíc
k I BI . Teda n
blokov. D
= k IBI , čiže B má
Podľa vety 8 . 1 môže blokový plán typu ( n , k) existovať len ak platí
n-1
O (mod (k- 1 ) )
n ( n - 1 ) = O (mod k ( k - 1 ) ) .
Definícia. Blokový plán typu ( n , 3 ) nazývame Steinerov systém troj íc.
Už v roku 1847 Kirkman dokázal, že podmienky na kongruenciu pre n sú nielen
nutné, ale aj postačujúce na existenciu Steinerovho systému trojíc na n bodoch. Avšak
riešením Kirkmanovho problému je špeciálny Steinerov systém trojíc na 1 5 bodoch.
Záverom tejto časti poznamenajme, že blokový plán typu ( n , 2) sa nazýva kompletný
graf na n vrcholoch.
8 . 2 . Konečné roviny
Ak rozšírime Euklidovskú rovinu tak, že do každej priamky pridáme bod, ktorý pred­
stavuje smer tejto priamky, a pridáme jednu priamku spájajúcu všetky smery, tak
dostaneme projektívnu rovinu. V tejto rovine, podobne ako v klasickej Euklidovskej ,
každými dvoma rôznymi bodmi prechádza jediná priamka. Naviac, každé dve priamky
sa pretínaj ú v jedinom bode (týmto spoločným bodom priamok je buď ich priesečník,
ak sú rôznobežné, alebo ich smer, ak sú rovnobežné) . Projektívne roviny možno skúmať
aj na konečnom počte bodov.
Definícia. Nech je B systém podmnožín konečnej množiny V a t 2 2 . Podobne
ako v Euklidovskej rovine budeme prvky množiny V nazývať body a prvky B budeme
nazývať priamky . Usporiadanú dvojicu D = (V, B) nazývame konečná projektívna
rovina rádu t , ak platí
(p1 ) pre každú dvojicu bodov vb v2 E V, v1 =l v2 , existuje jediná priamka B E B
taká, že vb v2 E B ;
(p2) pre každé B1 . B2 E B, B 1 =l B2 , existuje jediný bod v taký, že v E B 1 a zároveň
v E B2 ;
(p3) existujú štyri body, z ktorých žiadne tri neležia na jednej priamke;
(p4) existuje priamka B' E B taká, že I B' I = t + l .
52
Veta 8 . 2 . Nech je D = (V, B) konečná projektívna rovina rádu t, t ;: 2 . Potom D
je blokový plán typu (t 2 +t+ l , t+l ) , čiže platí
(i)
(ii)
(iii)
(iv)
každá priamka pozostáva z t + l bodov;
cez každý bod prechádza t + l priam ok;
I V I = t2 + t + l ;
I B I = t2 + t + l .
Dôkaz. Dokážeme že D je blokový plán. Keďže vlastnosti (d3) a (pl ) sú totožné,
stačí dokázať tvrdenia (i) = (d2) a (iii) = (dl ) . Tvrdenia (ii) a (iv) sú potom dôsledkom
vety 8 . 1 .
Nech je B' priamka zaručená (p4) , ktorá má práve t + l bodov, a nech je B ľubovoľná
priamka. Naj prv ukážeme, že existuje bod u, ktorý neleží ani na B ' , ani na B . Ak jeden
zo štvorice bodov zaručených (p3) neleží ani na B' , ani na B , tak niet čo dokazovať.
Predpokladajme teda, že všetky štyri tieto body sú v B' U B. Potom dva z týchto bodov
ležia na B' a dva ležia na B. Nech u� , u2 E B' a u3 , u4 E B. Označme B1 priamku
určenú bodmi u1 a ua a B2 priamku určenú u2 a u4 . Priamky B1 a B2 sú rôzne od B ' a
B a podľa (p2) majú spoločný bod u. Bod u nemôže ležať na B ' , lebo potom by bodmi
u a u1 prechádzali dve priamky, čo protirečí (pl ) . Keďže z podobného dôvodu u nemôže
ležať ani na B, tak u � B' U B. Nech B' = {vL v� , . . . , v�+d a B = {v� , v2
vz } .
Ukážeme, ž e l = t + l . Podľa (p2) každá z priamok určených u a v� , i = l , 2 , . . . , t+ l ,
pretína B a každá z nich v inom bode podľa (pl ) . Preto t + l � l . Avšak analogicky
každá z priamok určených u a vi , i = l , 2, . . . , l , pretína B' a každá z nich v inom bode.
Preto l � t+l , čiže l = t+ l . Keďže B bola ľubovoľná priamka D, tak každá priamka
projektívnej roviny pozostáva z t+ l bodov.
Nech je u ľubovoľný bod neležiaci na priamke B' zaručenej (p4) . Podľa (p2) sa každá
priamka prechádzajúca bodom u pretína s B ' a podľa (pl ) každá v inom bode. Preto
bodom u prechádza práve t+ l priamok. Keďže každé dve z týchto priamok sa pretínajú
2
v bode u a už nikde inde, tak D má (t+l)t + l = t + t + l bodov, lebo každá priamka
obsahuje práve t+ l bodov podľa (i) . O
•
.
.
.
,
V úvode tejto časti sme naznačili, ako možno z klasickej afinnej Euklidovskej roviny
vytvoriť projektívnu rovinu. Teraz využijeme opačný postup.
Definícia. Konečná afinná rovina rádu t je štruktúra, ktorá vznikne z konečnej
projektívnej roviny rádu t vynechaním jednej (ľubovoľnej) priamky a všetkých bodov
tejto priamky. Priamku, ktorú sme vynechali nazývame nevlastná priamka roviny.
Veta 8 . 3 . Nech je D = (V, B) afinná rovina rádu t, t ;: 2 . Potom platí
(al ) každými dvoma rôznymi bodmi prechádza práve jedna priamka;
(a2) ak bod v neleží na priamke B, tak existuje jediná priamka Bv taká, že v
a Bv n B = 0;
(a3) exist ujú štyri body, z ktorých žiadne tri neležia n a jednej priamke;
(a4) exist uje priamka B' E B taká, že I B' I = t.
E
Bv
53
Dôkaz. Vlastnosť (al ) je dôsledkom definície, pretože je splnená v projektívnej rovi­
ne. Z projektívnej roviny sme síce vynechali nevlastnú priamku, avšak aj všetky body,
ktoré na nej ležali.
Nech bod v neleží na priamke B. Označme B* priamku projektívnej roviny rádu t,
z ktorej vznikla B. Nech je s jediný bod projektívnej roviny, ktorý je spoločný pnamke
B* a nevlastnej priamke. Potom existuje jediná priamka B� prechádzajúca bodmi v a s .
Teda Bv = B� {s} je priamka afinnej roviny vyhovujúca (a2 ) . Sporom predpokladajme,
že existuje ďalšia priamka Bo vyhovujúca (a2) a označme Bô priamku projektívnej
roviny, z ktorej vznikla B0 . Keďže v projektívnej rovine sa každé dve priamky musia
pretnúť, tak Bô n B* = {s} , čiže bodmi s a v boli v projektívnej rovine určené dve rôzne
priamky B� a Bô , čo protirečí (pl ) .
Nech je s ľubovoľný bod nevlastnej priamky a nech sú B i a B2 dve rôzne vlastné
priamky projektívnej roviny prechádzajúce s. Podľa vety 8.2 takéto priamky existujú,
keďže t � 2. Potom sú B1 = Bi { s} a B2 = Bi - { s} priamky afinnej roviny a ľubovoľné
dva body B1 spolu s ľubovoľnými dvoma bodmi B2 tvoria štvoricu, vyhovujúcu (a3) .
Tvrdenie (a4) je dôsledkom definície a platí pre každú priamku. O
Č asto sa afinná rovina definuje pomocou vlastností (al) - (a4) . Dokážte, že štruk­
túru spfňajúcu tieto vlastnosti možno doplniť pridaním jednej " nevlastnej" priamky, na
ktorej leží t+l bodov, na projektívnu rovinu.
Nasledujúca veta je dôsledkom definície afinnej roviny, avšak možno ju dokázať aj
pomocou vety 8.3.
Veta 8 . 4 . Nech j e D = (V, B) konečná aflnná rovina rádu t, t
blokový plán typu (t 2 , t) , čiže platí
(i)
(ii)
(iii)
(iv)
>
2 . Potom D je
každá priamka pozostáva z t bodov;
cez každý bod prechádza t + l priamok;
I V l = t2 ;
I B I = t2 + t .
Teraz, keď už vieme, aké vlastnosti majú projektívne a afinné roviny, môžeme nejaké
zostrojiť. Nech je lF konečné pole s t prvkami. Potom t je mocninou prvočísla, čiže t = pq
pre vhodné prvočíslo p a kladné prirodzené q . Ak q = l , tak lF je jednoducho (Zp, + , ·).
Avšak ak q > l , tak lF je pole, ktorého prvkami sú všetky polynómy stupňa menšieho
ako q nad Zp. Sčítanie a násobenie sú obyčajné sčítanie a násobenie polynómov nad Zp,
avšak násobenie modulo f (x) , kde f (x) je nejaký ireducibilný polynóm stupňa q nad
Zp.
Zostrojme afinnú rovinu AP(lF) nad poľom lF nasledovne. Body AP(lF) tvoria usporia­
dané dvojice ( a , b) prvkov poľa lF a priamky sú množiny bodov vyhovujúcich lineárnym
rovniciam ex+ dy + e = O, pričom (e, d) =/= (0, O) . (Podobne ako v klasickej rovine za x
dosadzujeme prvú a za y druhú súradnicu bodu.) Je zrejmé, že rovnice ex + dy + e = O
a (lc)x + (ld)y + (le) = O určujú tie isté priamky ak l =/= O. Ak d = O, tak po vynásobení
rovnice výrazom e- 1 dostávame tvar x = e' a ak d =/= O, tak po vynásobení tejto rovnice
výrazom d- 1 dostávame tvar y = e'x + e' . Každú priamku teda môžeme reprezentovať
54
buď ako rovnicu x = e', alebo y = c'x + e' . Dokážte, že AP(lF) je blokový plán typu ( t 2 , t)
a potom nahliadnite, že AP(lF) vyhovuje vete 8.3. Na obrázku 6 je znázornená afinná
rovina AP(Z2) a na obrázku 7 tá istá rovina inak nakreslená. Priamky sú len dvojice
bodov, ktoré sú však spojené čiarou kvôli jednoduchšej identifikácii týchto priamok.
Na obrázku 8 je znázornená projektívna rovina PP(Z2) , ktorú dostaneme z AP(Z 2 )
pridaním všetkých smerov a nevlastnej priamky. Projektívna rovina PP(Z2) sa nazýva
Fanova rovina.
x=O
x=1
y=x
y=x+ 1
Obrázok 6
( 1 ,0 )
( 0,0 )
Obrázok 7
Obrázok
S
Sú známe aj iné afinné roviny ako AP(lF) , avšak doposiaľ sú známe len také afinné
roviny, ktorých rád je mocninou prvočísla. Už dávnejšie sa vie, že neexistuje afinná
(a teda ani projektívna) rovina rádu 6. V roku 1991 Clement W. H. Lam s využitím
počítača dokázal, že neexistuje ani afinná rovina rádu 10.
Cvičenia
Cvičenie 8 . 1 . Pre aké hodnoty n existuje kompletný graf na n vrcholoch?
Cvičenie 8 . 2 . Pre aké hodnoty n môže existovať Steinerov systém trojíc?
Cvičenie 8 . 3 . Zostrojte Steinerov systém trojíc na 7, respektíve na 9 vrcholoch.
Cvičenie 8 .4. Nech je B systém podmnožín konečnej množiny V a nech D = ( V, B)
sp fňa vlastnosti (al ) , (a2) , (a3) a (a4) z vety 8.3. Dokážte, že D je blokový plán typu
(t 2 , t ) , kde t je počet bodov priamky B' E B zaručenej (a4) .
Cvičenie 8 . 5 . Nech je B systém podmnožín konečnej množiny V a nech D = ( V, B)
sp fňa vlastnosti (al ) , (a2) , (a3) a (a4) z vety 8.3. Pomocou cvičenia 8.4 dokážte, že
D možno doplniť pridaním jedného bodu do každej množiny B E B a pridaním jednej
množiny do B na konečnú projektívnu rovinu.
Cvičenie 8 . 6 . Dokážte, že ak je lF konečné pole s t prvkami, tak AP(lF) je afinná
rovina rádu t .
55
Cvičenie 8 . 7. Zostrojte AP(Z3) a PP(Z3) .
Cvičenie 8 . 8 . V hazardnej hre hráči hádajú pomocov tiketov 5 čísel z množiny
{ 1 , 2 , . . . , 25} . Bankár náhodne vytiahne dve čísla z tejto množiny, pričom vyhrá len ten
hráč, ktorý má v pätici čísel na tikete obidve vytiahnuté čísla. Kolko minimálne tiketov
musí vyplniť hráč, aby mal istotu, že vyhrá? Akú štruktúru tvorí rozpis takýchto tiketov?
Zostrojte aspoň jeden takýto rozpis.
Cvičenie 8 . 9 . Polynóm x 2 + x + l je ireducibilný v Z2. Pomocou tohoto polynómu
zostrojte pole so štyrmi prvkami a následne afinnú rovinu rádu 4.
56
9 . PRECHÁDZKY V GRAFO CH
9 . 1 . Grafy
Definícia. Nech je E systém dvojprvkových podmnožín konečnej množiny V. Us­
poriadanú dvojicu G = (V, E) nazývame graf. Prvky množiny V nazývame vrcholy a
prvky množiny E nazývame hrany grafu G.
V predošlej kapitole sme sa stretli s kompletným grafom na n vrcholoch, ktorý oz­
načujeme Kn . Tento graf obsahuje všetky možné hrany, teda má (�) hrán.
Grafy možno v rovine znázorniť tak, že vrcholy budú predstavovať krúžky, pričom
dvojicu krúžkov spojíme úsečkou, respektíve oblúkom, práve vtedy, keď odpovedajúca
dvojica vrcholov tvorí hranu grafu. (Samozrejme, príslušná krivka odpovedajúca hrane
už neprechádza žiadnymi ďalšími vrcholmi. ) Na obrázku 9 uvádzame niekolko príkladov
grafov. Všimnite si, že prvé dva obrázky sú len rôzne nakreslenia rovnakého grafu.
Obrázok 9
(V, E) graf, v E V a e E E. Ak sa v hrane e vyskytuje
Definícia. Nech je G
vrchol v , tak v je susedný s hranou e a hrana e je susedná s vrcholom v . Ak je hrana
e susedná s vrcholmi u a v , tak túto hranu zapisujeme e = ( u , v ) . Počet hrán grafu
susedných s vrcholom v nazývame stupeň vrchola v . Ak majú všetky vrcholy grafu G
rovnaký stupeň k , tak G je pravidelný graf stupňa k .
=
Prvé dva grafy na obrázku 9 s ú pravidelné grafy stupňa 3 a tretí graf m á vrcholy
stupňov l , 2 a 4.
57
Veta 9 . 1. V každom grafe sa súčet stupňov všetkých vrcholov rovná dvojnásobku
počtu hrán tohoto grafu a párny počet vrcholov grafu má nepárny stupeň.
Dôkaz. Spočítajme počet usporiadaných dvojíc [v , e ] , kde v je vrchol a e je hrana
grafu, pričom v je susedný s e. Keďže každá hrana je susedná s dvoma vrcholrr; i, tak
takýchto dvojíc je 2m, kde m je počet hrán grafu. Na druhej strane, každý vrchol je
susedný s tolkými hranami, aký má stupeň. Ak sú v1 , v 2 , . . . , Vn všetky vrcholy grafu a
ich stupne sú po rade d1 , d2 , . . . , dn , tak podľa predošlého platí
d1 + d2 +
·
·
·
+ dn
=
2m,
čím sme dokázali prvé tvrdenie vety. Keďže súčet stupňov všetkých vrcholov je párne
číslo, tak počet vrcholov nepárneho stupňa musí byť párny. D
Definícia. Nech je G = (V, E) graf. Postupnosť ( vo , e1 , v1 . e 2 , v2 , . . . , ek , vk ) na­
zývame sled ak vo , v1 . . . . , Vk E V, e 1 , e2 , . . . , ek E E a ei = ( vi- l • vi ) pre každé
i = l , 2 , . . . , k . Sled, v ktorom sú všetky hrany navzájom rôzne nazývame ťah a sled,
v ktorom sú dokonca všetky vrcholy navzájom rôzne nazývame cesta. U zavretý sled
je taký sled, v ktorom je prvý vrchol zhodný s posledným a podobne, uzavretý ťah
je taký ťah, v ktorom je prvý vrchol zhodný s posledným. Kružnica je uzavretý ťah,
v ktorom sú všetky dvojice vrcholov, s výnimkou prvého a posledného, navzájom rôzne.
Pod d fžkou sledu, ťahu, cesty, či kružnice budeme vždy rozumieť počet hrán (včí­
tane opakovania) tohoto sledu, ťahu, cesty, či kružnice. Sled ( vo , e1 , v1 . e2 , v 2 , . . . , ek , vk )
budeme často kvôli stručnosti zapisovať v tvare ( vo , v b v 2 , . . . , vk ) .
Veta 9 . 2 . Ak graf obsahuje uzavretý sled nepárnej dfžky, tak obsahuje aj kružnicu
nepárnej dfžky.
Dôkaz. Dokážeme, že ak má uzavretý sled v grafe nepárnu dfžku, tak časť tohoto
sledu tvorí kružnicu nepárnej dfžky. Tvrdenie dokážeme indukciou vzhľadom na počet
hrán (včítane opakovania) sledu.
l o Keďže neexistuje uzavretý sled d fžky l (graf neobsahuje slučky) , tak najkratší
uzavretý sled nepárnej d fžky môže mať d fžku 3. Avšak v tomto prípade musia byť
všetky vrcholy tohoto sledu navzájom rôzne, s výnimkou prvého a posledného, teda
tento sled tvorí kružnicu.
2° Nech má uzavretý sled C = ( vo , v1 7
, Vk- l ! vo ) nepárnu dfžku k, pričom tvrdenie
platí pre všetky sledy menšej nepárnej d fžky. Ak sú všetky vrcholy C, s výnimkou prvého
a posledného, navzájom rôzne, tak sled C tvorí kružnicu. Predpokladajme preto, že
existuje vrchol, povedzme Vi , ktorý sa v slede C vyskytuje dvakrát (analogicky možno
postupovať, ak sa prvý vrchol vyskytuje v slede trikrát) . Teda
.
C
=
•
•
( vo , v1 , . . . , Vi- b vi , Vi + b . . . , Vj l . Vi , I Vj + b . . . , Vk - l . vo ) .
f
Potom sú ( v o , v b . . . , vi- l , Vi , Vj +b . . . , vk- l ! vo ) a ( vi , vi+b . . . , Vj - l , vi ) uzavreté sledy
menšej dfžky ako k . Je zrejmé, že jeden z týchto sledov má nepárnu dfžku a podľa
indukčného predpokladu časť tohoto sledu tvorí kružnicu nepárnej dfžky. D
58
Definícia. Graf je súvislý, ak pre každú dvojicu jeho vrcholov u a v existuje v tomto
grafe cesta začínajúca vrcholom u a končiaca vrcholom v. Ak graf nie je súvislý, tak
najväčšie súvislé časti grafu nazývame komponenty súvislosti.
Overte, že všetky tri grafy na obrázku 9 sú súvislé.
9 . 2 . Eulerovské ťahy
Mesto Konigsberg, teraz Kaliningrad, sa v 1 8-tom storočí rozprestieralo na brehoch
a dvoch ostrovoch rieky Pregoly. Tieto časti mesta boli pospájané 7 mostami, ako je
znázornené na obrázku 10. V tej dobe nebývalo bežné, aby boli časti mesta pospájené
až 7 mostami a obyvatelia Konigsbergu boli na tieto svoje mosty aj patrične hrdí.
V nedeľu sa Konigsbergčania obyčajne prechádzali po meste a objavil sa problém, či
je možné naplánovať takú prechádzku mestom, počas ktorej by prešli každým mostom
práve raz.
Leonhard Euler nahradil všetky časti súše vrcholmi a všetky mosty hranami spájajú­
cimi tieto vrcholy. Takto síce nedostal graf v zmysle našej definície, ale graf s násobnými
hranami, pozri obrázok l l . Avšak úlohu týmto spôsobom previedol na problém nájsť
taký ťah v grafe, ktorý by obsahoval každú hranu práve raz.
a
c
Obrázok
10
Obrázok
ll
Definícia. Uzavretý Eulerovský ťah je taký uzavretý ťah, ktorý obsahuje každú
hranu grafu práve raz a otvorený Eulerovský ťah je taký ťah, ktorý obsahuje každú
hranu grafu práve raz, pričom prvý vrchol tohoto ťahu je rôzny od posledného.
Problém mesta Konigsberg Euler zovšeobecnil a v roku 1 736 dokázal nasledujúcu
vetu, ktorá sa považuje za prvú vetu teórie grafov.
Veta 9 . 3 {Eulerova veta) . Súvislý graf má uzavretý Eulerovský ťah práve vtedy,
keď má všetky vrcholy párneho stupňa.
59
Dôkaz. Nech má graf G uzavretý Eulerovský ťah T. Prejdime sa pozdlž hrán ťahu
T. Ak do vrchola v prídeme kv krát pomocou kv rôznych hrán, tak z tohoto vrchola
musíme aj kv krát odísť pomocou ďalších kv rôznych hrán. To znamená, že vrchol v má
stupeň 2kv a teda stupeň každého vrchola grafu G je párny.
Teraz predpokladajme, že všetky vrcholy grafu G majú párny stupeň. Nech je v
ľubovoľný vrchol grafu G a nech je T najdlhší ťah začínajúci vo vrchole v . Predpokla­
dajme, že ťah T končí vo vrchole u, pričom u =/=- v . Potom je vrchol u susedný s nepárnym
počtom hrán ťahu T a keďže stupeň u je párny, tak aspoň jedna hrana susedná s u nepatrí
ťahu T. Č iže T možno predfžiť, čo je spor s predpokladom. To znamená, že ťah T nutne
končí vo vrchole v .
Ak ťah T obsahuje všetky hrany grafu G, tak je Eulerovský. Predpokladajme preto,
že T neobsahuje všetky hrany grafu G. Keďže G je súvislý, tak existuje taká hrana
e grafu G, ktorá nepatrí ťahu T, ale susedí s vrcholom, povedzme v ' , ktorý patrí T.
Vynechajme z G všetky hrany ťahu T. Takto dostaneme graf, ktorý môže byť nesúvislý.
Označme G' ten komponent súvislosti tohoto grafu, ktorý obsahuje vrchol v ' . Keďže
všetky vrcholy grafu G ' majú párny stupeň, tak v G ' existuje uzavretý ťah, povedzme
( v , v 1 , v 2 , . . . , vk , , v ' ) , zacinaJUCl hranou e. po t om t'ah T = ( v , vi , v2 , . . . , vi , v , vi +I ,
Vi +2 , . . . , Vk , v ) možno predfžiť na ťah
l
l
l
l
l
V '
•
,
•
ktorý je dlhší ako T, lebo okrem všetkých hrán ťahu T obsahuje aj hranu e. To je však
spor s predpokladom, že T je najdlhší ťah grafu G začínajúci vo vrchole v. To znamená,
že najdlhší ťah začínajúci vo v obsahuje všetky hrany grafu G, a teda tento ťah je
Eulerovský. O
Všimnite si, že v predošlom dôkaze sme nikde nevyužili, že graf G nemá násobné
hrany. Teda Eulerova veta platí aj pre také grafy, ktoré násobné hrany majú. Eulerova
veta má nasledujúci dôsledok, podľa ktorého neexistuje prechádzka mestom Konigsberg,
obsahujúca každý most práve raz.
Dôsledok. Súvislý graf má otvorený Eulerovský ťah práve vtedy, keď má práve dva
vrcholy nepárneho stupňa.
Dôkaz. Ak má graf otvorený Eulerovský ťah, tak je zrejmé, že všetky jeho vrcholy,
s výnimkou prvého a posledného vrchola otvoreného Eulerovského ťahu, sú párneho
stupňa. Teraz naopak predpokladajme, že súvislý graf G má len dva vrcholy, povedzme
u a v, nepárneho stupňa. Označme G' graf, respektíve graf Š násobnými hranami, ktorý
vznikne z G pridaním hrany (u, v ) . Graf G ' je súvislý a každý jeho vrchol má párny
stupeň. Preto má podľa Eulerovej vety uzavretý Eulerovský ťah, pričom vynechaním
hrany (u, v ) z tohoto ťahu dostaneme otvorený Eulerovský ťah grafu G. O
60
9 . 3 . Hamiltonovské kružnice
V roku 1 857 William R. Hamilton zostrojil matematický hlavolam, ktorého cieľom
bolo nájsť takú uzavretú prechádzku po hranách pravidelného dvanásťstena, ktorá by
obsahovala každý vrchol práve raz. Ak zabudneme na plochy dvanásťstena a nakreslíme
jeho vrcholy a hrany v rovine, tak dostaneme graf nakreslený na obrázku 1 2 .
Obrázok 12
Definícia. Hamiltonovská kružnica je taká kružnica, ktorá obsahuje všetky vr­
choly grafu a Hamiltonovská cesta je cesta, obsahujúca všetky vrcholy grafu.
Teda riešením Hamiltonovho hlavolamu je Hamiltonovská kružnica. Jedna takáto
kružnica je na obrázku 1 2 vyznačená tučnými hranami.
Zistiť, či má graf uzavretý Eulerovský ťah, je ľahký problém, lebo stačí zistiť súvislosť
grafu a paritu stupňov všetkých jeho vrcholov. Je prekvapujúce, že analogický problém
pre Hamiltonovské kružnice je ťažký. Tento problém patrí do skupiny takzvaných NP­
úplných problémov. Poznáme však veľmi veľa podmienok, ktorých splnenie vynucuje
v grafe existenciu Hamiltonovskej kružnice. Jednu z najznámejších postačujúcich pod­
mienok tohoto typu dokázal O. Ore v roku 1 960.
Veta 9.4 ( Oreho veta ) . Nech je G graf na n � 3 vrcholoch . Ak je súčet stupňov
každých dvoch vrcholov, ktoré nie sú spojené hranou, aspoň n, tak G má Hamiltonovskú
kružnicu.
Dôkaz. Nech je G graf sp fňajúci podmienky vety. Najprv dokážeme, že graf G je
súvislý. Sporom predpokladajme, že G má aspoň dva komponenty súvislosti. Nech je VI
vrchol z jedného komponentu súvislosti a v2 vrchol z iného komponentu súvislosti grafu
G. Vrcholy VI a v 2 nemôžu byť spojené hranou a teda podľa predpokladov vety je súčet
stupňov týchto vrcholov aspoň n. Teda z dvojprvkovej podmnožiny množiny vrcholov
vedie do ostatných n-2 vrcholov aspoň n hrán, čiže podľa Dirichletovho princípu aspoň
dve hrany vedú do ro.vnakého vrchola, povedzme w . Avšak potom sú (vb w ) aj (v2 , w )
61
hrany grafu G, čo je v spore s predpokladom, že v1 a v 2 patria do rôznych komponentov
súvislosti grafu G. Teda G je súvislý graf.
Teraz predpokladajme, že ( v1 , v2 , . . . , vk ) je najdlhšia cesta v grafe G. Dokážeme,
že existuje kružnica obsahujúca všetky vrcholy tejto cesty. Ak sú v1 a Vk spojené hra­
nou, tak niet čo dokazovať. Predpokladajme preto, že v1 a Vk nie sú spojené hranou.
Keďže ( v 1 , v 2 , . . . , vk ) je najdlhšia cesta v grafe G, tak z v1 aj z vk môžu viesť hrany iba
do vrcholov v 2 , VJ , . . . , Vk l · Rozdeľme všetky možné hrany susedné s v1 a vk do k-l
skupín { ( v 1 , v 2 ) } , { ( vl . VJ ) , ( v 2 , vk ) } , { ( vl . v4 ) , ( vJ , vk ) } , . . . , { ( vl . Vi ) , ( vi l . vk ) } , . . .
. . . , { ( v l . Vk_ l ) , ( vk 2 , vk ) } , { ( vk l , vk ) } . Všetky tieto skupiny, s výnimkou prvej a
poslednej , sú dvojprvkové. Vrcholy v1 a Vk nie sú spojené hranou, a preto je súčet
ich stupňov aspoň n. Keďže skupín hrán je k - 1 � n - 1 < n, tak podľa Dirichletovho
princípu sú v aspoň jednej skupine dve hrany grafu G. Nech sú týmito hranami ( v 1 , vi )
a ( vi l , vk ) pre nejaké i E {3, 4 , . . . , k- 1 } . Potom je
kružnica obsahujúca všetky vrcholy najdlhšej cesty ( v1 , v2 , . . . , vk ) grafu G, pozri ob­
rázok 13.
Ak k = n, tak tvrdenie vety je dokázané. Predpokladajme preto, že k < n . Keďže G je
súvislý graf, tak existuje vrchol u grafu G, u rt { v1 1 v2 , . . . , vk } , ktorý je spojený hranou
s nejakým vrcholom kružnice C. Potom však existuje cesta na vrcholoch v1 . v 2 , , Vk , u
(samozrejme nie nutne v tomto poradí) , čo je spor s predpokladom, že ( v1 , v 2 , . . . , vk )
je najdlhšia cesta v grafe G. O
•
•
•
Obrázok 1 3
Dôsledkom Oreho vety je tvrdenie, ktoré dokázal G. Dirac v roku 1952.
Dôsledok. Nech je G graf na n � 3 vrcholoch. Ak má každý vrchol grafu G stupeň
aspoň � , tak G má Hamiltonovskú kružnicu.
62
Cvičenia
Cvičenie 9 . 1 . Dokážte, že ak sú dva vrcholy grafu spojené sledom, tak sú spojené
aj cestou.
Cvičenie 9 . 2 . Ukážte, že ak graf obsahuje uzavretý sled párnej dfžky, tak ešte ne­
musí obsahovať kružnicu.
Cvičenie 9 . 3 . Dokážte, že ak sú stupne všetkých vrcholov grafu aspoň 2, tak graf
obsahuje kružnicu.
1
Cvičenie 9 .4. Dokážte, že graf na n vrcholoch, ktorý má viac, ako ( n 2 ) hrán, je
1
súvisi�. Ukážte, že ( n 2 ) hrán nestačí.
Cvičenie 9 . 5 . Pre aké n má kompletný graf na n vrcholoch Kn Eulerovský ťah?
Cvičenie 9 . 6 . Nech je G graf, ktorý má všetky vrcholy párneho stupňa, s výnimkou
vrcholov u a v , ktorých stupne sú nepárne. Dokážte, že graf G je súvislý práve vtedy,
keď je súvislý graf (respektíve graf s násobnými hranami) G ' , ktorý vznikne z grafu G
pridaním hrany ( u , v ) .
Cvičenie 9. 7. Dokážte, že graf na obrázku 14 nemá Hamiltonovskú kružnicu.
Obrázok 14
Obrázok 1 5
Cvičenie 9 . 8 . Dokážte, ž e Petersenov graf, ktorý je nakreslený n a obrázku 1 5 , nemá
Hamiltonovskú kružnicu.
1
Cvičenie 9 . 9 . Dokážte, že ak má graf n vrcholov a viac ako ( n 2 ) + l hrán, tak má
Hamiltonovskú kružnicu. Ukážte, že ( n 2 1 ) + l hrán nestačí.
Cvičenie 9 . 1 0 . Kolko rôznych Hamiltonovských kružníc má kompletný graf na n
vrcholoch K n ?
Cvičenie 9 . 1 1 . Nech je Wn graf, ktorý vznikne z pravidelného (n- 1 )-bokého ihlanu,
ak zabudneme na plochy tohoto ihlanu. Kolko rôznych Hamiltonovských kružníc má
Wn?
Cvičenie 9 . 1 2 . Nech je Hn graf, ktorý vznikne z pravidelného I -bokého hranola,
ak zabudneme na plochy tohoto hranola. Kolko rôznych Hamiltonovských kružníc má
Hn ?
63
10.
ROVINNOSŤ A FAREBNOSŤ GRAFOV
10. 1 .
Stromy
Definícia. Strom je súvislý graf, ktorý nemá kružnice.
Príklad
l.
Na obrázku 1 6 sú nakreslené všetky možné stromy na piatich vrcholoch.
><
Obrázok 1 6
Veta 10. 1 . Strom na n vrcholoch má n - l hrán.
Dôkaz. Označme n počet vrcholov stromu. Tvrdenie dokážeme indukciou podľa n.
l o Ak n = l , tak jediný graf na l vrchole nemá žiadnu hranu.
2° Nech je G strom na n vrcholoch a nech tvrdenie platí pre každý strom, ktorý
má menej ako n vrcholov. Keďže n > l a strom G je súvislý graf, tak má hranu,
povedzme (u, v ) . Nech je H graf, ktorý vznikne z G vynechaním hrany (u, v ) . Keby v H
existovala cesta z u do v , tak táto cesta by spolu s hranou (u, v ) tvorila kružnicu v G,
čo by bol spor s predpokladom, že G je strom. Preto je H nesúvislý graf. Keďže hrana
(u, v ) má len dva konce, tak H má práve dva komponenty súvislosti. Označme tieto
komponenty H1 a H2 . Strom G neobsahoval kružnice, a preto sú H1 a H2 súvislé grafy
bez kružníc, teda stromy. Nech má strom H1 n1 vrcholov a H2 nech má n2 vrcholov.
Potom platí n1 + n2 = n. Keďže n1 < n aj n2 < n, tak podľa indukčného predpokladu
má H1 n1 - l hrán a H2 má n2 - l hrán. Č iže spolu s hranou (u, v ) má strom G práve
(n1 - l ) + (n2 - l ) + l = n - l hrán. O
Dôsledok. Súvislý graf na n vrcholoch má aspoň n - 1 hrán, pričom ak má práve
n - 1 hrán, tak je stromom.
Dôkaz. Ak je graf stromom, tak tvrdenie platí podľa vety 10. 1 . Predpokladajme
preto, že G je súvislý graf na n vrcholoch, ktorý nie je stromom. To znamená, že G má
kružnicu. Je zrejmé, že vynechaním ľubovoľnej hrany z kružnice grafu G sa súvislosť
tohoto grafu neporuší. Označme G' graf, ktorý vznikne z grafu G vynechaním jednej
64
hrany, povedzme e, z ľubovoľnej kružnice grafu G. Ak má aj G' kružnicu, tak opäť
vynechajme jednu hranu z ľubovoľnej kružnice grafu G ' a tento proces opakujme až
dovtedy, kým z grafu G nezostane graf G* , ktorý neobsahuje kružnice. Graf G* je súvislý
graf bez kružníc, čiže je stromom. Podľa vety 10.1 má G* práve n - 1 hrán a keďže graf
G obsahuje okrem všetkých hrán stromu G* aj hranu e (a možno ešte niekolko ďalších
hrán) , tak G má aspoň n hrán. To znamená, že ak graf nie je stromom, tak má aspoň
n hrán, čiže ak má práve n 1 hrán, tak je stromom.
O
1 0 . 2 . Rovinné grafy
Definícia. Rovinné nakreslenie grafu je také nakreslenie tohoto grafu v rovine, pri
ktorom sa jeho hrany navzájom nepretínajú. Graf je rovinný ak má rovinné nakreslenie.
Predošlá definícia je trošku nepresná, pretože sme nezadefinovali, čo je to nakreslenie
grafu v rovine a ani čo to znamená, že sa hrany navzájom nepretínajú. Avšak intuitívne
je zrejmé, aký graf môže byť rovinný.
Príklad 2 . Na obrázku 17 je znázornené rovinné nakreslenie rovinného grafu. Toto
nakreslenie ohraničuje v rovine tri oblasti označené
sú po rade 3, 5 a 10.
a,
b a c, pričom d fžky týchto oblastí
Obrázok 1 7
Poznamenajme, ž e prvý graf nakreslený na obrázku 9 síce je rovinný, ale až druhý
obrázok predstavuje jeho rovinné nakreslenie.
Veta 1 0 . 2 (Eulerova formula) . Nech je G súvislý rovinný graf, ktorého hrany
v rovinnom nakreslení ohraničujú r oblastí. Ak má graf G n vrcholov a m hrán, tak
platí
n + r - m = 2.
65
Dôkaz. Nech je n pevne zvolené prirodzené číslo. Vetu dokážeme indukciou podľa
počtu hrán súvislého rovinného grafu na n vrcholoch.
1° Podľa dôsledku vety 10. 1 má každý súvislý graf na n vrcholoch aspoň n - 1 hrán,
pričom n - 1 hrán má len strom. Teda prvý krok indukcie urobíme pre stromy. Keďže
strom nemá kružnice, tak je rovinným grafom, pričom rovinné nakreslenie stromu ohra­
ničuje v rovine jedinú (vonkajšiu) oblasť. Podľa vety 1 0 . 1 má strom n - 1 hrán, a preto
n + l - ( n - 1 ) = 2, čiže pre stromy Eulerova formula platí.
2° Nech je G súvislý rovinný graf, ktorý má m > n- 1 hrán, pričom tvrdenie platí pre
rovinné grafy, ktoré majú m- 1 hrán. Nech má rovinné nakreslenie grafu G r oblastí.
Podľa vety 10. 1 G nie je stromom, a preto má kružnicu. Nech je ( u , v ) ľubovoľná hrana
tejto kružnice. Táto hrana leží na hranici dvoch oblastí. Jedna oblasť je vnútri a druhá
zvonka uvažovanej kružnice. Označme H graf, ktorý vznikne z grafu G vynechaním
hrany ( u , v ) . Graf H j e súvislý a rovinný. V tom rovinnom nakreslení grafu H, ktoré
vzniklo z rovinného nakreslenia grafu G, ohraničujú hrany H presne r - 1 oblastí, lebo
vynechaním hrany ( u , v ) vznikla z dvoch oblastí jedna. Keďže podľa indukčného pred­
pokladu pre graf H platí Eulerova formula, tak platí n + ( r - 1 ) - ( m- 1 ) = 2, čiže
n + r - m = 2. O
Nasledujúca veta je dôsledkom Eulerovej formuly.
Veta
10.3.
Každý rovinný graf obsahuje vrchol, ktorého stupeň je nanajvýš
5.
Dôkaz. Nech je G rovinný graf na n vrcholoch s m hranami. Graf G má podľa Eu­
lerovej formuly v každom rovinnom nakreslení m + 2 - n oblastí. Každá hrana sa vysky­
tuje na hranici oblasti dvakrát. Ak leží v kružnici, tak sa vyskytuje na hraniciach dvoch
rôznych oblastí a ak neleží v žiadnej kružnici, tak sa vyskytuje dvakrát na hranici jed­
nej oblasti. Preto sa súčet d fžok všetkých oblastí rovinného nakreslenia grafu rovná 2m.
Keďže každá oblasť je ohraničená aspoň tromi hranami, tak oblastí je nanajvýš
Teda m+2 - n � i m, čiže
(*)
m � 3n - 6.
Podľa vety 9 . 1 ak sú dt , d2 , . . . , dn stupne vrcholov Vt , v2 , . . . , Vn grafu G, tak platí
d1 + d2 +
+ dn = 2m.
Ak by boli všetky tieto stupne aspoň 6, tak by platilo 6n � 2m, čiže 3n � m, čo je
v spore s ( * ) . Preto v grafe G existuje vrchol, ktorého stupeň je nanajvýš 5 . O
·
10.3.
·
·
Farebnosť grafov
V tejto časti budem e farbiť vrcholy grafu.
Definícia. Zafarbenie vrcholov je dobré, ak majú každé dva vrcholy, ktoré sú spo­
jené hranou, rôznu farbu. Ak je možné dobre zafarbiť vrcholy grafu pri použití nanajvýš
k farieb, tak graf je k-farbitelhý.
66
Je zrejmé, že ak je graf k-farbiteľný, tak je aj (k+ 1 )-farbiteľný. Akonáhle graf obsahuje
aspoň jednu hranu, tak na jeho dobré zafarbenie potrebujeme aspoň dve farby.
Definícia. Graf je párny (=bipartitný) , ak je 2-farbiteľný.
Príklad 3 . Graf nakreslený na obrázku 18 je párny, pretože jeho vrcholy možno
dobre zafarbiť 2 farbami (bielou a čiernou) tak, ako je znázornené na obrázku 18.
Obrázok 1 8
Veta 1 0 . 4 . Graf je párny práve vtedy, keď nemá kružnicu nepárnej dfžky.
Dôkaz. Predpokladajme, že graf obsahuje.. kružnicu C nepárnej dfžky a zafarbime
vrcholy tohoto grafu dvoma farbami. Keďže kružnica C má nepárnu dfžku, tak jednou
z farieb je zafarbených viac vrcholov tejto kružnice, ako druhou farbou. Avšak potom
sú touto farbou zafarbené aj niektoré dva susedné vrcholy C, čiže farbenie nie je dobré.
Preto žiaden graf obsahujúci kružnicu nepárnej dfžky nemôže byť párny. (V predošlej
úvahe sme využili Dirichletov princíp, zrekonštrujte si jeho využitie podrobne.)
Teraz naopak predpokladajme, že graf G = (V, E) neobsahuje kružnicu nepárnej
dfžky. Ukážeme, že vrcholy grafu G možno dobre zafarbiť dvoma farbami. Bez újmy na
všeobecnosti môžeme predpokladať, že G je súvislý graf, pretože v opačnom prípade
zafarbíme každý komponent súvislosti samostatne. Nech je v vrchol grafu G. Označme
X množinu tých vrcholov x E V, pre ktoré existuje v - x cesta nepárnej dfžky v G a Y
označme množinu tých vrcholov y E V, pre ktoré existuje v - y cesta párnej dfžky v G.
Keďže graf G je súvislý, tak X U Y = V. Ak existuje vrchol u E X n Y , tak existuje nejaká
v - u cesta nepárnej d fžky a iná v - u cesta párnej dfžky. Tieto cesty spolu tvoria uzavretý
sled nepárnej dfžky, čiže graf G musí podľa vety 9.2 obsahovať kružnicu nepárnej d fžky,
čo je spor s predpokladom. To znamená, že systém {X, Y} tvorí rozklad V . Ak existujú
dva vrcholy ub u2 E X, u1 =l= u2 , ktoré sú spojené hranou ( u1 , u 2 ) , tak existujú v - u1
a v - u2 cesty nepárnej dfžky a tieto cesty spolu s hranou ( u1 , u 2 ) tvoria uzavretý sled
nepárnej dfžky, čo je podľa vety 9.2 opäť spor s predpokladom. Analogicky ak existujú
dva vrcholy u1 , u2 E Y, u1 =l= u 2 , ktoré sú spojené hranou ( u1 , u 2 ) , tak existujú v - u1
a v - u 2 cesty párnej d fžky a tieto cesty spolu s hranou ( u1 , u2 ) tvoria uzavretý sled
67
nepárnej d!žky, čo je podľa vety 9 . 2 spor s predpokladom. To znamená, že ak zafarbíme
všetky vrcholy množiny X prvou farbou a všetky vrcholy množiny Y druhou farbou,
tak dobre zafarbíme všetky vrcholy grafu G. O
Nech je G (V, E) párny graf. Zvoľme jedno dobré zafarbenie grafu G dvomi farbami
a pri tomto zafarbení označme X množinu vrcholov jednej a Y množinu vrcholov druhej
farby. Potom {X, Y} tvorí rozklad množiny vrcholov grafu G, pričom žiadna dvojica
vrcholov z jednej triedy rozkladu nie je spojená hranou. Ak je G súvislý graf, tak tento
rozklad je určený jednoznačne (pozri dôkaz vety 10.4) , a preto budeme párny graf často
zapisovať v tvare G (X, Y; E) .
=
=
Definícia. Kompletný bipartitný graf Km ,n je párny graf Km, n = (X, Y; E) , kde
I X I = m, I Y I
n a každý vrchol z množiny X je spojený hranou s každým vrcholom
z množiny Y .
=
Všimnite si, že kompletný bipartitný graf Kn,n má 2n vrcholov a n 2 hrán. Stupeň
každého vrchola je n, avšak tento graf je 2-farbiteľný (porovnajte s cvičením 10.8) .
Definícia. Nech je G = (V, E) graf a nech je S podmnožina množiny vrcholov
grafu G. Podgraf grafu G indukovaný množinou S je taký graf H = (S, F) , ktorého
množina vrcholov je S, pričom dva vrcholy sú spojené hranou v H práve vtedy, ak sú
tieto vrcholy spojené hranou v grafe G.
V ďalšom sa budeme zaoberať rovinnými grafmi. Majme v rovine nakreslenú mapu
štátov, ktoré sú všetky " súvislé" . Teda žiaden štát nemá na inom území enklávy ako
je napríklad Gibraltar. Politická mapa je také zafarbenie štátov farbami, pri ktorom
dostanú štáty, ktoré susedia hranicou nenulovej d!žky, rôzne farby. Zaujímavé je zis­
tiť, aký najmenší počet farieb potrebujeme na korektné zafarbenie politickej mapy. Ak
nahradíme všetky štáty vrcholmi, ktoré spojíme hranou práve vtedy, keď tieto štáty
susedia hranicou nenulovej d!žky, tak dostaneme rovinný graf. C iže úlohu sme previedli
na problém, kolko farieb stačí na dobré zafarbenie rovinného grafu. Nasledujúcu vetu
dokázal P. J. Heawood v roku 1890.
Veta 1 0 . 5 . Každý rovinný graf je 5-farbiteľný.
Dôkaz. Dôkaz urobíme indukciou vzhľadom na počet n vrcholov grafu. Zjavne veta
platí pre rovinné grafy, ktoré majú nanajvýš 5 vrcholov. Predpokladajme preto, že G je
rovinný graf na n vrcholoch, n > 5 , pričom veta platí pre všetky rovinné grafy na n - 1
vrcholoch. Podľa vety 1 0 . 3 m á graf G vrchol v stupňa nanajvýš 5 . Nech je H graf, ktorý
vznikne z grafu G vynechaním vrchola v a všetkých hrán, ktoré sú susedné s v. (Teda
H je podgraf grafu G (V, E) indukovaný množinou V- { v } . ) Keďže G je rovinný graf,
tak je rovinný aj graf H. V ďalšom uvažujme rovinné nakreslenie grafu H, ktoré vznikne
z rovinného nakreslenia grafu G vynechaním vrchola v . Podľa indukčného predpokladu
je graf H dobre zafarbiteľný 5 farbami. Ak má vrchol v v grafe G stupeň nanajvýš 4,
=
68
tak existuje farba, ktorú nemá žiaden sused vrchola v pri dobrom zafarbení vrcholov
grafu H piatimi farbami. Touto farbou môžeme zafarbiť vrchol v, pričom takto získané
zafarbenie grafu G je dobré.
Predpokladajme teda, že stupeň vrchola v v grafe G je 5. Nech sú vb v2 , . . . , Vs vrcholy
susedné s v , pričom hrany vedúce z vrchola v k v1 , v2 , . . . , vs sa v rovinnom nakreslení
grafu G objavia práve v tomto poradí, ak sa prejdeme v rovine po malej kružnici okolo
vrchola v , pozri obrázok 19. Ak majú dva z vrcholov Vi , v2 , , vs rovnakú farbu pri
dobrom zafarbení grafu H piatimi farbami, tak opäť existuje farba, ktorou nie je zafar­
bený žiaden sused vrchola v a touto farbou môžeme vrchol v zafarbiť. Predpokladajme
preto, že všetky vrcholy vb v2 , , vs majú v dobrom zafarbení grafu H piatimi far­
bami navzájom rôzne farby. Naviac, označme l farbu, ktorou je zafarbený vrchol v1 ,
2 farbu, ktorou je zafarbený vrchol v2 ,
, až 5 farbu, ktorou je zafarbený vrchol Vs .
Prefarbením niektorých vrcholov grafu H ukážeme, že existuje také dobré zafarbenie
grafu H piatimi farbami, v ktorom majú dva z vrcholov v1 , v2 , . . . , Vs rovnakú farbu,
čím ukážeme, že G je 5-farbiteľný.
Nech je H1 , 3 podgraf grafu H indukovaný vrcholmi, ktoré majú farbu l , alebo 3.
Predpokladajme, že v1 a V3 patria do rôznych komponentov súvislosti grafu H1 , 3 . Za­
meňme farby vrcholov v tom komponente súvislosti grafu H1,3 , v ktorom je v1 . Teda
tým vrcholom, ktoré mali farbu l dáme farbu 3 a tým, ktoré mali farbu 3 dáme farbu
l . Ukážeme, že takto získané zafarbenie grafu H je dobré. Sporom predpokladajme,
že toto zafarbenie nie je dobré. Potom existuje hrana ( ub u2 ) grafu H, ktorej obidva
vrcholy sú pri novom zafarbení zafarbené rovnakou farbou. Pri novom zafarbení sme
však iba navzájom zamenili farby l a 3 v niektorých vrcholoch. Preto obidva vrcholy
u1 a u2 majú pri novom zafarbení farbu l , prípadne obidva majú farbu 3. To znamená,
že u1 a u2 museli patriť do rôznych komponentov súvislosti grafu H1 , 3 , čiže nemôžu byť
spojené hranou v H, čo je spor s predpokladom. Teda existuje dobré zafarbenie grafu
H, v ktorom majú vrcholy v1 a v3 rovnakú farbu, čiže G je 5-farbiteľný.
Zostáva nám rozobrať prípad, keď v1 a v 3 patria do jedného komponentu súvislosti
grafu H1 , 3 . V tomto prípade existuje v grafe H taká cesta z vrchola v1 do v 3 , ktorá
využíva len vrcholy farieb l a 3 (táto cesta je naznačená na obrázku 19) . Keďže H je
rovinný graf, tak nemôže existovať cesta z vrchola v2 do vrchola v4 , využívajúca len
vrcholy farieb 2 a 4. To znamená, že ak označíme H2 , 4 podgraf grafu H indukovaný
vrcholmi, ktoré majú farbu 2 , alebo 4, tak v2 a v4 patria do rôznych komponentov
súvislosti grafu H2 , 4 · Teda keď zameníme farby tých vrcholov grafu H2 , 4 , ktoré ležia
v komponente súvislosti obsahujúcom v 2 , tak dostaneme dobré zafarbenie grafu H pia­
timi farbami, v ktorom majú vrcholy v 2 a v4 rovnakú farbu. Č iže aj v tomto poslednom
prípade je graf G 5-farbiteľný. O
.
.
•
•
.
.
•
.
.
69
Vs
Obrázok 1 9
Ako sme mohli nahliadnúť, dôkaz tvrdenia, že každý rovinný graf je 5-farbiteľný, je
ľahký. Platí však silnejšie tvrdenie, známe ako 4CT (four colour theorem) , ktoré tvrdí,
že každý rovinný graf je 4-farbiteľný! Hypotéza, že každý rovinný graf je 4-farbiteľný,
bola snáď najznámejším otvoreným problémom v teórii grafov. V roku 1 976 K. Appel
a W. Haken oznámili, že pomocou počítača dokázali 4CT. Ich dôkaz bol pomerne ne­
prehľadný a dosť podstatným sa ukázal problém nezávislej verifikácie ich počítačových
programov. V roku 1 9 9 7 bol publikovaný odlišný dôkaz, ktorého autormi sú N. Robert­
son, D. Sanders, P. Seymour a R. Thomas. Tento dôkaz tiež využíva počítač, je však
oveľa prehľadnejší a akceptovateľnejší.
Cvičenia
Cvičenie 1 0. 1 . Pomocou Eulerovej formuly dokážte, že kompletný graf na 5 vr­
choloch Ks nie je rovinný.
Cvičenie 1 0 . 2 . Pomocou Eulerovej formuly dokážte, že kompletný bipartitný graf
K3 , 3 nie je rovinný.
Cvičenie 1 0 . 3 . Pomocou Eulerovej formuly dokážte, že Petersenov graf nie je ro­
vinný (pozri obrázok 15) .
Cvičenie 10.4. Určte najmenšie počty farieb nutných na dobré zafarbenie grafov
Platónovských telies: pravidelného štvorstena, kocky, osemstena, dvanásťstena a dvad­
saťstena.
Cvičenie 1 0 . 5 . Dokážte, že strom je párny graf.
Cvičenie 1 0 . 6 . Dokážte, že ak má graf jedinú kružnicu nepárnej dlžky, tak je 3farbiteľný.
Cvičenie 10.7. Môže mať párny graf na nepárnom počte vrcholov Hamiltonovskú
kružnicu? Pomocou tohoto pozorovania opätovne nahliadnite, že graf znázornený na
obrázku 14, respektíve 18, nemôže mať Hamiltonovskú kružnicu.
Cvičenie 10.8 {Brooksova veta ) . Dokážte, že ak je � maximálny stupeň vrchola
v grafe G, tak G je (�+1 )-farbiteľný.
70
Cvičenie 1 0 . 9 . Nájdite najmenšie k, pre ktoré je Petersenov graf k-farbiteľný.
Cvičenie 1 0 . 1 0 . Nech je Wn graf, ktorý vznikne z pravidelného (n- 1 )-bokého ih­
lanu, ak zabudneme na plochy tohoto ihlanu. Určte najmenšie k, pre ktoré je graf Wn
k-farbi teľný.
Cvičenie 10. 1 1 . Nech je Hn graf, ktorý vznikne z pravidelného � -bokého hranola,
ak zabudneme na plochy tohoto hranola. Určte najmenšie k, pre ktoré je graf Hn k­
farbiteľný.
71
ll.
11.1.
PÁRNE GRAFY
Párovania a transverzály
Definícia. Párovanie (matching) v grafe je taká množina hrán, z ktorých žiadne
dve nemajú spoločný vrchol. Hrany ľubovoľného párovania tvoria množinu navzájom
nezávislých hrán. Maximové párovanie je párovÉmie s najväčším počtom hrán a
kompletné párovanie v grafe na n vrcholoch je párovanie, ktoré má � hrán.
Poznamenajme, že každý graf má max:imové párovanie, avšak kompletné párovanie
mať nemusí.
Na obrázku 20 sú znázornené tri súvislé pravidelné grafy stupňa 3, všetky
na párnom počte vrcholov. Prvý graf má kompletné párovanie, dokonca množinu jeho
hrán možno rozložiť na tri kompletné párovania. Druhý graf má kompletné párovanie,
ale množinu jeho hrán nemožno rozložiť na tri kompletné párovania. Tretí graf nemá
kompletné párovanie.
Príklad
l.
Obrázok 20
Párovania v párnych grafoch odpovedajú transverzálam. Nech je X množina dievčat
a Y nech je množina mládencov. Nech je G = (X, Y; E) párny graf, v ktorom sú vrcholy
x E X a y E Y spojené hranou práve vtedy, keď sa mládenec y páči slečne x. Ak označíme
N(x) množinu vrcholov y E Y , pre ktoré existuje (x, y) hrana v grafe G, tak systém
{N(x) ; x E X } odpovedá zoznamom prípustných nápadníkov pre dievčatá a priradenie
čo najväčšieho počtu nápadníkov dievčatám odpovedá max:imovému párovaniu.
72
Definícia. Hrana pokrýva vrchol, ak je s týmto vrcholom susedná a množina hrán
M pokrýva množinu vrcholov S ak pre každý vrchol v E S existuje hrana e E M pokrý­
vajúca vrchol v . Nech je G ( V E) graf, x E V a S � V. Symbolom N(x) označujeme
množinu vrcholov y E V, pre ktoré existuje (x, y ) hrana v grafe G a symbolom N(S)
=
,
označujeme množinu U N(x) .
xES
Nasledujúca veta je ekvivalentná s Hallovou vetou 7. 1 , avšak formulovaná je v reči
teórie grafov.
Veta 1 1 . 1 {Hallova veta) . Párny graf G = (X, Y; E) má párovanie pokrývajúce
celú množinu X práve vtedy, ked' IN(S) l � I B I pre každú množinu S � X .
Dôkaz. Nech je G = (X, Y; E) párny graf, pričom X
{xb x2 , . . . , X n } · Podľa Hallovej vety 7. 1 má systém N(x1 ) , N(x2) , . . . , N(x n ) podmnožín množiny Y transverzálu
práve vtedy, keď pre každé k
l , 2, . . . , n a pre každý výber ib i2 , . . . , ik taký, že
l � i1 < i2 < · · · < ik � n platí
=
=
Transverzála je priradenie rôznych prvkov y množiny Y rôznym množinám N(x ) , pričom
y E N(x) . Preto dvojice prvkov (x, y) reprezentujúce toto priradenie tvoria navzájom
nezávislé hrany grafu G. Keďže v transverzále má každá množina N (x) , x E X , reprezen­
tanta y E Y, tak navzájom nezávislé hrany reprezentujúce transverzálu pokrývajú celú
množinu X . Teda systém N(xl ) , N(x2) , . . . , N(x n ) má transverzálu práve vtedy, keď
v grafe G existuje párovanie pokrývajúce celú množinu X . Na druhej strane
čiže pre každú množinu S = {xb x2 , . . . , xk } platí IN(x i 1 ) U N(xi2 ) U · · · U N (xi k ) l � k
práve vtedy, keď IN(S) I � IBI . D
Veta 1 1 . 2 . Nech je H = (X, Y; F) pravidelný párny graf stupňa p. Potom množinu
hrán F možno rozložiť na p kompletných párovaní grafu H.
Dôkaz. Všimnite si, že I X I
=
I Y I , keďže H má piX I
=
p i Y I hrán. Vetu dokážeme
indukciou podľa stupňa p grafu H.
l Ak p = l , tak niet čo dokazovať, lebo hrany tvoria kompletné párovanie grafu H.
2° Nech veta platí pre grafy stupňa p- 1 , pričom párny graf H má stupeň p. Ukážeme,
že H má kompletné párovanie. Nech S � X . S vrcholmi množiny S je susedných piSI
hrán, pričom všetky tieto hrany majú druhého suseda v množine N(S) . Ak by platilo
IN(S) I < I B I , tak by podľa Dirichletovho princípu existoval vrchol y E N(S) , ktorého
stupeň je aspoň
> p, čo je spor s predpokladom, že párny graf H je pravidelný
stupňa p. To znamená, že IN(S) I � IBI platí pre každú množinu S � X , čiže podľa
Hallovej vety 1 1 . 1 má párny graf H párovanie M pokrývajúce celú množinu X . Keďže
I X I = IYI , tak M je kompletné párovanie grafu H. Označme H' graf, ktorý vznikne z H
o
73
vynechaním všetkých hrán párovania M. Graf H' je pravidelný párny graf stupňa p- 1
a podľa indukčného predpokladu možno množinu hrán grafu H' rozložiť na p- 1 kom­
pletných párovaní M1 , M2 , . . . , Mp - l · Teda M1 , M2 , . . . , Mp - b M je rozklad množiny
hrán grafu H na p kompletných párovaní. O
Porovnajte vetu 1 1 . 2 s cvičením 7.5. Nasledujúca veta je ekvivalentná so zovšeobec­
nenou Hallovou vetou 7.3, avšak formulovaná je v reči teórie grafov.
Veta 1 1 . 3 (zovšeobecnená Hallova veta) . Nech je G = ( X, Y; E) párny graf.
Označme So , takú podmnožinu množiny X, pre ktorú je číslo I So i - IN( So ) l najväčšie .
Potom maximové párovanie párneho grafu G má
I X I - ( I So l - IN( So ) l )
hrán.
Dôkaz. Najprv si všimnime, že platí I So i - IN( So ) l � O, keďže pre prázdnu množinu
sa tento výraz rovná O. Podľa zovšeobecnenej Hallovej vety 7.3 má párny graf G =
= ( X, Y; E) , kde I X I = n , párovanie velkosti r práve vtedy, keď pre každé k = l , 2, . . . , n
a pre každú k-prvkovú podmnožinu S množiny X platí
IN( S ) I � k - ( n - r ) .
To znamená, že párny graf G má párovanie velkosti
množinu S množiny X platí
IN( S ) I � I S I - I X I + r,
čiže
r
r
práve vtedy, keď pre každú pod­
�
I X I - ( I B I - IN(S) I ) .
Teda ak označíme 80 takú podmnožinu množiny X , pre ktorú je hodnota I So i - I N( So ) l
najväčšia, tak maximové párovanie grafu G má
I X I - ( I So l - I N( So ) l )
hrán. O
11.2.
Petersenova a Konigova veta
Definícia. Nech je G = (V, E ) graf a nech je H = (V, F) podgraf grafu G. Ak je H
pravidelný graf stupňa k, tak H nazývame k-faktor grafu G.
Všimnite si, že vrcholová množina k-faktoru grafu G je totožná s vrcholovou množinou
grafu G. Kompletné párovanie je l-faktor grafu a teda podľa vety 1 1 .2 možno pravidelný
74
párny graf stupňa p rozložiť na p l-faktorov. Ak však graf nie je párny, tak nie vždy je
možné rozložiť pravidelný graf na l-faktory, pretože tento graf nemusí obsahovať žiaden
l-faktor, pozri príklad l . Napriek tomu pre 2-faktory platí nasledujúce tvrdenie, ktoré
dokázal J. Petersen v roku 189 1 .
Veta 1 1 .4 ( Petersenova veta ) . Nech je G = (V, E ) pravidelný graf stupňa 2p.
Potom množinu hrán E možno rozložiť na p 2-faktorov grafu G.
Dôkaz. Vetu stačí dokázať pre súvislé grafy, pretože v nesúvislom grafe možno rozlo­
žiť každý komponent súvislosti samostatne. Teda predpokladajme, že G je súvislý graf.
Keďže všetky vrcholy grafu G sú párneho stupňa, tak podľa Eulerovej vety 9.3 v grafe G
existuje uzavretý Eulerovský ťah T. Zvoľme si orientáciu ťahu T a prejdime sa po grafe
pozd fž hrán T . Zvolená orientácia nám určila, ktorým smerom sme prešli každú hranu
grafu G. Označme V = { v b v 2 , . . . , Vn } vrcholy grafu G. Nech sú X = { x 1 , x2 , . . . , Xn } a
Y { Yl l Y2 , . . . , Yn } disjunktné množiny. Zostrojme pomocný párny graf H = (X , Y; F)
tak, že dvojica (xi , Yj ) , je hranou grafu H práve vtedy, keď je ( vi , Vj ) hranou grafu G,
pričom pri prechádzke pozdfž hrán ťahu T sme túto hranu prešli v smere z Vi do Vj ,
l � i � n a l � j � n . Keďže G je pravidelný graf stupňa 2p, tak H je pravidelný
párny graf stupňa p (do každého vrchola grafu G ťah T p krát " prišiel" a p krát z neho
" odišiel" ) . Podľa vety 1 1 . 2 možno množinu hrán F grafu H rozložiť na p kompletných
párovaní F1 , F2 , . . . , Fp . Nech Ek obsahuje také hrany ( vi , Vj ) grafu G, pre ktoré buď
(xi , Yj ) , alebo (xj , Yi ) , patria do Fk , k = l , 2, . . . , p (všimnite si, že iba jedna z hrán
(xi , Yj ) a (xj , Yi ) sa môže vyskytovať v grafe H) . Keďže Xi aj Yi sú vrcholy stupňa l
v l-faktore Fk , tak stupeň vrchola Vi v Ek je 2 pre každé i = l , 2 , . . . , n a k = l , 2, . . . , p.
To znamená, že E1 1 E2 , , Ep sú 2-faktory grafu G. Tieto 2-faktory spolu obsahujú
všetky hrany grafu G, a preto sú ich množiny hrán navzájom disjunktné. Teda systém
E1 1 E2 , . . . , Ep tvorí rozklad množiny hrán grafu G na 2-faktory. D
=
.
•
.
Definícia. Nech je G
(V, E) graf. Podmnožina P množiny vrcholov V tvorí vr­
cholové pokrytie grafu G, ak je každá hrana grafu G susedná s nejakým vrcholom
=
z
množiny P.
Veta 1 1 . 5 ( Konigova veta ) . Počet hrán maximového párovania párneho grafu sa
rovná minimálnemu počtu vrcholov vrcholového pokrytia tohoto grafu.
Dôkaz. Nech je G = (V, E) párny graf. Označme me počet hrán maximového páro­
vania a mv minimálny počet vrcholov vrcholového pokrytia grafu G. Podľa vety 1 1 .3
sa počet hrán maximového párovania rovná J X I - ( J So i - JN(So) l ) pre nejakú množinu
So � X . Potom však (X -So) U N(So) tvorí vrcholové pokrytie, lebo žiadna hrana
nespája vrchol z množiny So s vrcholom z Y -N(So) . Velkosť tohoto pokrytia je
( J X J - J So l ) + J N(So ) l = J X I - ( J So J - J N(So ) l ) = me ,
a preto pre minimálny počet vrcholov vrcholového pokrytia platí mv � me . Na druhej
strane každé vrcholové pokrytie obsahuje aspoň jeden vrchol z každej hrany maximového
párovania, a preto me � mv , čiže me = mv . D
75
Konigova veta je známejšia v inej formulácii.
Definícia. Riadky aj stfpce matice nazývame spoločným názvom línia. Ak nejaký
prvok matice leží v línii l , tak línia l pokrýva tento prvok. Prvky matice, ktoré neležia
v spoločnej línii nazývame nezávislé. Matica A je binárna, ak sú všetky jej prvky O,
alebo l .
Veta 1 1 .6 (Konigova veta) . Maximálny počet navzájom nezávislých jednotiek
binárnej matice sa rovná minimálnemu počtu línií, ktoré pokrývajú všetky jednotky
v tejto matici.
Dôkaz. Nech je A matica typu m x n s prvkami ai ,j a nech sú X = { x1 , X 2 , . . . , Xm }
a Y = {Yb y2 , . . . , Yn } disjunktné množiny. Zostrojme párny graf G = (X, Y; E) tak,
že ( xi , Y; ) E E práve vtedy, keď ai ,; = l. Teda jednotky matice A odpovedajú hranám
a nuly " nehranám" grafu G. Hrany každého párovania grafu G predstavujú v matici A
navzájom nezávislé jednotky, pretože žiadna dvojica týchto hrán nemá spoločný vrchol,
čiže žiadna dvojica odpovedajúcich jednotiek neleží v spoločnej línií. Na druhej strane,
vrcholy každého vrcholového pokrytia grafu G predstavujú línie A pokrývajúce všetky
jednotky, pretože každá hrana je susedná niektorému vrcholu z vrcholového pokrytia,
čiže každá jednotka matice A leží v niektorej z pokrývajúcich línií. Podľa Konigovej
vety 1 1 .5 sa velkosť maximového párovania v grafe G rovná minimálnemu počtu vr­
cholov vrcholového pokrytia grafu G, a preto sa maximálny počet navzájom nezávislých
jednotiek v A rovná minimálnemu počtu línií, pokrývajúcich všetky jednotky matice
A.
O
Príklad
2.
Uvažujme binárnu maticu A typu 5
A=
x
5
o o l o o
o l o l o
l o o o o
o l o o l
o o l o o
Táto matica neobsahuje žiaden nulový riadok ani nulový stfpec. Napriek tomu na pokry­
tie tejto· matice stačia štyri línie: druhý a štvrtý riadok a prvý a tretí stfpec. V matici
A sú štyri navzájom nezávislé jednoty, pretože a1 , 3 = a2 , 4 = a3 , 1 = a4 , 2 = l . Podľa
Konigovej vety 1 1 .6 už neexistuje väčší počet navzájom nezávislých jednotiek ani menší
počet pokrývajúcich línií.
Konigova veta je vetou minimaxového typu. Existuje metahypotéza, že každú hod­
notu, ktorá je maximom jednej veličiny a zároveň minimom inej veličiny, možno nájsť
v čase zhora ohraničenom polynómom, ktorého argument predstavuje velkosť úlohy.
76
Cvičenia
Cvičenie 1 1 . 1 . Dokážte, že množinu hrán Petersenovho grafu nemožno rozložiť
kompletné párovania.
na
Cvičenie 1 1 . 2 . Nájdite rozklad množiny hrán kompletného bipartitného grafu
Kn,n , kde n je párne, na 2-faktory.
Cvičenie 1 1 . 3 . Nájdite rozklad množiny hrán kompletného grafu Kn , kde n je
párne, na l-faktory.
Cvičenie 1 1 .4. Nájdite rozklad množiny hrán kompletného grafu Kn , kde n je
nepárne, na 2-faktory.
Cvičenie 1 1 . 5 . Pre aké n môže existovať rozklad množiny hrán kompletného grafu
Kn na trojuholníky? Akú štruktúru tvorí takýto rozklad?
Cvičenie 1 1 .6 . Dokážte, že v ľubovoľnom grafe má minimová množina vrcholov
vrcholového pokrytia aspoň takú velkosť, ako je velkosť maximového párovania.
Cvičenie 1 1 . 7 . Zostrojte párny graf odpovedajúci binárnej matici A z príkladu 2.
Cvičenie 1 1 . 8 . Zostrojte binárnu maticu A odpovedajúcu prvému grafu z obráz­
ku 20.
77
Literat úra
BRUALDI, R. : Intro ductory combinatorics. 2- nd edition, Prentice Hall 1992.
BURJAN, V. , BERO, P., C ERNEK, P.: Matematický koktail. Slovenské Pedago­
gické nakladateľstvo, Bratislava 1 99 1 .
[3] SIRÁŇ, J . : Prednášky pre postgraduálnych študentov. Stavebná fakulta, Slovenská
technická univerzita, Bratislava 1 997.
[ 4] VILENKIN, N. J . : Kombinatorika. SNTL, Praha 1977.
[ 5 ] ZNÁM, S . : Kombinatorika a teória grafov. Matematicko-fyzikálna fakulta, Uni­
verzita Komenského, Bratislava 1989.
[ l]
[2]
·
78
Obsah
Predhovor
l.
3
Dirichletov princíp
5
1 . 1 . Slabá forma Dirichletovho princípu
1 .2. Silná forma Dirichletovho princípu
1 .3. Ramseyova veta
5
6
8
2. Základné enumeračné princípy
2 . 1 . Dva základné princípy
2.2. Permutácie, variácie a kombinácie
2.3. Permutácie, variácie a kombinácie s opakovaním
3 . Binomické koeficienty
3.1.
3.2.
3.3.
3.4.
Pascalova formula
Binomická veta
Multinomická veta
Newtonova binomická veta
4. Princíp inklúzie a exklúzie
4. 1 . Princíp inklúzie a exklúzie
4 . 2 . Modifikácie princípu inklúzie a exklúzie
5. Rekurentné vzťahy
5. 1 . Iterácie
5. 2 . Lineárne homogénne vzťahy s konštantnými koeficientami prípad rôznych koreňov
5.3. Lineárne homogénne vzťahy s konštantnými koeficientami prípad rovnakých koreňov
6 . Vytvárajúce funkcie
6. 1 . Obyčajné vytvárajúce funkcie
6.2. Exponenciálne vytvárajúce funkcie
6.3. Binárne stromy
ll
ll
12
14
17
17
19
21
21
24
24
25
30
30
32
34
38
38
40
42
79
Systémy rozličných reprezentantov
1.
7 . l . Hallova veta
7.2. Zovšeobecnenie Hallovej vety
8 . Blokové plány
45
48
51
8. 1 . Blokové plány
8.2. Konečné roviny
51
52
9 . Prechádzky v grafoch
57
9 . 1 . Grafy
9.2. Eulerovské ťahy
9.3. Hamiltonovské kružnice
10. Rovinnosť grafov
10. 1 . Stromy
10.2. Rovinné grafy
10.3. Farebnosť grafov
ll.
Párne grafy
l l . l . Párovania a transverzály
1 1 . 2 . Petersenova a Konigova veta
Literatúra
80
45
57
59
61
64
64
65
66
72
72
74
78
RNDr. Martin Knor, PhD.
KOMBINATORIKA A TEÓRIA GRAFOV I
Vedúci katedry: doc. RNDr. Valent Zaťko, CSc.
Vydal a Uni verzita Komenského v Bratislave vo Vydavateľstve UK
Zodpovedná redaktorka: Anna Známová
Technická redaktorka: Darina Fäl dešová
Korigoval autor
Rozsah 80 strán, 4,9 1 AH, 5 , 2 7 VH, prvé vydan ie, náklad 1 5 0 výtlačkov, v roku 2000 vytlačilo Polygrafické stredisko UK
v Brati slave
ISBN 80-223-1339-4
Download

Untitled - HelpWeb