Produsul graficelor este o operație binară asupra graficelor . Mai precis, este o operație care mapează două grafice G 1 și G 2 la un grafic H cu următoarele proprietăți:
Următorul tabel prezintă cele mai frecvent utilizate produse grafice. În tabel înseamnă „conectat printr-o margine” și înseamnă „neconectat printr-o margine”. Simbolurile de operare prezentate mai jos nu înseamnă întotdeauna standardul, mai ales în lucrările anterioare.
Nume | Condiție pentru ( , ) ∼ ( , ). | Dimensiuni | Exemplu |
---|---|---|---|
produs cartezian |
( = și ) sau ( și = ) |
||
Produs tensor (produs categorial) |
și | ||
Lucrări lexicografice sau |
u 1 ∼ v 1 sau ( u 1 = v 1 și u 2 ∼ v 2 ) |
||
Produs puternic (produs normal) |
( u 1 = v 1 și u 2 ∼ v 2 ) sau ( u 1 ∼ v 1 și u 2 = v 2 ) sau ( u 1 ∼ v 1 și u 2 ∼ v 2 ) |
||
Produs conormal al graficelor (produs disjunct) |
u 1 ∼ v 1 sau u 2 ∼ v 2 |
||
Produs modular | și sau și |
||
produs rădăcină | vezi articolul | ||
produs Kronecker | vezi articolul | vezi articolul | vezi articolul |
Produs în zig-zag | vezi articolul | vezi articolul | vezi articolul |
Lucrări de înlocuire | |||
Produs omomorf [1] [2] [1] |
sau și |
În general, un produs grafic este definit de orice condiție pentru ( u 1 , u 2 ) ∼ ( v 1 , v 2 ) care poate fi exprimată în termenii afirmațiilor u 1 ∼ v 1 , u 2 ∼ v 2 , u 1 = v 1 și u 2 = v 2 .
Fie un grafic complet cu două vârfuri (adică o singură muchie). Produsele graficelor , , și arată exact ca semnul operației de înmulțire. De exemplu, este un ciclu de lungime 4 (pătrat) și este un grafic complet cu patru vârfuri. Notația pentru produsul lexicografic amintește de faptul că produsul nu este comutativ.