Teorie grafů


Definice Grafu

Graf je uspořádaná dvojice (V,E)(V,E), kde:

Příklady grafů

Značení

Rozšíření


Zoo grafů

Bipartitní graf

Definice:
Graf GG je bipartitní, právě tehdy když \exists rozklad V(G)X,YV(G) X,Y, tak že E(G){{x,y}xX,yY}E(G) \leq \{\{x,y\} x \in X, y \in Y \}

nebo

eE(G):eX=1eY=1\forall e \in E(G): \lvert e \cap X \lvert = 1 \land \lvert e \cap Y \lvert = 1

Příklady:


Izomorfismus

Definice:
Grafy GG a HH jsou izomorfní (značíme GHG \cong H) f:V(G)V(H)\equiv \exists f: V(G) \rightarrow V(H) bijekce tak, že u,vV(G):({u,v}E(G)    {f(n),f(v)}E(H))\forall u,v \in V(G): (\{u,v\} \in E(G) \iff \{ f(n), f(v) \} \in E(H))

\Downarrow Azˇ na jmeˊna vrcholu˚ se jednaˊ o stejnyˊ graf\text{Až na jména vrcholů se jedná o stejný graf}
izo1 izo2

Pozorování:
Na libovolné množině grafů je izomorfismus ( \cong) ekvivalence.

izo3


Stupeň vrcholu

Definice:
Stupeň vrcholu vv v grafy GG je

degG(v):={uv(G){u,v}E(G)}\deg_G(v) := |\{u \in v(G) | \{u,v\} \in E(G)\} | \Downarrow #hran vedoucıˊch z vrcholu v\#\text{hran vedoucích z vrcholu } v

Graf je kk-regulární (pro kNk \in \N) uV(G):degg(u)=k\equiv \forall u \in V(G): deg_g(u) = k
Graf je regulární k:G\equiv \exists k:G je kk-regulární


Skóre grafu

Definice:
Skóre grafu GG je posloupnost stupňů všech vrcholů (až na uspořádání)


Věta o principu sudosti

vVdeg(v)=2.E\sum_{v \in V} deg(v) = 2.|E|

Důsledky: vdeg(v)\sum_v deg(v) je sudé     #vV\implies \#v \in V lichého stupně je sudý


Věta o skóre

Posloupnost D=d1...dnD = d_1 \leq ... \leq d_n pro n2n \geq 2 je skóre grafu     D=d1...dn1\iff D' = d'_1 ... d'_{n -1} je skóre grafu:

Důkaz:
\Leftarrow nechť GG' je graf se skóre DD' a vrcholy v1...vn1v_1 ... v_{n-1}, tak že degG(vi)=di\forall \deg_G(v_i) = d_i vytvoří GG se skórem DD doplněním vrcholu VnV_n a hran {vi,vn}\{v_i,v_n\} pro i{ndn,...,n1}i \in \{n-d_n,..., n-1\}

Lemma: Nechť G\mathbb{G} je množina všech grafů se skóre DD vrcholech {1...n}\{1...n\} se skóre D,GGG:{v1,vi}E(G)D,\mathbb{G} \neq \emptyset \Rightarrow \exists G \in \mathbb{G}: \{v_1,v_i\} \in E(G) pro všechna i{ndn,n1}i \in \{n-d_n, n-1 \}

Důkaz lemma:
Pro GGG \in \mathbb{G} definujeme j(G):=max{j{Vj,Vn}E(G)}j(G):= \max\{j \mid \{ V_j, V_n\} \notin E(G) \}


Grafy na množině

Počet grafů na množině

Pro množinu vrcholů V:={1...n}V := \{1...n\} existuje:

#grafu˚(V,E)=2(n2)=2(n2)\# \text{grafů} (V,E) = \lvert 2^{\binom{n}{2}} \lvert = 2^{\binom{n}{2}}

