Zpět na stránku cvika

7. cvičení

Definice. Řekneme, že $G(V,E)$ je izomorfní $H(V',E')$ právě když existuje $f:V\rightarrow V'$: $f$ je bijekce a pro každé $u,w \in V$ platí $(u,w)\in E$ právě když $(f(u),f(w))\in E'.$

Definice. Isomorfismus grafu sama do sebe nazveme automorfismus.

Definice. Řekneme, že $G(V,E)$ je podgraf grafu $H(V',E')$, pokud $V\subseteq V'$ a $E \subseteq E'$ (a $G$ je stále graf, tedy $E$ nemůže obsahovat hrany k vrcholům, které nejsou v $V$).

Definice. Řekneme, že $G(V,E)$ je indukovaný podgraf grafu $H(V',E')$, pokud je to podgraf a současně "obsahuje všechny hrany které může", neboli $E=\{(u,v)\mid(u,v)\in E' \wedge u\in V \wedge v\in V\}$.

Definice. Řekneme, že $G(V,E)$ je souvislý, pokud mezi libovolnými dvěma jeho vrcholy existuje cesta.

Definice. Řekneme, že $G(V,E)$ je strom, pokud je souvislý a současně neobsahuje kružnici jako podgraf.

Definice. Řekneme, že $G(V,E)$ je les, pokud neobsahuje kružnici jako podgraf.

Definice. Řekneme, že vrchol je list, má-li stupeň 1. Řekneme, že vrchol je izolovaný, má-li stupeň 0.

Věta. Každý strom o alespoň dvou vrcholech má alespoň 2 listy.

Definice. Doplněk grafu $G(V,E)$ je graf $\overline G(V,E')$ na těch samých vrcholech takový, že $E' = \{\{u,v\}\mid \{u,v\} \notin E\}$.

Příklad 1. Charakterizujte všechny grafy, které neobsahují cestu na třech vrcholech jako svůj indukovaný podgraf.

Příklad 2. Dokažte, že když jsou dva grafy izomorfní, jsou izomorfní i jejich doplňky.

Příklad 3. Mějme graf o $n$ vrcholech a $k$ komponentách souvislosti. Kolik nejméně a nejvíce hran může tento graf mít?

Příklad 4. Na množině $[n]$ určete počet různých (ač samozřejmě izomorfních):

  1. Úplných grafů,
  2. Cest,
  3. Grafů, kde mají všechny vrcholy stupeň 1,
  4. Úplných bipartitních grafů $K_{k,n-k}$ pro nějaké pevné $k$.

Příklad 5. Pro každé $n\in \mathbb N$ najděte graf s právě $n$ automorfismy.

Příklad 6. Mějme strom $G$ na alespoň dvou vrcholech a jebo vrchol $v$. Dokažte, že $G$ má alespoň $deg(v)$ listů.

Příklad 7. Mějme strom $G(V,E)$ a nějaký jeho automorfismus $f$. Dokažte, že buď existuje vrchol $v$ takový, že $f(v)=v$, nebo dva vrcholy $u$, $v$ takové, že $f(u)=v$ a $f(v)=u$.

Zobraz nápovědu Skryj nápovědu

Hledejte $u$ a $v$ takové, že $\{u,v\}\in E$.

Příklad 8. Mějme strom $G$ a několik (alespoň 2) jeho souvislé podgrafy $G_1(V_1,E_1),G_2(V_2,E_2),\dots,G_n(V_n,E_n)$. Dokažte,

  1. Že průnik všech $G_i$ je buď strom nebo prázdný graf.
  2. Že když pro každé dvě $k$, $\ell$ platí, že $V_k\cap V_\ell \neq \emptyset$, pak také $$\bigcap_{i=1}^{n}V_i\neq\emptyset.$$
  3. Že kdyby $G$ nemusel být strom, předchozí tvrzení nemusí platit.