Součin grafů

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

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 \land c \sim d) \lor (a \sim b \land c=d)

Soubor:Graph-Cartesian-product.svg

Tenzorový součin

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) \land (c \sim d)

Soubor:Graph-tensor-product.svg

Úplný součin

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) \land (c \sim d)) \lor ((a \sim b) \land (c = d)) \lor ((a = b) \land (c \sim d) )

Externí odkazy

Kategorie:Grafové pojmy Kategorie:Binární operace