kdy E(V2)E \subseteq \binom{V}{2}.

Počet tříd izomorfismu

Pro n=3n = 3 existují 4 grafy (mod\kern-1em\mod{} izomorfismus)

obrázek

Určit přesné množství tříd izomorfismu je obtížné, ale můžeme udělat spodní odhad. Protože třída isomorfismu může obsahovat maximálně n!n! grafů     \implies #\#Tříd izomorfismu je

2(n2)n!\geq \frac{2^{n \choose 2}}{n!}

Takže platí

2(n2)#Trˇıˊd izomorfismu2(n2)n!2^{n \choose 2} \geq \#\text{Tříd izomorfismu} \geq \frac{2^{n \choose 2}}{n!}

Což v logaritmickém měřítku je:

log2(2(n2)n!)log2(#Trˇıˊd izomorfismu)log2(2(n2))\log_2 \left(\frac{2^{n \choose 2}}{n!}\right) \leq \log_2 \left(\#\text{Tříd izomorfismu}\right) \leq \log_2 \left(2^{n \choose 2}\right) \Downarrow log2(2(n2))log2(n!)log2(#Trˇıˊd izomorfismu)(n2)\frac{\log_2 \left(2^{n \choose 2}\right)}{\log_2 (n!)} \leq \log_2({\#\text{Tříd izomorfismu}}) \leq {n \choose 2} \Downarrow n2nlognlog(#Trˇıˊd isomorfismu)n2\sim{n^2} - n\log n \leq \log({\#\text{Tříd isomorfismu}}) \leq \sim{n^2}

Podgrafy

Definice:
Graf G=(V,E)G' = (V',E') je podgrafem grafu G=(V,E)G=(V,E) (značíme jako GGG' \subseteq G) VVEE\equiv V' \subseteq V \land E' \subseteq E.

Indukovaný podgraf

