Diskrétní matematika

• 2 minuty opékat 1A, 2A
• 2 minuty 1B, 3A
• 2 minuty 2B, 3B

lze indukovat tak, že dokážeme platnost tvrzení pro $n = 1$, $n = 2$ a následně pro $n + 2$

• teorie z přednášek – umět definovat, formulovat tvrzení, dokázat je
• nemusíme si pamatovat důkazy z přednášek
• je potřeba, abychom na zkoušce předvedli cokoliv, co funguje

$a \backslash b \equiv \exists c : b = a \cdot c$

$definice \rightarrow tvrzení \xrightarrow{důkaz} věta$

• budeme předpokládat, že tvrzení neplatí, následně dokážeme, že je nemožné, aby tomu tak bylo
• příklad
  • Tvrzení: Prvočísel je nekonečně mnoho.
  • Důkaz: sporem: Nechť $p_1, p_2, \dots, p_n$
  • viz sešit

• chceme: $\forall n \in \mathbb{N}: \phi(n)$
• poznámka: do přirozených čísel na této přednášce řadíme nulu
• uděláme: $\phi(0)$, indukční krok $\forall n(\phi(n) \Rightarrow \phi(n+1))$
• příklad
  • Tvrzení: $2^0 + 2^1 + \dots + 2^n = 2^{n+1}-1$
  • Dk: indukcí podle n
    1. zákl. případ: $n=0$ ......... 1=1
    2. krok: IP:

• $(x,y) \in R$ zkrátíme na xRy
• rovnost
  • R = {(1,1), (2,2), (3,3), (4,4), (5,5)}
  • diagonální relace – $\Delta_X := \{(x,x) | x \in X\}$
• dělitelnost x \ y
• $x+y \leq 5$
• $\emptyset$ prázdná relace
• X × Y univerzální relace

$\forall x \in X, \forall \in Y: yR^{-1}x \equiv xRy$

$\forall x \in X, \forall z \in Z: x(R \circ S)z \equiv (\exists y \in Y: xRy \land ySz)$

• $R \subseteq X×Y, \Delta_Y$
• $R\circ \Delta_Y = R$

• pro $x \in X: f(x)=y \equiv xfy$
• pro $A \subseteq X: f[A]:=\{f(a)|a \in A\}$

• $x \mapsto x$ identita $\Delta_X$
• $sin: \mathbb{R} → [-1,1]$
  • lze zapsat větší množinu než definiční obor?
• $sgn: \mathbb{R} → \{-1,0,+1\}$
  • $x \mapsto -1$ pro $x<0$
  • $x \mapsto 0$ pro $x=0$
  • $x \mapsto +1$ pro $x>0$
• mohutnost množiny
  • $|\_|: 2^\mathbb{N} → \mathbb{N} \cup \{\infty\}$
• $f(a,b) = a+b$
  • $f: \mathbb{R}×\mathbb{R} → \mathbb{R}$

• $f \circ g$
• dva způsoby značení
• $(f \circ g)(x)=g(f(x))$

• prostá (injektivní) $\equiv \forall x_1, x_2 \in X: X \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$
• na Y (surjektivní, francouzská výslovnost) $\forall y \in Y : \exists x \in X : f(x)=y$
• vzájemně jednoznačná (1–1, bijektivní) $\equiv \forall y \in Y : \exists! x \in X: f(x) = y$

přičemž Y' je množina všech obrazů, tedy všech $f[X]$

• reflexivní $\equiv \forall x \in X: xRx$
  • $\Delta_X \subseteq R$
• symetrická $\equiv \forall x,y \in X: xRy \iff yRx$
  • $R = R^{-1}$
• antisymetrická $\equiv \forall x,y \in X, x\neq y: (xRy \Rightarrow \neg yRx)$
  • pokud x a y jsou různé prvky a x je v relaci s y, tak není pravda, že y je v relaci s x
• tranzitivní $\equiv \forall x,y,z \in X: xRy \land yRz \Rightarrow xRz$
  • $R \circ R \subseteq R$
• Df: Relace R je ekvivalence $\equiv$ R je reflexivní & symetrická & tranzitivní
  • příklady
    • rovnost na reálných číslech
    • mod K na Z
      • $x \equiv y \iff K \backslash x-y$
    • geometrická shodnost
    • geometrická podobnost
  • pro R ekvivalenci na X
    • Df: ekvivalenční třída prvku $x \in X$: $R[x] := \{y\in X | xRy\}$
      • viz sešit

