Základní pojmy teorie grafů

Definice: Graf $G$ je dvojice $(V,E)$, kde $V$ je množina vrcholů a $E\subseteq \left(\genfrac{}{}{0ex}{}{V}{2}\right)$ je množina hran.

• $E(G)$ je značení množiny hran grafu $G$
• $V(G)$ je značení množiny vrcholů grafu $G$ Zajímavé typy grafů:
• úplný $K_n=\left(\{1,2,\dots ,n,(\genfrac{}{}{0ex}{}{V}{2})\}\right)$
• úplný bipartitní $K_{m,n}$:
  • $V(K_{m,n})=\{a_1,a_2,\dots ,a_m,b_1,b_2,\dots ,b_n\}$
  • $E(K_{m,n})=\{\{i,j\}|i\in \{a_1,a_2,\dots ,a_m\},j\in \{b_1,b_2,\dots ,b_n\}\}$
  • bipartitní graf je takový, který je podgrafem úplného bipartitního.
• cesta $P_n=\{\{1,2,\dots ,n\},\{\{i,i+1\}|0\le i<n\}\}$
• cyklus $C_n=\{\{1,2,\dots ,n\},\{\{i,(i+1)\text{ mod }n\}|0\le i<n\}\}$

Definice: Grafy $G$ a $H$ jsou izomorfní $G\cong H⟺f:V(G)\to V(H)$ bijekce taková, že $\forall u,v\in V(G)$ platí $\{u,v\}\in E(G)⟺\{f(u),f(v)\}\in E(H)$.

Definice: Graf $H$ je podgrafem grafu $G$ platí-li $V(H)\subseteq V(G)\wedge E(H)\subseteq E(G)\cap \left(\genfrac{}{}{0ex}{}{V(H)}{2}\right)$.

Definice: Graf $H$ je indukovaným podgrafem grafu $G$ platí-li $V(H)\subseteq V(G)\wedge E(H)=E(G)\cap \left(\genfrac{}{}{0ex}{}{V(H)}{2}\right)$.

Definice: Okolí vrcholu $v\in V(G)$ v grafu $G$ značíme $N(v)=\{u|\{u,v\}\in E(G)\}$. Definice: Stupeň vrcholu $v$ v grafu $G$ se rozumí přirozené číslo $k=\mathrm{deg}(v)=|N(v)|$.

Definice: Graf $G$ je $k$-regulární pro nějaké $k\in \mathbb{N}$, když stupeň všech vrcholů je alespoň $k$.

Definice: Doplněk grafu $G$ je graf $\overline{G}$, pro který platí $V(G)=V(\overline{G})$ a $(\forall u,v\in V(\overline{G}),u\ne v)(\{u,v\}\in E(\overline{G})⟺\{u,v\}\notin E(G))$.

Definice: Orientovaný graf $G$ je dvojice $(V(G),E(G))$, kde $V(G)$ je množina vrcholů a $E(G)$ je množina uspořádaných dvojic vrcholů a pro $(u,v)\in E(G)$ říkáme, že hrana vede z $u$ do $v$.

Definice: Multigraf je uspořádaná trojice $(V,E,K)$, kde:

• $V$ jsou neprázdné vrcholy
• $E$ jsou hrany
• $K$ je zobrazení $E\to \left(\genfrac{}{}{0ex}{}{V}{2}\right)\cup V$ (sjednocení kvůli existenci smyček)

Souvislost grafů

Definice: Graf $G$ je souvislý, právě tehdy když $\forall u,v\in V(G)$ existuje cesta z $u$ do $v$. Můžeme takto definovat relaci $\sim$ dosažitelnosti na vrcholech grafu $G$, která je ekvivalencí pro neorientované grafy. Tranzitivita se jen musí ošetřit, abychom měli jen cesty a ne sledy.

Definice: Komponenty souvislosti grafu $G$ jsou $V_1,V_2,\dots ,V_m\subseteq V(G)$, definované ekvivalenčními třídami na $V(G)$ promocí $\sim$.

Alternativně můžeme říci, komponenta souvislosti grafu je maximální souvislý podgraf, tj. v tomto podgrafu najdeme cestu z vrcholu $a$ do vrcholu $b$ pro jakékoliv vrcholy $a,b$ v podgrafu.

Jsou to všechny indukované podgrafy na jednotlivých třídách ekvivalence souvislosti. Je to souvislý podgraf, který není obsažen v žádném větším souvislém podgrafu. Souvislý graf má právě jednu komponentu.

Pro orientované grafy definujeme dvě souvislosti:

1. Silně souvislá komponenta je takový maximální podgraf orientovaného grafu, v němž pro každou dvojici vrcholů $u,v$ existuje sled.
2. Slabě souvislá komponenta je takový maximální podgraf orientovaného grafu, v němž pro každou dvojici vrcholů $u,v$ existuje sled alespoň v jednom směru.

Vzdálenost v grafu

Definice: Vzdálenost dvou vrcholů grafu $G$ je funkce $d:V(G)\times V(G)\to \mathbb{N}$, která je definována $\forall u,v\in V(G):d(u,v)=$ nejkratší cesta z $u$ do $v$.