Grafy

Note	Typy grafů, stromy, stupně vrcholů, orientované grafy, reprezentace grafů. Algoritmy prohledávání grafu do hloubky a do šířky a jejich využití. Komponenty souvislosti. IB000, IB002

Graf je uspořádaná dvojice $(V, E)$ , kde $V$ je množina vrcholů (uzlů, vertices) a $E$ je množina hran mezi vrcholy (edges).

V neorientovaném grafu je $E$ množina dvouprvkových podmnožin $V$ :

E \subseteq (2 V)

V orientovaném grafu je $E$ množina dvojic — relace na $V$ :

E \subseteq V \times V

Grafové pojmy

Stupeň vrcholu: U neorientovaných grafů je to počet hran vycházejících z vrcholu. U orientovaných rozlišujeme vstupní a výstupní stupeň.
Souvislost: Možnost pohybovat se v neorientovaném grafu po cestách. Ekvivalence těch dvojic vrcholů, kteréžto cestou propojeny jsou.
Slabá souvislost: Souvislost na orientovaných grafech, kde zanedbáváme směr hran.
Dosažitelnost směrem ven: Existuje vrchol, z nehož se dá dostat do všech ostatních.
Silná souvislost: Souvislost na orientovaných grafech, kde musí mezi vrcholy vést cesta tam i zpátky.
Komponenta souvislosti: Třídy ekvivalence souvislosti, resp. podgrafy indukované těmito třídami. Maximální oblasti grafu, kde se dá dostat všude.
Isomorfismus: Bijektivní zobrazení $f : V (G) \to V (H)$ takové, že každá dvojice vrcholů $u, v \in V (G)$ je spojena hranou v $G$ , právě tehdy kdy $f (u), f (v)$ v $H$ .
Podgraf grafu $G$: Libovolný graf $H$ takový, že $V (H) \subseteq V (G)$ , $E (H) \subseteq E (G)$ a $E (H)$ obsahuje hrany pouze mezi vrcholy z $V (H)$ . Píšeme $H \subseteq G$ .
Indukovaný podgraf: Podgraf $H \subseteq G$ takový, že $E (H)$ obsahuje všechny hrany z $G$ mezi vrcholy z $V (H)$ .
Acykličnost: Absence kružnic.

Typy grafů

d-regulární

Všechny vrcholy mají stejný stupeň.

Kružnice délky $n$

Má $n \geq 3$ různých vrcholů spojených v cyklu. Značí se $C_{n}$ .

Cesta délky $n \geq 0$

Má $n + 1$ různých vrcholů spojených "za sebou". Značí se $P_{n}$ .

Jednoduchá cesta

Cesta, která neobsahuje dva stejné vrcholy.

Úplný graf na $n \geq 1$

Má hrany mezi všemi vrcholy. Značí se $K_{n}$ .

Bipartitní graf

Vrcholy lze rozdělit na dvě skupiny, které mají hrany pouze mezi sebou, nikoliv mezi svými členy.

Úplný bipartitní graf na $m \geq 1$ a $n \geq 1$

Má $m + n$ vrcholů ve dvou skupinách. Hranami jsou spojeny všechny dvojice z různých skupin. Značí se $K_{m, n}$ .

Hvězda s $n \geq 1$ rameny

Úplný bipartitní graf $K_{1, n}$ .

Les

Acyklický graf. Nemusí být souvislý.

Strom

Souvislý, acyklický graf.

Pokud má víc než jeden vrchol, pak existuje vrchol se stupněm 1.
Strom na $n \geq 1$ má přesně $n - 1$ hran.
Mezi každými dvěma vrcholy vede právě jedna cesta.
Přidáním jedné nové hrany do stromu vznikne jedna kružnice.

Reprezentace grafů

Obrázkem pro lidi
Seznamem vrcholů a hran
Tabulkou (maticí z/do)

Průchod grafem

Do hloubky — Depth-First Search (DFS)

Prohledání po "slepých uličkách".
Dá se jednoduše zapsat rekurzivně, protože používá zásobník.
Používá při výpočtu topologického uspořádání uzlů, k nalezení silných komponent, zjištění přítomnosti cyklů, …

def dfs(graph: List[List[bool]], stamps: List[int], vertex: int) -> None:
    if stamps[vertex] == -1:
        stamps[vertex] = 0
    stamp = stamps[vertex]
    for i in range(0, len(graph)):
        if graph[vertex][i] and stamps[i] != -1:
            stamps[i] = stamp + 1
            dfs(graph, stamps, i)

Do šířky — Breadth-First Search (BFS)

Prohledávání po "vrstvách".
Nedá se jednoduše zapsat rekurzivně, protože používá frontu.
Používá se při hledání nejkratších cest. Součást Dijkstrova algoritmu.
Součást Jarníkova algoritmu na hledání minimální kostry grafu.

def bfs(graph: List[List[bool]], stamps: List[int], vertex: int) -> None:
    stamp = 0
    queue = deque()
    queue.append(vertex)
    while len(queue) > 0:
        current = queue.popleft()
        stamps[current] = stamp
        stamp += 1
        for i in range(0, len(graph)):
            if graph[current][i] and stamps[i] == -1:
                queue.append(i)