Skip to content

1.3 Běžné grafy

Definice 1.5 (Úplný graf \(K_{n}\) Klika)

Úplný graf - Klika

  • Nechť \(n ≥ 1\).
  • Úplný graf na \(n\) vrcholech \(K_{n}\) je graf \((V, \binom{V}{2} )\), kde \(|V| = n\).

Definice 1.6 (Úplný bipartitní graf \(K_{n_{1},n_{2}}\))

Úplný bipartitní graf

  • Nechť \(n_{1} ≥ 1\) a \(n_{2} ≥ 1\).
  • Úplný bipartitní graf \(K_{n_{1},n_{2}}\) tvořený dvěma partitami o \(n_{1}\) a \(n_{2}\) vrcholech je graf \((A \cup B\), {{\(a\), \(b\)} | \(a \in A, b \in B\)}), kde \(A \cap B = \emptyset, |A| = n_{1}\) a \(|B| = n_{2}\).

Definice 1.7 (Cesta \(P_{n}\))

Cesta

  • Nechť \(n ≥ 1\).
  • Cesta s \(n\) vrcholy (s \(n − 1\) hranami) \(P_{n}\) je graf:
    ({\(1, . . . , n\)}, {{\(i, i + 1\)} | \(i \in\) {\(1, . . . , n − 1\)}}).

Definice 1.8 (Kružnice \(C_{n}\))

Kružnice

  • Nechť \(n ≥ 3\)
  • Kružnice délky \(n\) (s \(n\) vrcholy) \(C_{n}\) je graf ({\(1, . . . , n\)}, {{\(i, i + 1\)} | \(i \in\) {\(1, . . . , n − 1\)}} \(\cup\) {{\(n, 1\)}})

Definice 1.9 (Doplněk grafu)

Doplněk grafu

Doplněk \(\overline{G}\) grafu \(G = (V, E)\) je graf \((V, (\binom{V}{2}) \setminus E)\).

Definice 1.10 (Okolí vrcholu, stupeň vrcholu)

Okolí vrcholu a stupeň vrcholu

Nechť \(G = (V, E)\) je graf a \(v \in V\) jeho vrchol.

  • Symbolem \(deg_{G}(v)\) označíme počet hran grafu \(G\) obsahujících vrchol \(v\).
    Toto číslo nazveme stupněm vrcholu \(v\) v grafu \(G\).
  • Symbolem \(N_{G}(v)\) označíme množinu všech sousedů vrcholu \(v\) v grafu \(G\).
    Tuto množinu nazveme (otevřené) okolí vrcholu \(v\) v grafu \(G\).
  • Množinu \(N_{G}[v] = N_{G}(v) \cup \{v\}\) nazveme uzavřeným okolím vrcholu \(v\) v grafu \(G\).

Platí tedy \(deg_{G}(v) = |N_{G}(v)|\)

Definice 1.11 (Regulární graf)

Regulární graf

  • Graf je r-regulární, pokud stupeň každého jeho vrcholu je \(r\).
  • Graf je regulární, pokud je r-regulární pro nějaké \(r\).

Definice 1.12 (Izolovaný vrchol)

Izolovaný vrchol

  • Vrchol stupně \(0\) nazveme izolovaný (nemá žádné sousedy).

K zamyšlení

  • Jak vypadá 0-regulární graf o n vrcholech?
  • Jak vypadá 1-regulární graf o n vrcholech?
  • Existuje 1-regulární graf s lichým počtem vrcholů?
  • Jak vypadá 2-regulární graf o n vrcholech?
  • Existuje 2-regulární graf s lichým počtem vrcholů?
  • Kolik existuje neizomorfních 2-regulárních grafů o n vrcholech?

Věta 1.3 (O principu sudosti)

Věta o principu sudosti

Pro každý graf \(G = (V, E)\) platí:

\[ \sum_{v \in V}{deg_{G}(v) = 2|E|} \]
Důkaz Věty 1.3

Posčítáme-li stupně všech vrcholů, započítáme každou hranu přesně dvakrát, což dává součet \(2|E|\).

\[ \begin{align} & \sum_{v \in V}{deg_{G}(v)} = \sum_{v \in V}{|N_{G}(v)|} = \sum_{v \in V}{|\{u \in V | \{u,v\} \in E \}|} \\ \\ & = \sum_{v \in V}{|\{e \in E | v \in e \}|} = \sum_{v \in V}{}\sum_{e \in E | v \in e}{1} = \sum_{e \in E}{\sum_{v \in e}{1}} = \sum_{e \in E}{2} = 2 |E| \end{align} \]

Důsledek 1.1

Věta o principu sudosti má řadu důsledků.

  1. V každém grafu je počet vrcholů lichého stupně sudý.
  2. Každý regulární graf lichého stupně musí mít sudý počet vrcholů.

Definice 1.13 (Podgraf)

Podgraf

  • Graf \(H\) je podgrafem grafu \(G\), když \(V (H) \subseteq V (G)\) a \(E(H) \subseteq E(G)\).
  • Graf \(H\) je indukovaným podgrafem grafu \(G\), když \(V (H) \subseteq V (G)\) a \(E(H) = E(G) \cap \binom{V(H)}{2}\).
  • Je-li \(G = (V, E)\) a \(V' \subseteq V\) , pak \(G[V']\) označuje graf s množinou vrcholů \(V'\) a množinou hran \(E(G) \cap \binom{V'}{2}\).
    Říkáme, že \(G[V']\) je podgraf indukovaný množinou vrcholů \(V'\).
    Graf \(G[V \setminus V']\) budeme zapisovat zkráceně \(G − V'\).
    A speciálně, pokud \(V' = \{v\}\), pak píšeme \(G − v\) místo \(G − \{v\}\)

Definice 1.14 (Bipartitní graf)

Bipartitní graf

Podgraf úplného bipartitního grafu je bipartitní graf

Definice 1.15 (Klika v grafu \(G\))

Klika v grafu G

Klika v grafu G je podmnožina vrcholů, z nichž každé dva jsou sousední (čili spojeny hranou).

Definice 1.16 (Orientovaný graf)

Orientovaný graf

Orientovaný graf \(G\) je uspořádaná dvojice \((V, E)\), kde

  • \(V\) je neprázdná konečná množina vrcholů a
  • \(E\) je množina orientovaných hran (zobrazujeme jako šipky).

Orientovaná hrana \((u, v) \in E\) je uspořádaná dvojice vrcholů \(u, v \in V\) .
Říkáme, že \(u\) je předchůdce \(v\) a \(v\) je následník \(u\).
Říkáme, že orientovaná hrana \((u, u)\) je smyčka.