Preskočiť na obsah

Súvislý graf

z Wikipédie, slobodnej encyklopédie

Neorientovaný graf sa nazýva súvislý, ak medzi ľubovolnými dvoma jeho vrcholmi existuje cesta.

Vrchol 0 nemá spoločnú hranu so zvyškom grafu, daný graf je teda nesúvislý.

Súvislý graf sa skladá z práve jedného komponentu.

Pre orientované grafy sú definované dva druhy súvislosti:

  • Orientovaný graf je slabo súvislý, ak jeho symetrizácia je súvislý graf.
  • Orientovaný graf je silno súvislý, ak pre každé dva vrcholy u a v existuje cesta z u do v aj cesta v do u.

Vlastnosti súvislých grafov

[upraviť | upraviť zdroj]
  • Každý súvislý graf G obsahuje vrchol v s vlastnosťou G - v (tzn. z grafu G odstraníme vrchol v) je súvislý graf
  • V súvislom grafu je m ≥ n - 1 (kde m je počet hrán a n je počet vrcholov)
  • Ak sú stupne všetkých vrcholov aspoň n/2 (kde n je počet vrcholov), potom je graf súvislý

Literatúra

[upraviť | upraviť zdroj]
  • Znám, Š: Kombinatorika a teória grafov. Bratislava, Matematicko-fyzikálna fakulta Univerzity Komenského. 1982, s. 39