Komponent grafu

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
Graf s tromi komponentami

Komponent grafu G je taký súvislý podgraf grafu G, ktorý nie je obsiahnutý v žiadnom väčšom súvislom podgrafe grafu G (maximálne súvislý podgraf).

Graf je súvislý, ak má práve jeden komponent.

Artikulácia[upraviť | upraviť zdroj]

Vrchol v\in V sa nazýva artikulácia, ak graf G - v má väčší počet komponentov ako graf G.

Vrchol neorientovaného grafu, z ktorého vychádzajú dve rôzne hrany, ktoré súčasne nepatria žiadnej kružnici grafu je artikulácia.


Most[upraviť | upraviť zdroj]

Hrana h\in H sa nazýva most, ak graf G - h má väčší počet komponentov ako graf G.

Príklad[upraviť | upraviť zdroj]

V tomto grafe je hrana 4-6 mostom a vrchol 4 artikuláciou.