Součin grafů

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Součin grafů je operace, která ze dvou grafů G1 a G2 vytvoří nový graf G, jehož množina vrcholů V(G) je V(G1)×V(G2), kartézský součin množin vrcholů násobených grafů. Jednotlivé druhy součinů se pak rozlišují podle toho, které hrany jsou ve výsledném grafu. Symboly operátorů jsou voleny tak, aby odpovídaly součinu dvou grafů K2.

Kartézský součin[editovat | editovat zdroj]

Značí se G1◻G2. Hranou jsou spojeny právě ty vrcholy, jejichž jedna souřadnice je shodná a druhá odpovídá hraně v příslušném grafu.

(a,c) \sim (b,d) \Leftrightarrow (a=b \and c \sim d) \or (a \sim b \and c=d)

Graph-Cartesian-product.svg

Tenzorový součin[editovat | editovat zdroj]

Značí se G1×G2. Hranou jsou spojeny právě ty vrcholy, jejichž jedna souřadnice je různá a druhá odpovídá hraně v příslušném grafu.

(a,c) \sim (b,d) \Leftrightarrow (a \sim b) \and (c \sim d)

Graph-tensor-product.svg

Úplný součin[editovat | editovat zdroj]

Značí se G1⊠G2. Hranou jsou spojeny právě ty vrcholy, jejichž nějaká souřadnice odpovídá hraně v příslušném grafu a druhá buď také, nebo odpovídá stejnému vrcholu.

(a,c) \sim (b,d) \Leftrightarrow ((a \sim b) \and (c \sim d)) \or ((a \sim b) \and (c = d)) \or ((a = b) \and (c \sim d) )