• např. porovnávání reálných čísel
• Df: (částečně) Uspořádaná množina (X,R): X je množina, R uspořádání na X
• Značení $\leq$ (nebo různé varianty tohoto znaku)
• Df: $x,y \in X$ jsou porovnatelné $\equiv xRy \lor yRx$
• Df: Uspořádání je lineární (úplné) $\equiv$ každé 2 prvky jsou porovnatelné
• částečné uspořádání – může (ale nemusí) mít neporovnatelné prvky
• ostré uspořádání – každému uspořádání $\leq$ na X přiřadíme relaci $<$ na X: $a < b \equiv a \leq b \land a \neq b$
  • pozor – ostré uspořádání není speciálním případem uspořádání (protože není reflexivní)
  • vlastnosti ostrého uspořádání – ireflexivní, antisymetrické, tranzitivní
• příklady
  • $(\mathbb{N}, \leq)$ lineární
  • $(\mathbb{Q}, \leq)$ lineární
  • $\Delta_X$
  • $(\mathbb{N}^+, \backslash)$
  • $(2^X, \subseteq)$ inkluze
  • lexikografické
    • abeceda: $(X, \leq)$
    • Df: $(X^2,\leq_{lex})$
    • $(a_1, a_2) \leq_{lex} (b_1, b_2) \equiv a_1 \lt b_1 \lor (a_1=b_1 \land a2\leq b_2)$
    • $(X^k, \leq_{lex})$
    • $(X^*, \leq_{lex})$
      • X* – konečné posloupnosti prvků z X
    • pokud je slovo krátké, doplníme ho mezerami ze začátku abecedy

• $a \triangleleft b \equiv a \lt b \land \nexists c: a \lt c \land c \lt b$
• Hasseův diagram – pro konečné ČUM (částečně uspořádané množiny) – viz sešit

• minimální $\equiv \nexists y\in X:y \lt x$
• nejmenší $\equiv \forall y \in X: x \leq y$
• maximální
• největší

• Buď $x_1$ je minimální,
• nebo $\exists x_2 < x_1$, s ním pokračuji
• $x_1>x_2>x_3>\dots >x_t$
• Pokud t > |x|, pak $\exists i,j; i\neq j: x_i = x_j$
• to lze pomocí tranzitivity dovést ke sporu

• řetězec $\equiv (A,\leq)$ je lineární UM
• antiřetězec $\equiv \forall(a,b) \in A, a \neq b$ jsou neporovnatelné

n-prvková množina od 1 do n

• jeden člen výsledného součtu – součin n věcí, z nichž každá bude x nebo y
  • z každé závorky vyberu x nebo y
  • výsledkem je člen $x^{n-k}y^k$
  • takových členů tam bude $n \choose k$

• kolik existuje způsobů, jak číslo n zapsat jako k sčítanců
• kuličky nejsou rozlišitelné, přihrádky ano
• máme stroj na plnění přihrádek, ten se nad nimi pohybuje a sype do nich kuličky
• umí operace – pohni se o přihrádku doprava (P), přidej kuličku (K)
• v programu je právě k-krát příkaz na pohyb a právě n-krát příkaz na přidání kuličky, musí končit p
• tudíž (k-1)-krát příkaz na pohyb a n-krát příkaz na přidání kuličky
• ${n+k-1}\choose n$ možností

• bijekce z množiny klobouků do množiny pánů
• $\pi(i)=i$ … pevný bod
• velikost průniku je $(n-k)!$
• nezáleží na výběru podmnožiny z indexové množiny, takže stačí vynásobit n nad k

• triviální: $2^{n-1} \leq n! \leq n^n$
• $n^{\frac{n}{2}} \leq n! \leq (\frac{n+1}{2})^n$
• důkaz AG nerovnosti

• G = (V, E)
• množina vrcholů … V(G)
• množina hran … E(G)

• orientované – hrany mají šipky
• se smyčkami – jako u relací
• multigrafy – dva vrcholy spojené více než jednou hranou
• nekonečné grafy

• úplný graf $K_n$
  • $V(K_n):=[n]$
  • $E(K_n):={V(K_n)\choose 2}$
• prázdný graf $E_n$
  • $V(E_n):=[n]$
  • $E(E_n) =\emptyset$
• cesta $P_n$
  • $V(P_n):=\{0\dots n\}$
  • $E(P_n):=\{\{i,i+1\}|0\leq i \lt n\}$
  • délka cesty se měří v počtu hran
