Silně připojená součást

Orientovaný graf (digraf) se nazývá silně souvislý , jsou -li jakékoli dva jeho vrcholy s a t silně propojeny, tedy existuje-li směrovaná cesta z do  a současně vedená cesta z do

Silně propojené komponenty digrafu jsou jeho inkluze-maximální silně propojené podgrafy. Silně spojená oblast je množina vrcholů silně spojených komponent.

Definice

Digraf, který nepatří do třídy silně souvislých grafů, obsahuje nějakou množinu silně souvislých komponent a nějakou množinu orientovaných hran jdoucích z jedné komponenty do druhé.

Jakýkoli vrchol digrafu je pevně spojen sám se sebou.

Algoritmy

Nejjednodušší algoritmus pro řešení problému hledání silně propojených komponent v digrafu funguje následovně:

  1. Pomocí tranzitivního uzávěru zkontrolujeme, zda je dosažitelný z az pro všechny páry a
  2. Potom definujeme takový neorientovaný graf , který obsahuje hranu pro každý takový pár.
  3. Hledání souvislých komponent takového neorientovaného grafu dává silně propojené komponenty digrafu.

Je zřejmé, že hlavní doba běhu tohoto algoritmu je obsazena tranzitivním uzávěrem.

Existují také tři algoritmy, které řeší tento problém v lineárním čase, tedy V krát rychleji než výše uvedený algoritmus. Jedná se o algoritmy Kosaraju , hledání silně propojených komponent se dvěma zásobníky , a Tarjana .

Příklad

Obrázek ukazuje digraf, pro který jsou zobrazeny všechny tři silně propojené složky (stínované oblasti ohraničené tečkovanou čarou).

Viz také

Literatura