Produktet af grafer er en binær operation på grafer . Mere specifikt er det en operation, der kortlægger to grafer G 1 og G 2 til en graf H med følgende egenskaber:
Følgende tabel viser de mest brugte grafprodukter. I tabellen betyder "forbundet af en kant" og betyder "ikke forbundet med en kant". Betjeningssymbolerne nedenfor betyder ikke altid standarden, især i tidligere værker.
Navn | Betingelse for ( , ) ~ ( , ). | Dimensioner | Eksempel |
---|---|---|---|
Kartesisk produkt |
( = og ) eller ( og = ) |
||
Tensor-produkt (kategorisk produkt) |
og | ||
Leksikografisk arbejde el |
u 1 ∼ v 1 eller ( u 1 = v 1 og u 2 ∼ v 2 ) |
||
Stærkt produkt (normalt produkt) |
( u 1 = v 1 og u 2 ∼ v 2 ) eller ( u 1 ∼ v 1 og u 2 = v 2 ) eller ( u 1 ∼ v 1 og u 2 ∼ v 2 ) |
||
Konormalt produkt af grafer (Disjunkt produkt) |
u 1 ∼ v 1 eller u 2 ∼ v 2 |
||
Modulært produkt | og eller og |
||
rodprodukt | se artiklen | ||
Kronecker produkt | se artiklen | se artiklen | se artiklen |
Zigzag produkt | se artiklen | se artiklen | se artiklen |
Udskiftningsarbejde | |||
Homomorft produkt [1] [2] [1] |
eller og |
Generelt er et grafprodukt defineret ved en hvilken som helst betingelse for ( u 1 , u 2 ) ∼ ( v 1 , v 2 ), der kan udtrykkes i form af udsagn u 1 ∼ v 1 , u 2 ∼ v 2 , u 1 = v 1 og u 2 = v 2 .
Lad være en komplet graf med to spidser (det vil sige en enkelt kant). Produkterne af graferne , , og ligner nøjagtigt tegnet på multiplikationsoperationen. For eksempel er en cyklus med længde 4 (kvadratisk), og er en komplet graf med fire hjørner. Notationen for det leksikografiske produkt minder om, at produktet ikke er kommutativt.