• kružnice/cyklus $C_n$
  • $n\geq 3$
  • $V(C_n):=\{0\dots n–1\}$
  • $E(C_n):=\{\{i,i+1\mod n\}|0\leq i \lt n\}$
• úplný bipartitní $K_{m,n}$
  • každý prvek nalevo je spojený s každým napravo
  • prvky na jedné straně mezi sebou nejsou spojeny
• bipartitní graf
  • partity grafu – jednotlivé „strany“
  • Df: Graf (V, E) je bipartitní $\equiv \exists L,P\subseteq V$ t. ž.:
    • $L \cup P = V$
    • $L \cap P = \emptyset$
    • $\forall e \in E: |e \cap L| = 1\quad (\land\ |e \cap P| = 1)$

• existuje bijekce, která zachovává vlastnost být spojen hranou
• v podstatě stačí přejmenovat vrcholy a dostaneme dva stejné grafy
• značení $\cong$
• $\cong$ je ekvivalence na libovolné množině grafů
  • neexistuje množina všech grafů (protože neexistuje množina všech množin)

• # grafů na n vrcholech
• každá dvojice vrcholů buď je hranou, nebo ne
• některé grafy jsou izomorfní, ale dokázali jsme, že se počet neizomorfních grafů blíží počtu všech grafů

• „podgraf indukovaný množinou vrcholů“
• $G[A] := (A, E(G) \cap {A \choose 2})$

• v grafu existuje podgraf izomorfní s Pn
• v grafu existuje určitá posloupnost

• výsledný graf je podgraf indukovaný množinou všech vrcholů bez toho odebíraného
  • $G-v=G[V\setminus\{v\}]$

nepovolíme smyčky (v podstatě zakážeme diagonálu na relaci)

• silná souvislost – existuje cesta z každého vrcholu do každého vrcholu
• slabá souvislost – graf „drží pohromadě“, podkladový graf je souvislý (podkladový graf je neorientovaný graf založený na tom původním orientovaném)
• silná souvislost $\implies$ slabá souvislost
• pro vyvážené grafy platí silná souvislost právě tehdy, když platí slabá

• matice sousednosti (A)
  • pro graf s n vrcholy má n řádků a n sloupců
  • jednoznačně určuje graf až na pojmenování vrcholů (tedy všechny izomorfní grafy)
  • matice sousednosti je symetrická s nulami na hlavní diagonále
  • druhá mocnina matice sousednosti nám určí, kolik je mezi dvěma vrcholy sledů délky 2
  • věta o k-té mocnině matice sousednosti + důkaz

• vzdálenost bude vždy nezáporná
• $d_G(u,v) = 0 \iff u=v$
• platí trojúhelníková nerovnost $d_G(u,w) \leq d_G(u,w) + d_G(w,v)$
• $d_G(v,u)=d_G(u,v)$

nejdřív musíme otrhat listy a potom je zpátky přidat – nestačí dokázat, že můžeme přidávat listy k grafu o jednom vrcholu a bude to platit stále

• G je souvislý a acyklický (strom)
• mezi vrcholy $u, v$ existuje právě jedna cesta (jednoznačně souvislý)
• G je souvislý a po smazání libovolné jedné hrany už nebude souvislý (minimální souvislý)
• G je acyklický a po přidání libovolné jedné hrany vznikne cyklus (maximální acyklický)
• G je souvislý a platí pro něj Eulerova formule

• $f:[0,1]→\mathbb R$
• spojitá, prostá
• = oblouk

• části, na které nakreslení grafu rozděluje rovinu
• stěnou je i vnější stěna (zbytek roviny)
• hranice stěny – skládá se z hran
• hranice stěny je nakreslení uzavřeného sledu

• cesty
• kružnice
• stromy
• $K_1, K_2, K_3, K_4$

• stereografická projekce
• střílím polopřímku ze severního pólu, promítám na rovinu, na které leží jižní pól
• spojitá bijekce mezi sférou bez severního pólu a rovinou
• sféru můžeme libovolně pootočit
• $\implies$vnější stěnu lze zvolit libovolně

• odebrání vrcholu či hrany je v pořádku
• přidání vrcholu je v pořádku
• přidání hrany může být problém
• dělení hrany je v pořádku
• kontrakce hrany je v pořádku (podle geometrické intuice)

G je nerovinný$\iff$G obsahuje podgraf izomorfní s dělením $K_5$ nebo $K_{3,3}$

• základní příklad
  • G je strom, $e = v-1$
  • f = 1
  • chceme: $v+1=v-1+2 \space\checkmark$
