Skip to content

2.1 Souvislost grafů

Souvislost (neorientovaných) grafů

Definice 2.1 (Souvislost grafu)

Souvislost grafu

Graf \(G\) je souvislý, jestliže v něm pro každé jeho dva vrcholy \(u\), \(v\) existuje u-v-cesta.
Jinak je \(G\) nesouvislý.

Definice 2.2 (Souvislá komponenta)

Souvislá komponenta

Indukovaný podgraf \(H\) grafu \(G\) je souvislou komponentou, pokud:

  • je souvislý a
  • neexistuje žádný souvislý podgraf \(F\) , \(F \neq H\), grafu \(G\) takový, že \(H \subseteq F\).

Souvislá komponenta je tedy v inkluzi maximální souvislý podgraf grafu \(G\).

Pozorování

Graf je souvislý právě tehdy, když obsahuje jedinou souvislou komponentu.

Důkaz

  • \(\Rightarrow\)
    Sporem. Je-li souvislý, pak nemůže obsahovat více než jednu souvislou komponentu, protože vrcholy a hrany komponent jsou disjunktní, a pokud by existovaly alespoň dvě komponenty, pak by existovaly dva vrcholy v jednotlivých komponentách tak, že by mezi nimi neexistovala cesta, a tedy daný graf by nebyl souvislý.

  • \(\Leftarrow\)
    Obsahuje-li graf jedinou souvislou komponentu, pak je z definice komponenty souvislý.

Tvrzení

Binární relace \(\leftrightsquigarrow\) nad vrcholy grafu \(G\) definovaná předpisem

\[ u \leftrightsquigarrow v \iff \exists\text{ } u\text{-}v\text{-cesta v } G \]

je ekvivalence, jejíž třídy ekvivalence indukují souvislé komponenty grafu \(G\).

Souvislost orientovaných grafů

  • Pojmy souvislost a souvislá komponenta neorientovaných grafů nelze jednoduše použít pro orientované grafy.

Definice 2.3 (Symetrizace orientovaného grafu)

Symetrizace orientovaného grafu

Symetrizace orientovaného grafu \(G = (V, E)\) je neorientovaný graf

sym\((G) = (V, E')\), kde:
\(\phantom{XXXX}\{u, v\} \in E'\) právě tehdy, když \((u, v) \in E\) nebo \((v, u) \in E\).

Symetrizace tedy odstraní z grafu informace o orientaci hran.

Definice 2.4 (Slabá souvislost orientovaného grafu)

Slabá souvislost orientovaného grafu

Orientovaný graf \(G = (V, E)\) nazveme slabě souvislý, pokud je souvislá jeho symetrizace sym\((G)\).

Testovat slabou souvislost orientovaného grafu tedy znamená testovat, např. pomocí algoritmu BFS, souvislost jeho symetrizace, což je neorientovaný graf.

Definice 2.5 (Silná souvislost orientovaného grafu)

Silná souvislost orientovaného grafu

Orientovaný graf \(G = (V, E)\) nazveme silně souvislý, pokud pro každé dva vrcholy \(u, v \in V\) existuje v \(G\) orientovaná cesta z \(u\) do \(v\) a současně orientovaná cesta z \(v\) do \(u\).

Vyšetřování souvislosti grafu

Úloha vyšetřování souvislosti grafu \(G\) má různé podoby, např.:

  1. Zjistit, zda je \(G\) souvislý.
  2. Pokud není, identifikovat všechny souvislé komponenty.
  3. Je-li zadán vrchol \(s\), zkonstruovat souvislou komponentu, do které \(s\) patří.

Vstup: Graf \(G\).
Výstup: Graf \(s\) označenými souvislými komponentami.

Algoritmus 2.1 (BFS_graf)

BFS_graf

Algoritmus BFS_graf (graf G):
1
2
3
4
5
6
Pro každý vrchol u ∈ V (G):
    stav[u] := nenalezený
    D[u] := P[u] := undef
Pro každý vrchol s ∈ V (G):
    Pokud stav[s] = nenalezený:
        BFS(G, s)
BFS(graf G, vrchol s):
 7
 8
 9
10
11
12
13
14
15
16
Q := fronta obsahující s
stav[s] := otevřený, D[s] := 0, P[s] := ⊥
Dokud je fronta Q neprázdná:
    Odeber z Q první vrchol → v
    Pro všechny sousedy w vrcholu v:
        Pokud stav[w] = nenalezený:
            stav[w]:= otevřený
            D[w]:= D[v]+1, P[w]:= v
            Přidej w na konec Q
    stav[v] := uzavřený

Vstup: Graf \(G\) a jeden jeho vrchol \(s\).
Výstup: Graf \(s\) označenou souvislou komponentou, ve které leží vrchol \(s\).

Algoritmus 2.2 (DFS_graf)

DFS_graf

Algoritmus DFS_graf (graf G, vrchol s):
1
2
3
Pro každý vrchol u ∈ V (G):
    stav[u] := nenalezený
DFS(s)
DFS (vrchol v):
4
5
6
7
8
9
Pokud stav[v] = otevřený nebo uzavřený:
    return
stav[v] := otevřený
Pro každého souseda u vrcholu v:
    DFS(u)
stav[v] := uzavřený