Kreslení grafů na plochách

Definice: Nechť $X\subseteq {\mathbb{R}}^n,Y\subseteq {\mathbb{R}}^m$, kde $n,m\in \mathbb{N}$. Potom homeomorfismus $f:X\to Y$ je spojité zobrazení, bijekce a $f^{-1}$ je také spojitá. $X,Yjsouhomeomorfn\acute{ı}$X \cong Y$ existuje-li mezi nimi homeomorfismus.

Definice: Plocha je kompaktní (uzavřená, omezená), souvislá (např. oblouková – každé dva body můžeme propojit obloukem), $2$-rozměrná varieta bez hranice (dostatečně malé okolí každého bodu je homeomorfní otevřenému okolí v ${\mathbb{R}}^2$).

Příkladem je třeba sféra nebo torus v ${\mathbb{R}}^3$, naopak celá ${\mathbb{R}}^2$ do definice nezapadá kvůli kompaktnosti.

Každý druh plochy lze zkonstruovat přidáním

• ucha, kde vyřízneme dva kruhy v ploše, kde k těmto dvěma dírám přidám uzavřený plášť válce, na hranici dvou kruhů, který je jinak disjunktní se zbytkem.
• křižítka, kde vyříznu zase kruh a přidám jakýsi “teleport”, jenž bod přemostí do bodu naproti přes křižítko.

Značme ${\Sigma }_g$ pro $g\in \mathbb{N}$, jež je plochou vzniklou ze sféry přidáním $g$ uší. Je to orientovatelná plocha rodu $g$. Obdobně značíme ${\Pi }_g$ pro $g\in \mathbb{N}$ neorientovatelnou plochu rodu $g$ vzniklou přidáním $g$ křižítek ke sféře.

---

Nakreslení grafu

Definice: Nakreslení grafu $G$ na plchu $\Gamma$ je zobrazení $\phi$ takové že

• $\forall v\in V(G)$ přiřadí bod $\phi \in \Gamma$
• $\forall e\in E(G)$ přiřadí prostou, tedy vzájemně neprotínající, křivku $\phi (e)\in \Gamma$ spojující oba konce dané hrany
• žádné dva vrcholy se nepřekrývají
• hrany se překrývají jen ve sdílených vrcholech
• vrcholy které nepatří hraně se s ní neprotínají

Definice: Stěna nakreslení je souvislá komponenta $\Gamma \setminus \left({\bigcup }_{x\in E(G)\cup V(G)}\phi (x)\right)$. Definice: Buňkové nakreslení je takové nakreslení, že každá jeho stěna je homeomorfní otevřenému kruhu v ${\mathbb{R}}^2$.

---

Eulerova formule

Definice: Eulerova charakteristika plochy $\Gamma$ je

$$\begin{array}{rl}\text{X}(\Gamma )& =\{\begin{array}{lcl}2-g& \Gamma \cong {\Pi }_g& \text{pro }g\ge 1\\ 2-2g& \Gamma \cong {\Sigma }_g& \text{pro }g\ge 0\end{array}\\ & =2-\text{pocˇet krˇizˇıˊtek}-2\cdot \text{pocˇet usˇıˊ}.\end{array}$$

Věta: (Zobecněná Eulerova formule) Mějme nakreslení grafu $G$ na ploše $\Gamma$, které má $S$ množinu stěn. Pak $|V|-|E|+|S|\ge \text{X}(\Gamma )$. Pokud je zakreslení buňkové tak to platí s rovností. Důkaz: Indukcí dle rodu $\Gamma$, pro $\Gamma \cong {\Sigma }_0$ toto platí, protože to je rovinná verze Eulerovi formule. Následující postup je analogický pro $\Gamma \cong {\Sigma }_g$, kde trháme ucha, nyní si označme $v(G),e(G),s(G)$ jako počty vrcholů hran a stěn. Mějme buňkové nakreslení $G$ na $\Gamma \cong {\Pi }_g$

Nechť $K$ je křižítko na $\Gamma$ a $x_1,x_2,\dots ,x_k$ jsou body $K$ (ne nutně ale vrcholy grafu), kde $G$ hrany hraničí s $K$. Můžeme předpokládat $k\ge 1$, protože jinak by stěna s $K$ nebyla buňková. Navíc b.ú.n.o. každý vrchol přímo na $K$ posuneme o trochu vedle aby byli incidentní jen hrany.

Vytvoříme si graf $G^{\prime }$ přidáním dvou dělících vrcholů těšně vedle každého $x_i$ na příslušnou hranu. A skóre se pro $G^{\prime }$ změnila tedy na

$$\begin{array}{rl}v(G^{\prime })& =v(G)+2k\\ e(G^{\prime })& =e(G)+2k\\ s(G^{\prime })& =s(G)\end{array}$$

a tedy levá strana rovnice se nezměnila oproti původnímu $G$.

Nyní vytvoříme $G^{\prime \prime }$ přidáním cest délky 2 k sousedním vrcholům pro každý vrchol $x_i$, tím vyrobíme kružnici $V$ kolem $K$ a skóre se změní

$$\begin{array}{rl}v(G^{\prime \prime })& =v(G^{\prime })+2k\\ e(G^{\prime \prime })& =e(G^{\prime })+4k\\ s(G^{\prime \prime })& =s(G)+2k\text{ (steˇny skrze krˇizˇıˊtko deˇlıˊme na 3)}\end{array}$$

a levá strana rovnice se opět nehnula.

Teď odebereme vše uvnitř $C$ a vytvoříme $G^{\prime \prime \prime }$ a skóre je nyní

$$\begin{array}{rl}v(G^{\prime \prime \prime })& =v(G^{\prime \prime })\\ e(G^{\prime \prime \prime })& =e(G^{\prime \prime })-k\text{ (podle k krˇıˊzˇıˊcıˊch se hran)}\\ s(G^{\prime \prime \prime })& =s(G)-k+1\end{array}$$

a levá strana se změnila o $1$ a tedy dle indukčního předpokladu máme

$$v(G^{\prime \prime \prime })-e(G^{\prime \prime \prime })+s(G^{\prime \prime \prime })=\text{X}({\Pi }_{g-1})$$

jako platné a z konstrukce nám vychází

$$\begin{array}{rl}v(G^{\prime \prime \prime })-e(G^{\prime \prime \prime })+s(G^{\prime \prime \prime })& =v(G)-e(G)+s(G)+1\\ \text{X}({\Pi }_{g-1})& =\text{X}({\Pi }_g)+1\end{array}$$

a to sedí s definicí.

Důsledek: Každý graf $G$ nakreslitelný na plochu $\Gamma$ splní $|E|\le 3\cdot |V|-3\text{X}(\Gamma )$, pokud $|V|\ge 4$. Důkaz: Předpokládejme, že každá stěna je trojúhelník a dosadíme $|S|=\frac{2}{3}|E|$.

Věta: Nechť $\Gamma$ je plocha $\Gamma \ncong {\Sigma }_0$, nechť je $G$ nakreslený na $\Gamma$. Potom existuje vrchol v $G$, který má stupeň ($\delta (G)$ - nejmenší stupeň v $G$)

$$\delta (G)\le \lfloor \frac{5+\sqrt{49+24\text{X}(\Gamma )}}{2}\rfloor$$

Důkaz: Mějme průměrný stupeň jako v Důsledku Eulerovi formule. Sice $\frac{2e(G)}{v(G)}$ a máme

undefined