• $e -1→ e$
  • mějme graf G s $e$ hranami
  • nechť x je hrana na kružnici v G
  • $G' := G–x$
  • $v'=v$
  • $e'=e-1$
  • $f'=f-1$
  • z IP: $v' + f' = e'+2$
  • $v+f-1=e-1+2 \space \checkmark$

• G je souvislý (u nesouvislých se komponenty dají spojit, což je spor s maximální souvislostí)
• je-li hranicí stěny kružnice$\implies$je to $\Delta$ (kdyby to nebyl trojúhelník, dá se najít úhlopříčka, což je spor)
• hranicí stěny není $C_n$

• každá stěna přispěje třemi hranami
• každá hrana patří ke dvěma stěnám
• $3f=2e → f=\frac{2}{3}e$
• $v+\frac{2}{3}e=e+2$
• $v-2=\frac{1}{3}e$
• $e=3v-6$

$v'=v,\ e'\geq e,\ e'=3v'-6,\ e\leq 3v-6$

• průměrný stupeň vrcholu v rovinném grafu < 6
  • součet stupňů / v = 2e/v $\leq$ 6v-12 / v < 6
• v každém rovinném grafu existuje vrchol stupně $\leq$ 5

• max. grafy mají stěny čtverec, pěticyklus, hvězda o pěti paprscích
• podle eulerovy formule…

• $\chi(E_n)=1$
• $\chi(K_n)=n$
• $\chi(P_n)=2$ pro $n\geq 1$
• pro $n$ sudé $\chi(C_n)=2$, pro $n$ liché $\chi(C_n)=3$

• strom rozdělíme do vrstev podle vzdálenosti od kořenu
• $c(x)=(d(v,x) \mod 2)+1$

tedy bipartitní grafy jsou ty, které neobsahují liché kružnice

• $\implies$ máme dokázáno obměnou (když má lichou kružnici, nejde obarvit dvěma barvami)
• $\impliedby$
  • kdyby G byl nesouvislý: obarvíme po komponentách
  • jinak: nechť T je kostra grafu G, pak existuje obarvení kostry (dvěma barvami)
    • sporem: kdyby existovala hrana, které tohle obarvení přiřklo stejné barvy koncových vrcholů, pak v grafu existuje lichá kružnice
    • mezi stejnobarevnými vrcholy bude cesta sudé délky, protože mají stejnou barvu a jsou ve stromě
    • tedy spojením stejnobarevných vrcholů vznikne lichá kružnice

• vrcholy lze uspořádat tak, že z každého vrcholu doleva vede nejvýše k hran
• vrcholy skládám zprava doleva tak, jak je odtrhávám

• pro $|V|\leq 5$ triviální
• $n-1\to n$
  • nechť $v$ je vrchol s minimálním stupněm (nejvýše pět)
  • G' := G–v, podle IP existuje 5-obarvení c' grafu G'
  • pokud na sousedech $v$ v obarvení c' jsou použity max. 4 barvy, tak tu pátou můžeme použít na vrchol $v$
  • co když má každý soused jinou barvu
    • A je podgraf indukovaný vrholy, do kterých existuje cesta ze souseda $a$ přes áčkové a céčkové barvy
    • pokud soused $c \notin A$
      • prohodíme barvy v A
      • tím pádem áčková barva se uvolní pro $v$
    • pokud soused $c \in A$
      • použiju stejný trik pro b a d
      • soused $b$ je obalený kružnicí mezi $a$ a $c$, takže nehrozí, že by byl spojený s $d$
  • tzv. Kempeho řetězce

• máme vrchol stupně 5
• musí existovat dva sousedi toho grafu, kteří nejsou spojeni hranou (jinak bychom dostali K5)
• můžu vytvořit rovinný G'=G–v+{x,y} (přidání hrany)
• můžu vytvořit rovinný G''=G'.{x,y} (kontrakce hrany)
• G'' obarvíme indukcí → dostaneme obarvení c'' → c obarvení G–v (v němž se barvy x a y rovnají) → existuje volná barva pro v

• síť vysílačů – vysílačům přiřazuju frekvence
• dělení přednášek do poslucháren

• $\Omega$ = množina elementárních jevů
• $\mathcal F \subseteq 2^\Omega$ = množina jevů
• $P:\mathcal F \to [0,1]$ = pravděpodobnost

