Nespojené spojení grafů - Disjoint union of graphs

A shlukový graf, disjunktní unie kompletní grafy

v teorie grafů, obor matematiky, disjunktní spojení grafů je operace, která kombinuje dvě nebo více grafy k vytvoření většího grafu. Je to analogické s disjunktní sjednocení množin, a je konstruováno tak, že vrcholová množina výsledku bude disjunktním spojením vrcholových sad daných grafů a hranová množina výsledku bude disjunktním spojením hranových sad daných grafů. Jakékoli disjunktní spojení dvou nebo více neprázdných grafů je nutně odpojen.

Zápis

Disjunktní unie se také nazývá součet grafu, a mohou být reprezentovány buď a znaménko plus nebo znaménko plus v kroužku: Pokud ${displaystyle G}$ a ${displaystyle H}$ jsou tedy dva grafy ${displaystyle G + H}$ nebo ${displaystyle Goplus H}$ označuje jejich disjunktní spojení.^[1]

Související třídy grafů

Určité speciální třídy grafů mohou být reprezentovány pomocí disjunktních sjednocujících operací. Zejména:

• The lesy jsou nesouvislé odbory stromy.^[2]
• The shlukové grafy jsou nesouvislé odbory kompletní grafy.^[3]
• The 2 pravidelné grafy jsou nesouvislé odbory cyklické grafy.^[4]

Obecněji řečeno, každý graf je disjunktním spojením spojené grafy, své připojené komponenty.

The cographs jsou grafy, které lze sestrojit z grafů s jedním vrcholem kombinací disjunktního spojení a doplněk operace.^[5]

Reference