Připojený graf

Souvislý graf  je graf , který obsahuje právě jednu souvislou složku . To znamená, že mezi libovolným párem vrcholů v tomto grafu existuje alespoň jedna cesta .

Příklady aplikací

Přímou aplikací teorie grafů je teorie sítí – a její aplikací je teorie elektronických sítí. Například všechny počítače připojené k internetu tvoří propojený graf, a přestože samostatná dvojice počítačů nemusí být přímo propojena (ve formulaci pro grafy nesmí být spojena hranou), informace lze přenášet z každého počítače do libovolného jiný (z libovolného vrcholu grafu existuje cesta k libovolnému jinému).

Konektivita pro orientované grafy

V orientovaných grafech se rozlišuje několik konceptů konektivity.

O orientovaném grafu se říká , že je silně souvislý , pokud má (nasměrovanou) cestu z libovolného vrcholu k jinému, nebo, ekvivalentně, graf obsahuje právě jednu silně souvislou složku .

Orientovaný graf se nazývá slabě souvislý , jde-li o souvislý neorientovaný graf získaný z něj nahrazením usměrněných hran neorientovanými.

Některá kritéria připojení

Zde jsou některé kriteriální (ekvivalentní) definice souvislého grafu:
Graf se nazývá jednoduše spojený (spojený) , pokud:

  1. Má jeden připojený komponent
  2. Existuje cesta z libovolného vrcholu do jakéhokoli jiného vrcholu
  3. Existuje cesta z daného vrcholu do jakéhokoli jiného vrcholu
  4. Obsahuje připojený podgraf, který zahrnuje všechny vrcholy původního grafu
  5. Obsahuje jako podgraf strom, který zahrnuje všechny vrcholy původního grafu (takový strom se nazývá spanning tree )
  6. Když jsou jeho vrcholy libovolně rozděleny do 2 skupin, vždy existuje alespoň 1 hrana spojující pár vrcholů z různých skupin

Viz také