• $\Omega$ konečná nebo spočetná (tedy spočetně nekonečná, existuje bijekce do $\mathbb N$)
• $\mathcal F = 2^\Omega$
• $P(J)=\sum_{x\in J}P(\lbrace x\rbrace)$
  • stačí určit pravděpodobnosti elementárních jevů
  • tedy jev nastává, když nastane kterýkoli z jeho elementárních jevů
• $P(\emptyset)=0$
• $P(\Omega)=1$
• náš diskrétní pravděpodobnostní prostor je konečný a klasický
• klasický … $P(J)=\frac{|J|}{|\Omega|}$
  • klasický pravděpodobnostní prostor – všechny elementární jevy mají stejnou pravděpodobnost

• $\Omega = \lbrace 0,1 \rbrace^n$
• $P(\lbrace \omega \rbrace)=2^{-n}$

• u kulatých je tam množina
• u hranatých je tam podmínka

• tři kartičky, jedna je z obou stran červená, druhá modrá, třetí má jednu stranu červenou a druhou modrou
• vybereme náhodnou kartičku
• otočíme ji náhodnou stranou nahoru
• horní strana je červená
• jaká je pravděpodobnost toho, že dolní strana je také červená
• pravděpodobnostní prostor: ČČ, ČČ, MM, MM, ČM, ČM
• tři možnosti, z nich dvě chceme, takže $2 \over 3$

• T … pozitivní
• N … nemocný
• známe
  • $P[T|N]=0.95$
  • $P[T|\bar N]=0.03$
  • $P(N)=0.06$
• chceme: $P[N|T]$

• $P(A\cap B)=P(A)\cdot P(B)$
  • $P[A|B]\cdot P(B)=P(A)\cdot P(B)$
• $\iff P(B)=0 \lor P[A|B]=P(A)$

• lze zobecnit na jevy po k nezávislé
• jevy jsou nezávislé $\equiv$ pro každé $k\geq 2$ jsou po $k$ nezávislé

• kostka
• jev A … padlo sudé … 1/2
• jev B … padlo prvočíslo … 1/2
• padlo sudé prvočíslo … 1/6
• jevy jsou závislé

• dva hody mincí
• A … první hod je jednička
• B … druhý hod je jednička
• C … sudý počet jedniček
• jevy jsou po 2 nezávislé, ale nejsou po 3 nezávislé, tedy nejsou nezávislé

• jev s pevným bodem 1
• jev s pevným bodem 2
• nejsou nezávislé

důkaz pomocí roztržení sumy

• n hodů mincí
• X = počet jedniček … chceme $\mathbb E[X]$
• $X_i :=$ počet jedniček na i-té pozici
• z linearity víme, že střední hodnota X je součet středních hodnot Xi

• funkce, která elementárním jevům přiřazuje reálná čísla
• $X:\Omega\to\mathbb R$

• $\mathbb E[X]:=\sum_{\omega\in\Omega}X(\omega)\cdot P(\omega)=\sum_{a\in\mathbb R}a\cdot P[X=a]$
• linearita

• $X:=$ počet jevů, které nastaly
• $X_i$ … indikátor jevu $J_i$
• $\mathbb E[X_i]=0\cdot P[X_i=0]+1\cdot P[X_i=1]$
• střední hodnota indikátoru jevu je rovna pravděpodobnosti jevu
• $\mathbb E[X]=\sum_i\mathbb E[X_i]$

• kolik hran vede mezi levou a pravou hromádkou?
• $X$ … počet hran, které vedou napříč
• vezmeme náhodný rozklad
  • $L\cup P=V$
  • $L\cap P = \emptyset$
  • jedna z hromádek může být i prázdná
• $X:=$ počet hran mezi $L,P$, tedy počet $e\in E:|e\cap L|=1$
• $X_e$ … indikátor
• $\mathbb E[X_e]=\frac{1}{2}$
• $X=\sum_eX_e\implies\mathbb E[X]=\sum_e\mathbb E[X_e]=\frac{|E|}{2}$
• důsledek: existuje rozdělení na $L,P$ takové, že napříč vede alespoň polovina hran
  • alespoň jeden z bipartitních podgrafů obsahuje alespoň polovinu všech hran

pokud $X\lt{49\over 100}\cdot |E|$, znovu

• nechť X je nezáporná náhodná veličina a $k\gt 0$
• přičemž $\mathbb E[X]\gt 0$
• pak $P\left[X\geq k\cdot\mathbb E\left[X\right]\right]\leq\frac 1k$

