— —

Definice

Graf G je uspořádaná dvojice (V, E), kde V je libovolná konečná množina (obecněji zcela libovolná) a E ⊆ \binom{V}{2}.

Úplný graf (na n vrcholech):

K_{n} = (V, \binom{V}{2})

Kružnice:

C_{n} = ({v_{1}, …, v_{n}}, {{v_{1}, v_{2}}, {v_{2}, v_{3}}, …, {v_{n−1}, v_{n}}, {v_{n}, v_{1}}}) n ≥ 3

Cesta:

P_{n} = ({v_{0}, …, v_{n}}, {{v_{0}, v_{1}}, {v_{1}, v_{2}}, …, {v_{n−1}, v_{n}}})

Sled: v_{0}, e_{1}, v_{1}, e_{2}, …, e_{m}, v_{m}, kde e_{i} = {v_{i−1}, v_{i}}. (Cesta je tedy speciální druh sledu, kde jedním vrcholem neprojdeme vícekrát.)

Úplný bipartitní graf K_{n,m} = (V, E)

V = {u_{1}, …, u_{n}, v_{1}, …, v_{m}}
E = {{u_{i}, v_{j}} : i = 1, …, n; j = 1, …, m}
|V | = n + m, |E| = n · m

Příklad:

K_{2,3}:

*-“ * /-* “ X X / *-ˆ -*

Bipartitní graf

Graf G = (V, E) takový, že:

V = \underbrace{U ∪^{.} W}_{{V =U∪W, \atop U∩W =0}}

E ⊆ {{u, w} : u ∈ U, w ∈ W }

Isomorfismus

“Přejmenování vrcholů” G | G′ (G, G′ jsou izomorfní), pokud existuje bijekce f: V (G) ⟷^{1–1} V (G′) taková, že:

{x, y} ∈ E(G) ⇔ {f(x), f(y)} ∈ E(G′)

Pozn.: Izomorfismus je ekvivalence (reflexivní, symetrická, tranzitivní).

Podgraf: Graf G′ je podgrafem grafu G (G′ ⊆ G), pokud V (G′) ⊆ V (G) a E(G′) ⊆ E(G).

Indukovaný podgraf

— —

Graf G′ je indukovaným podgrafem grafu G, pokud V (G′) ⊆ V (G) a E(G′) = E(G) ∩ \binom{V (G′)}{2}.

Pozorování

Graf G na n vrcholech má 2^{n} indukovaných podgrafů (každá podmnožina V indukuje indukovaný podgraf).

Souvislý graf

Graf G je souvislý, pokud ∀x, y ∈ V (G) existuje v G cesta z x do y: x ∼_{G} y. ∼_{G} je ekvivalence na množině V (G).

DŮKAZ:

Reflexivita a symetrie je zřejmá.

Tranzitivita:

x ∼_{G} y ∧ y ∼_{G} z ⇒ ∃ sled z x do z

Nejkratší sled z x do z je cesta ⇒ x ∼_{G} z. Q.E.D.

Poznámka:

G souvislý ⇔ ∀x, y ∈ V (G) ∃ sled z x do y (v G)

Komponenta grafu G

Podgraf indukovaný třídami ekvivalence ∼_{G}. Pozn.: G souvislý ⇔ má jednu komponentu.

Vzdálenost v grafu

x, y ∈ V (G), d_{G}(x, y) = vzdálenost x, y v G = délka nejkratší cesty z x do y

Poznámka:

d_{G}(x, y) má vlastnosti metriky (vzdálenosti):

d_{G}(x, y) ≥ 0
d_{G}(x, y) = 0 ⇔ x = y
d_{G}(x, y) = d_{G}(y, x)
d_{G}(x, y) + d_{G}(y, z) ≥ d_{G}(x, z)

Sousedi v grafu: y je soused x v G, pokud {x, y} ∈ E(G) (⇔ d_{G}(x, y) = 1). Matice sousednosti:

G = (\{v_{1}, …, v_{n}\}, E) : A_{G} = (a_{i,j})_{i,j=1}^{n} , a_{i,j} = \{ \begin{matrix}1 & \{v_{i}, v_{j}\} ∈ E(G) \\ 0 & jinak \end{matrix}

Stupeň vrcholu: Stupeň vrcholu x v G jest deg_{G}(x) = deg(x) = počet hran obsahujících x = počet sousedů.