Fakulta elektrotechniky a informatiky Vysoká škola báňská - Technická univerzita Ostrava
Diskrétní matematika 2012/2013
Projekt číslo 3 jméno: Jiří Znoj login: zno0011 hodnotící: Mgr. Pavel Skalný
Příklad:
Hodnocení:
Poznámky:
Kombinatorika: 3.1 Kombinatorika: 3.2 Teorie grafů: 3.3 Teorie grafů: 3.4
Ostrava, 6. prosince 2012
I.
Obsah I.
Obsah .................................................................................................................................................... 2
II.
Kombinatorika: ..................................................................................................................................... 3 1.
příklad 3.1. ......................................................................................................................................................3 zadání:................................................................................................................................................................................ 3 výpočet: ............................................................................................................................................................................. 3 výsledek: ............................................................................................................................................................................ 3
2.
příklad 3.2 .......................................................................................................................................................3 zadání:................................................................................................................................................................................ 3 výpočet: ............................................................................................................................................................................. 3 výsledek: ............................................................................................................................................................................ 4
III. 1.
Teorie grafů: ...................................................................................................................................... 4 příklad 3.3 .......................................................................................................................................................4 zadání:................................................................................................................................................................................ 4 výpočet: ............................................................................................................................................................................. 4 výsledek: ............................................................................................................................................................................ 4
2.
příklad 3.4 .......................................................................................................................................................5 zadání:................................................................................................................................................................................ 5 výpočet: ............................................................................................................................................................................. 5 výsledek: ............................................................................................................................................................................ 5
Jiří Znoj – zno0011
2
II.
Kombinatorika: 1. příklad 3.1. zadání: Rytíři kulatého stolu zasedli ke společné hostině. Kolik má král Artuš možností jak posadit 15 hodovníků (15 včetně Artuše, Guinevery a Lancelota) kolem stolu, jestliže chce sedět vedle Guinevery a zároveň nechce, aby vedle Guinevery seděl Lancelot? (1b) výpočet: Nejdříve posadím ke stolu Artuše, Guineveru a 12 nepojmenovaných rytířů. Toto učiním tak, že jelikož Guinevera bude sedět vedle Artuše, z jedné či druhé strany, tak mám 2*13! možností, jak těchto 14 lidí rozesadit. Musím pak ještě posadit Lancelota a to tak, aby neseděl vedle Guinevery. Takže ze 14 pozic, kam by si mohl teoreticky sednout, zbývá 12, které vyhovují zadání. Celkový počet možností je tedy výsledek: 149 448 499 200
2. příklad 3.2 zadání: Neznámý pachatel přestřihl 5 elektrických vodičů. Nešikovný elektrikář se snaží závadu opravit a náhodně vodiče pospojuje. Jaká je pravděpodobnost, že alespoň jeden drát zapojí správně? (2b) výpočet: Všech možností je 5! = 120. Počet možností, že alespoň jeden drát zapojí správně je: ⋃ A1= první drát je zapojen správně a ostatní libovolně, A2 = druhý drát je zapojen správně a ostatní libovolně, A3 = třetí drát je zapojen správně a ostatní libovolně, A4 = čtvrtý drát je zapojen správně a ostatní libovolně, A5 = pátý drát je zapojen správně a ostatní libovolně.
, kde
Ai nejsou disjunktní jevy, proto je třeba použít princip inkluze a exkluze: |⋃
|
∑
( )
číslo ( ) udává počet průniků množin. Každý takový průnik má mohutnost MK. |, pak si musíme uvědomit, že množina Chceme-li určit | obsahuje všechny permutace 𝜋, pro které platí 𝜋(2) = 2 ∧ 𝜋(3) = 3. Každou permutaci z množiny vyjádříme jednořádkově takto: | 𝜋 , přičemž na volných pozicích můžeme čísla 1, 4 a 5 uspořádat libovolně. Proto | | vyjde výsledek totožný, stejně jako pro všechny průniky dvou množin. Pro množinu | | můžeme všechny permutace vyjádřit jako Pokud zvolíme více množin, tak pro množiny | | | 𝜋 , takže , což platí pro všechny průniky 3 množin, jelikož všechny tyto množiny mají stejnou mohutnost. Obecně tedy v tomto příkladu platí, že mohutnost průniku k množin je rovna vztahu , takže
|⋃
Jiří Znoj – zno0011
|
∑
( )
3
pro k=1; pro k=2;
, ( )
,
pro k=3; ( )
,
( )
pro k=4;
,
pro k=5; ( ) |⋃
|
. .
Pravděpodobnost P, že elektrikář zapojí alespoň jeden drát správně je poměr počtu jevů vyhovujících zadání (76) ku počtu všech možných jevů, které mohou nastat (120)
výsledek:
III.
Teorie grafů: 1. příklad 3.3 zadání: Rozhodněte, jestli je posloupnost (6, 5, 4, 2, 2, 2, 2, 1) grafová. Pokud ano, nalezněte 2 grafy, které mají tuto stupňovou posloupnost a nejsou isomorfní. (1b) výpočet: - vrchol je nejvyššího stupně 6, což splňuje podmínku maximálního stupně vrcholu v grafu o 8 vrcholech - posloupnost vyhovuje principu sudosti - zbývá použít větu Havel-Hakimi : (6, 5, 4, 2, 2, 2, 2, 1) ~ (4, 3, 1, 1, 1, 1, 1) ~ (2, 0, 0, 0, 1, 1) ~ (2, 1, 1, 0, 0, 0) ~ (0, 0, 0, 0, 0) Graf s posloupností (0, 0, 0, 0, 0) umím nakreslit:
a podle věty Havel-Hakimi platí, že když posloupnost (0, 0, 0, 0, 0) je grafová, tak i posloupnost (6, 5, 4, 2, 2, 2, 2, 1) je grafová. 2 neizomorfní grafy:
Grafy jsou neizomorfní, protože v levém grafu vrchol stupně 1 sousedí s vrcholem stupně 5 a vpravo nikoli. výsledek: Posloupnost je grafová, 2 neizomorfní grafy – viz obrázek víše. Jiří Znoj – zno0011
4
2. příklad 3.4 zadání: Máme dán rovinný graf s x hranami. Kolik nejméně vrcholů může tento graf mít? (2b) výpočet: Jednoduchý rovinný graf na vrcholech má nejvýše 3 – 6 hran. Důkaz (Kovář Petr: Úvod do teorie grafů, strana 112): Ukážeme, že nerovnost platí v každé komponentě rovinného grafu, proto můžeme předpokládat, že daný graf 𝐺 je souvislý. Označíme počet vrcholů v grafu 𝐺, 𝑓 počet oblastí a ℎ počet hran. Protože jednoduchý graf neobsahuje smyčky ani násobné hrany, tak každá oblast je (v libovolném nakreslení grafu 𝐺) ohraničena alespoň třemi hranami. Budeme-li počítat hrany na hranici každé oblasti, započítáme každou hranu nejvýše dvakrát (ve dvou přilehlých oblastech). Platí tedy Dosazením do Eulerova vztahu (
ℎ
ℎ
𝑓, neboli
ℎ
𝑓.
𝑓) dostaneme: 𝑓
ℎ
ℎ
ℎ
ℎ
odkud snadno vyjádříme horní odhad počtu hran ℎ což je dokazované tvrzení. Z tohoto tvrzení vyplývá, že rovinný graf s x hranami má nejméně
vrcholů, což platí pro graf s minimálním
počtem 3 vrcholů, tedy pro . Pro má graf nejméně 3 vrcholy: (o-o-o). Pro má graf nejméně 2 vrcholy: (o-o). Pro má graf nejméně 1 vrchol: (o). výsledek: Pro
má rovinný graf nejméně
pro pro pro
má rovinný graf nejméně 3 vrcholy, má rovinný graf nejméně 2 vrcholy, má rovinný graf nejméně 1 vrchol.
Jiří Znoj – zno0011
vrcholů,
5