• $\mathbb E[X]=\sum_{a\geq0}a\cdot P[X=a]=\sum_{a\lt t}a\cdot P[X=a]+\sum_{a\geq t}a\cdot P[X=a]$
• tvrdím, že první suma (pro $a\lt t$) je nezáporná
• u druhé sumy využiju toho, že $a\geq t$
• $\mathbb E[X]\geq t\cdot P[X\geq t]$
• pro $t=k\cdot\mathbb E[X]$ dosadím
• $P[X\geq k\cdot\mathbb E[X]]\leq\frac{\mathbb E[X]}{k\cdot\mathbb E[X]}$

• $P[X\lt {49\over 100}\cdot|E|]$
• $X'=|E|-X$
  • (počet hran, které nevedou napříč)
• $X'\gt{51\over 100}\cdot|E|$
• $X'\gt {51\over 50}\cdot\frac{|E|}{2}$
• …

• věta: pro každou konečnou ČUM $(X,\leq)$ platí $\alpha(X,\leq)\cdot \omega(X,\leq)\geq |X|$
  • řetězec: $A\subseteq X:\forall a,b\in A: a\leq b\lor b\leq a$
  • antiřetězec: $A\subseteq X:\forall a,b\in A,\;a\neq b: \neg(a\leq b\lor b\leq a)$
  • maximální velikost řetězce … $\omega$ („výška“)
  • maximální velikost antiřetězce … $\alpha$ („šířka“)
  • důsledek věty: $\text{max}(\alpha,\omega)\geq\sqrt{|X|}$
• důkaz
  • najdeme všechny minimální prvky → vrstva $X_1$
  • smažu $X_1$, proces opakuju → najdu $X_2$
  • tak postupuju dál, dokud nerozkrájím celou ČUM
  • každá vrstva tvoří antiřetězec
  • vrstvy jsou rozklad
  • existuje množina taková, že každý prvek je z jiné vrstvy a dohromady tvoří řetězec
    • formálně $\exists\lbrace q_1,\dots,q_k\rbrace$ řetězec t. ž. $\forall i: q_i\in X_i$
    • jak je to možné?
      • $q_{i+1}$ je ve vrstvě $X_{i+1}$, protože nějaký prvek $q_i$ je menší – ten je ve vrstvě $X_i$

• lemma: Nechť $x_1,\dots,x_{n^2+1}$ je posloupnost nazvájem různých čísel. Potom existuje vybraná podposloupnost délky $n+1$, která je ostře monotónní (rostoucí nebo klesající).
• důkaz
  • definujme relaci $\leq$ na množině indexů $\lbrace 1,\dots,n^2+1\rbrace$
  • $i\leq j\equiv i\leq j\land x_i\leq x_j$
  • pozorování: $\leq$ je ČU
    • řetězec je rostoucí pp. (podposloupnost)
    • antiřetězec je klesající pp.
  • $\alpha\cdot\omega\geq n^2+1$
    • nemůže nastat $\alpha \leq n\land \omega\leq n$
    • $\implies \alpha\geq n+1\lor\omega\geq n+1$

• platónské těleso = konvexní pravidelný mnohostěn, jehož všechny stěny jsou shodné pravidelné mnohoúhelníky a zároveň z každého vrcholu vychází stejný počet hran
• příklad
  • vezmu osmistěn, opíšu mu sféru
  • z těžiště budu promítat vrcholy na sféru
  • vznikne rovinný graf
• hledám rovinný graf
  • každá stěna má právě $k$ hran, $3\leq k$
  • graf je d-regulární, $d\leq 5$
• lze sestrojit duální graf – prohodí se nám $k$ a $d$
  • $3\leq k\leq 5$
  • $3\leq d\leq 5$
• Eulerova formule: $v+f=e+2$
  • $kf=2e, \quad dv=2e$
  • vyjádříme $f,v$ dosadíme do E. f.
  • ${2e\over d}+{2e \over k}=e+2$
  • vydělím 2e
  • $\frac 1d+\frac 1k=\frac 12+\frac 1e$
  • tedy pravá strana rovnice bude $\in(\frac 12,1]$
    • z toho plyne, že $\text{min}(d,k)=3$
• tabulka možných parametrů – $d,k$ vymýšlím podle podmínek, zbytek dopočítávám ze vzorců
  • d,k; e,v,f
  • 3,3; 6,4,4 … čtyřstěn
  • 3,4; 12,8,6 … krychle
  • 3,5; 30,20,12 … dvanáctistěn
  • 4,3; 12,6,8 … osmistěn
  • 5,3; 30,12,20 … dvacetistěn
• jiné nemohou existovat