Definice:
Graf G=(V,E)G' = (V',E') je indukovaným podgrafem G=(V,E)G=(V,E) (značíme jako G[V]G[V']) VVE=E(V2)\equiv V' \subseteq V \land E' = E \cap {V' \choose 2}

Čteme jako: Podgraf indukovaný množinou VVV' \subseteq V

Cesta v grafu

Cesta v grafu G=(V,E)G = (V,E) je:

  1. GG:GPnG' \subseteq G : G' \cong P_n pro nějaké nn
  2. (v0,e1,v1,e2,v2,...,en,vn)(v_0,e_1,v_1,e_2,v_2,...,e_n,v_n), kde:
    • v0...vnv_0 ... v_n, jsou navzájem různé
    • e1...ene_1 ... e_n jsou hrany
    • i:ei={vi1,vi}\forall i : e_i=\{v_{i-1},v_i\}
  3. Posloupnost vrcholů spojených postupně hranami

NENÍ posloupnost hran, kdy každá má s následující hranou společný vrchol.
Protipříklad:

Není cesta v grafu

Kružnice (cyklus) v grafu

  1. GG:GCnG' \subseteq G : G' \cong C_n pro nějaké nn
  2. (v0,e0,v1,e0,...,vn1en1,v0)(v_0, e_0, v_1, e_0, ...,v_{n-1} e_{n-1}, v_0)
    • v0...vn1v_0 ... v_{n-1} jsou navzájem různé
    • e0...en1e_0 ... e_{n-1} hran
    • ei={vi,v(i+1)modn}\forall e_i = \{v_i, v_{(i+1)\mod n}\}

Souvislý graf

Definice:
Graf GG je souvislý u,vV(G)\equiv \forall u,v \in V(G) \exists cesta v GG s krajními bodu u,vu,v

Dosažitelnost

Definice:
Dosažitelnost v GG je relace na V(G)V(G), taková že uvu \sim v \equiv cesta v GG s krajními vrcholy u,vu,v.

Lema:
Relace \sim je ekvivalence

Důkaz lematu:
Reflexivní: uvu \sim v: existuje triviální cesta
Symetrie: uvu \sim v: mezi uu a vv existuje cesta \equiv mezi vv a uu existuje cesta
Transitivita: uvvw    uwu \sim v \land v \sim w \implies u \sim w

Komponenty souvislosti

Definice:
Komponenty souvislosti jsou podgrafy indukované třídami ekvivalence \sim

Pozorování:


Procházení grafů

Sled

Sled (walk) - posloupnost (v0,e1,v1,e2,...,en,vn)i(v_0,e_1,v_1,e_2,...,e_n,v_n) \forall i ei={vi1,vi}e_i=\{v_{i-1},v_i \}
Libovolná posloupnost na sebe navazujících vrcholů a hran, ve které se může cokoli opakovat.

Tah

Tah je sled, kde se neopakují hrany

Cesta

Cesta je sled, kde se neopakují hrany ani vrcholy

Lemátko:
\exists cesta mezi u,v    u,v \iff \exists sled mezi u,vu,v

Důkaz:
\Rightarrow triviální
\Leftarrow uvažujme sled SS

  • kdyby se v SS neopakovaly vrcholy, je to cesta
  • pokud vk=vlv_k = v_l a k<lk < l tak:
    v0,e1,v1,...,ek,vk,ek+1,...,el,vl,el+1,...,en,vnv_0, e_1, v_1, ..., e_k, v_k, e_{k+1}, ...,e_l, v_l, e_{l+1}, ..., e_n,v_n
    \downarrow v0,e1,v1,...,ek,vk=vl,el+1,...,en,vnv_0, e_1, v_1, ..., e_k, v_k = v_l, e_{l+1}, ..., e_n,v_n
    Postupným vystříháváním cyklů vznikne cesta

Matice sousednosti

Definice:

Aij:={0jinak1pokud {vi,vj}E(G)A_{ij} := \left\{ \begin{array}{ll} 0 & \text{jinak} \\ 1 & \text{pokud } \{v_i,v_j\} \in E(G) \end{array} \right.

nebo

Aij:=[{vi,vj}E]A_{ij} := \left[\{v_i,v_j\} \in E \right]
obrázek grafu k matici     \implies v1v2v3v4v1v2v3v4[0110101011010010]\begin{array}{c c} & \begin{array}{c} v_1 \kern0.6em v_2 \kern0.6em v_3 \kern0.6emv_4 \\ \end{array} \\ \begin{array}{c c c} v_1 \\ v_2 \\ v_3 \\ v_4 \end{array} \kern-1.7em & \left[ \begin{array}{c c c c} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right] \end{array}

Pozorování:

Umocňování matice sousednosti

Aij2=(A.A)ij=kAik.AAkj=k[{vi,vk}E].[{vk,vj}E]A^2_{ij} = (A.A)_{ij} = \sum_k A_{ik} . A_{A_kj} = \sum_k [\{v_i,v_k\} \in E].[\{ v_k,v_j \} \in E] =#sledu˚ deˊlky 2 z vi do vj= \#\text{sledů délky } 2 \text{ z } v_i \text{ do } v_j

Lema:

Aijt=#sledu˚ deˊlky t z vi do vjA^t_{ij} = \#\text{sledů délky } t \text{ z } v_i \text{ do } v_j

Důkaz:

  1. t=1t = 1 -matice sousednosti - triviální
  2. tt+1:Ait+1j=(At.A)ij=kAiktAkj=k#t \rightarrow t+1: A^{t+1}_ij = (A^t.A)_{ij} = \sum_k A^t_{ik}A_{kj} = \sum_k \#sledů délky tt z viv_i do vkv_k

Počet trojúhelníků v grafu

#podgrafu˚ izomorfnıˊch s k3=#uzavrˇenyˊch sledu˚ deˊlky 3 z vi do vi=iAii36\#\text{podgrafů izomorfních s } k_3 = \#\text{uzavřených sledů délky } 3 \text{ z } v_i \text{ do } v_i = {\sum_i A^3_{ii} \over 6}


Grafová metrika

Definice:
Grafová metrika (vzdálenost) v souvislém grafu GG:

dG:V2Nd_G: V^2 \rightarrow \N
dG(u,v):=d_G(u,v) := minimum z délek (počet hran) cest mezi uu a vv

Lemma:

  1. dG(u,v)0d_G(u,v) \geq 0
  2. dG(u,v)=    u=vd_G(u,v) = \iff u = v
  3. dG(u,v)=dG(v,u)d_G(u,v) = d_G(v,u)
  4. \bigtriangleupnerovnost: dG(u,v)dG(u,w)+dG(w,v)d_G(u,v) \leq d_G(u,w) + d_G(w,v)

Grafové operace

Nechť G=(V,E)G=(V,E)

Pozorování:


Eulerovské grafy

Definice:
Eulerovský tah je takový, který obsahuje všechny vrcholy a hrany grafu.

Definice:
Graf je eulerovský \cong existuje v něm uzavřený eulerovský tah.

Věta o Eulerových grafech:
Graf GG je eulerovský     G\iff G je souvislý vV(G):degG(v)\land \forall v \in V(G): \deg_G(v) je sudý.

Důkaz:
    \implies souvislostí u,vV(G)\forall u,v \in V(G) \exists tah mezi u,v     \implies \forall cesta mezi u,vu,v

TT je uzavřený: Sporem:

  • nechť uu je jeden z konců tahu, který je nejdelší a otevřený
  • tah obsahuje lichý #\#hran incidetních s uu
  • uu má sudý deg(u)    \deg(u) \implies \exists nepoužitá hrana což je ve sporu s předpokladem, že je nejdelši možný \rightarrow Každý nejdelší tah je uzavřený.

TT je eulerovský:
a. pokud {u,v}e(G),u,vT\{u,v\} \in e(G), u,v \in T, pak {u,v}T\{u,v\} \in T
- kdyby to pro nějaké {u,v}\{u,v\} nebyla pravda (předpoklad a.), tak TT “rozpojíme” při některém z průchodů z uu: u,...uu,...u a nakonec přidáme {u,u},v\{u,u\},v \rightarrow delší tah a to je spor

b. TT obsahuje všechny vrcholy

  • když uV(b)uT\exists u \in V(b) \land u \notin T:
    1. tak zvolíme v vTv \in T libovolně
    2. pak díky souvislosti G    G \implies \exists cesta CC mezi uu,vv
    3. r\exists r a sC:rT,sT,{r,s}E(G)s \in C: r \in T, s \notin T, \{r,s\} \in E(G),
    4. TT rozpojíme v rr a prodloužíme {r,s},s    \{r,s\},s \implies delší tah a to je spor

Orientované grafy

Je normální graf akorát hrany jsou orientované dvojice vrcholů. Těmto orientovaným hranám se může říkat “šipky”. Matice sousednosti už nemusí být symetrická.

Definice:

EV2 {(x,x)xV}E \subseteq V^2 \ \{(x,x) \mid x \in V \}

Stupně vrcholu rozlišujeme na vstupní stupeň a výstupní stupeň.

Definice:
degin(v):=#u:(u,v)Edegout(v):=#w:(v,W)E\begin{aligned} \deg^{\text{in}}(v) &:= \#u: (u,v) \in E \\ \deg^{\text{out}}(v) &:= \#w: (v, W) \in E \end{aligned}

stupeň vrcholu orientovaneho grafu

Vyvážený orientovaný graf

Definice:
Graf je vyvážený vVdegin(v)=degout(v)\equiv \forall v \in V \deg^{\text{in}}(v) = \deg^{\text{out}}(v)

Podkladový graf

Definice:
Pro orientovaný graf G=(V,E)G = (V,E): podkladový graf G0=(V,E0)G^0 = (V,E^0), kde {u,v}E0(u,v)E(v,u)E\{u,v\} \in E^0 \equiv (u,v) \in E \lor (v,u) \in E.

(Prostě u hran grafu GG zapomeneme orientaci.)

Souvislost

Má dva pohledy:

  1. Slabá souvislost - Graf drží pohromadě
    • Definice: podkladový graf je souvislý
    • není možné množinu vrcholů rozdělit na dvě, aby mezi nimi neexistovala hrana.

graf drží pohromadě

  1. Silná souvislost - Dosažitelnost všude
    • Definice: u,vV\forall u,v \in V \exists orientovaná cesta z uu do vv
    • z každého vrcholu se dá po hranách přejít do jiného.
    • implikuje slabou souvislost

Pro neorientovaný graf platí obě, pro orientovaný už ne.

Polosouvislost

Definice:
u,vV(G)\forall u,v \in V(G) \exists cesta z uu do vv nebo z vv do uu.

polosouvislost

Věta o orientovaných grafech

Věta:
Následující vlastnosti orientovaného grafu GG jsou ekvivalentní:

  1. GG je vyvážený a slabě souvislý
  2. GG je euklidovský
  3. GG je vyvážený a silně souvislý

Důkaz:

  1.     \implies 1.
  2.     \implies 3.
    • vyváženost - triviální
    • silná souvislost - u,v\forall u,v \exists orientovaný tah uv    u \rightarrow v \implies \exists orientovaná cesta vuv \rightarrow u
  3.     \implies 2.
    • lehce upravíme důkaz pro neorientovaný graf.

Stromy

Definice:
Graf je GG je strom G\equiv G je souvislý \land acyklický. Ve V(G)V(G) je list degG(v)=1\equiv \deg_G(v) = 1

Strom výrazu Strom hierarchie království
strom výrazu strom hierarchie

Věta o charakterizaci stromů

Pro graf GG jsou následující tvrzení ekvivalentní:

  1. GG je souvislí a acyklický
  2. u,vV(G)!\forall u,v\in V(G) \exists! cesta mezi uu,vv v GG (jednoznačně souvislý)
  3. GG je souvislý a eE(G):Ge\forall e \in E(G): G-e není souvislý (minimálně souvislý)
  4. GG je acyklický a e(V(G)2)E(G+e)\forall e \in \binom{V(G)}{2} \setminus E(G + e) obsahuje cyklus (maximálně acyklický)
  5. GG je souvislý a E(G)=V(G)1\mid E(G) \mid = \mid V(G) \mid -1

Důkaz:
Pro nn: Každý graf s n=n\mid n \mid = n splňuje 1.     \implies 2.
Krok n1nn-1 \rightarrow n: Buď GG graf s nn vrcholy. Platí-li 1, GG je strom     l\implies \exists l (list) a ss (jediný soused) ll. GlG-l je také strom, má n1n-1 vrcholů     Gl\implies G - l je jednoznačně souvislý.

Jednoznačná souvislost GG: nechť u,vVu,v \in V \rightarrow

  • u,vlu,v \neq l
    • Přidáním listu nevzniká nová cesta
  • bez újmy na obecnosti u=l,vlu = l, v \neq l
    • cesta v..lv..l jde přes ss mezi v,s!v,s \exists! cesta (z indukčního předpokladu) a tujde rozšířit jedním způsobem a to přidáním hrany s,ls,l
  • u,v=lu,v = l
    • existuje jen jedna cesta
    1.     \implies 3. (indukce)
    1.     \implies 4. (indukce)
    1.     \implies 5. (indukce pro $$n=1: \lvert v \lvert = 1, \lvert E \lvert = 0)
    1.     \implies 1. (¬\neg1.     ¬\implies \neg2.)
    1.     \implies 1. (¬\neg1.     ¬\implies \neg3.)
    1.     \implies 1.
    1.     \implies 1.

Lemma:
Je-li GG strom na alespoň 2 vrcholech, GG má alespoň 2 listy.

Důkaz:
Uvažme nejdelší cestu ve stromu:

nejdelší cesta stromu

uu, vv jsou listy, protože kdyby uu nebyl list: t:{y,u}\exists t: \{y,u\} je hrana, která neleží na cestě:

  1. t,{u,t},Pt, \{u,t\}, P nejdelší cesta
  2. část cesty u...t+{t,u}u...t + \{t,u\} tvoří cyklus

Lemma:
Nechť vv je list grafu GG. Pak GG je strom     \iff GvG - v je strom.

Důkaz:
    \implies

  • GvG-v je souvislý (pokud mezi xx, yvy \neq v \exists cesta v GG, pak leží i v GvG-v)

Les

Graf GG je les G\equiv G je acyklický     G\iff G je les, když všechny jeho komponenty souvislosti jsou stromy.

Kostra grafu

Definice:
TGT \subseteq G je kostra grafu GTG \equiv T je strom V(T)=V(G)\land \lvert V(T) \lvert = \lvert V(G) \lvert

Větička:
Graf má kostru     \iff je souvislý

Důkaz:
\Rightarrow trivka
\Leftarrow Mažeme hrany na cyklech, dokud nevznikne strom.


Nakreslení grafu

Nakreslení do roviny

Věta: Hranice stěny souvislého topologického grafu je nakresnením uzavřeného sledu.

Důkaz:

  1. E=V1\lvert E \lvert = \lvert V \lvert -1, graf je strom - Platí
  2. indukční krok: Graf není strom. Nechť ee je hrana na kružnici     e\implies e odděluje 2 stěny.

indukce stěny

Pro G:=GeG' := G - e věta platí, o(e)s1s2o(e) \cup s_1 \cup s_2 je stěna \rightarrow je uzavřena na dvě části, kažkou uzavřeme hranou ee.

indukce steny indukce steny

Graf GG má rovinné nakreslení     \iff má nakreslení lomenými čarami.

Dělení hran zachochová rovinnost, kontrakce také: jeli GG roviný, pak GeG \setminus e také. Graf je rovinný, když jeho libovolné dělení je rovinný. Rovinný bude i po kontrakci hran také roviný.

dělení hran kontrakce hran

K5K_5 a K3,3K_{3,3} nejsou rovinné a jejich dělaní také ne. Pokud graf obsahuje K5K_5 nebo K3,3K_{3,3} jako podgraf, také není roviný.

Kuratovského věta

Graf není rovinný     \iff obsahuje podgraf izomorfní nějakéku dělení K5K_5 nebo K3,3K_{3,3}.

Jordanova věta o kružnici

Jeli cc topologická kružnice v R2\R^2, pak R2c\R^2 \setminus c má právě dvě komponenty obloukové souvislosti: omezenou a neomezenou a cc je jejich společnou hranicí.

Důsledek:
K5K_5 není rovinný.

K5 není rovinný

K3,3K_{3,3} je také nerovinný

Nakreslení na sféru

Věta
Graf má nakreslení na sféru     \iff má nakreslení do roviny.

Důkaz stereografickou projekcí
spojitá bijekce mezi sférou bez severního pólua R2\R^2

stereografie

Válcová plocha (plášť válce)

Totéž jako rovina

Nakreslení na torus

“Povrh pneumatiky”. Můžeme na něj nakreslit vše co do roviny ale opačně to neplatí.

Eulerova formule

Jeli graf GG nakreslený do roviny:

v+f=e+2v + f = e + 2

Důkaz:
1.GG je strom: víme, že v1=ev=e+1v-1 = e \rightarrow v = e + 1, f=1:v+f=v+1=e+2f=1 : v + f = v + 1 = e + 2

  1. indukční krok:
    Nechť ee je hrana na kružnici a G:=GeG' := G - e … paramatry:
    • v=vv' = v
    • e=e1e' = e - 1
    • f=f1f' = f -1
\Downarrow v+f=e+2v+f1=e1+2v+f=e+2\begin{aligned} v' + f' &= e' + 2 \\ v + f - 1 &= e - 1 + 2 \\ v + f &= e + 2 \end{aligned}

Důsledek:
Stěny jsou vlastnost nakreslení. Všechna nakreslení téhož grafu mají stejný počet stěn.

Maximální rovinný graf

Definice:
GG je maximální rovinný G\equiv G je rovinný e(V(G)2)E(G):G+e\land \forall e \in {V(G) \choose 2} \setminus E(G): G + e není rovinný.

Věta:
V nakreslení maximálně rovinného grafu s minimálně 3 vrcholy jsou všechny stěny trojúhelníky.

Důkaz:
Nechť GG je maximální rovinný topologický graf s nakreslením.

  1. kdy GG nebyl souvislý (můžeme přidat hrany mezi komponentami)
  2. kdyby \exists stěna ohraničeá CnC_n pro n>3n > 3 (u,v:=u,v := nesousední vrcholy stěny přidáme hranu {u,v}\{ u, v\} nakreslenou vnitřkem.)
  3. jinak jsou stěny ohraničené uzavřenými sledy co nejsou kružnice (opakuje se na něm vrchol vv) (svs-v má více komponent, u,w:=u,w := vrcholy různých komponent, lze přidat hranu {u,w}\{ u, w\} a to je spor)

Eulerova formule

Jeli graf GG nakreslený do roviny:

v+f=e+2v + f = e + 2

Důkaz:
1.GG je strom: víme, že v1=ev=e+1v-1 = e \rightarrow v = e + 1, f=1:v+f=v+1=e+2f=1 : v + f = v + 1 = e + 2

  1. indukční krok:
    Nechť ee je hrana na kružnici a G:=GeG' := G - e … paramatry:
    • v=vv' = v
    • e=e1e' = e - 1
    • f=f1f' = f -1
\Downarrow v+f=e+2v+f1=e1+2v+f=e+2\begin{aligned} v' + f' &= e' + 2 \\ v + f - 1 &= e - 1 + 2 \\ v + f &= e + 2 \end{aligned}

Pro triangulace a Eulerovy formule:

v+f=e+2v+23e=e+2v2=13e3v6=e\begin{aligned} v + f &= e + 2 \\ v + \frac{2}{3}e &= e + 2 \\ v - 2 &= \frac{1}{3}e \\ 3v - 6 &= e \end{aligned}

Věta:
Nechť GG je rovinný graf s aspoň 33 vrcholy, v=V(G),e=E(G)v = \lvert V(G) \lvert , e = \lvert E(G) \lvert.

Důkaz:
Nechť GG' (triangula grafu GG) je maximálně rovinny vzniklý z GG přidáváním hran. \downarrow
e=3v6e' = 3v' - 6
e3v6e' \geq 3v' - 6
v=vv' = v

Důsledky:


Barvení map

Sousední státy (Sousední stěny topologického rovinného grafu) mají mít různé barvy \rightarrow Problém čtyř barev

Chceme barvit vrcholy: f:V{1,...,k}tak,aby{u,v}E    f(u)f(v)f: V \rightarrow \{1,...,k\} tak, aby \{u,v\} \in E \implies f(u) \neq f(v)

Duální graf

G=(V,E)G = (V,E) se stěnami FG=(F,E)F \rightarrow G^*=(F,E^*)

{f1,f2}E    f1,f2\{f_1, f_2 \} \in E^* \iff f_1, f_2 sousedí v GG, ee se zachová:

VfV \leftrightarrow f

Duální graf

Obecně definováno na multigrafech.