Produsul graficelor

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:

Mulțimea de vârfuri a graficului H este produsul direct V ( G 1 ) × V ( G 2 ), unde V ( G 1 ) și V ( G 2 ) sunt mulțimile de vârfuri ale lui G 1 și respectiv G 2 .
Două vârfuri ( u 1 , u 2 ) și ( v 1 , v 2 ) ale graficului H sunt legate printr-o muchie dacă și numai dacă vârfurile u 1 , u 2 , v 1 , v 2 îndeplinesc anumite condiții corespunzătoare produsului tip (vezi mai jos).

Tipuri de lucrări

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. $\sim$ $\nu \sim$

Nume	Condiție pentru ( , ) ∼ ( , ). $tu_{1}$ $u_{2)$ $v_{1}$ $v_{2}$	Dimensiuni	Exemplu
produs cartezian $G\H pătrat$	( = și ) sau $tu_{1}$ $v_{1}$ $u_{2)$ $\sim$ $v_{2}$ ( și = ) $tu_{1}$ $\sim$ $v_{1}$ $u_{2)$ $v_{2}$	$G_{V_{1},E_{1}}\square H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1}V_{2})}$
Produs tensor (produs categorial) $G\ ori H$	$tu_{1}$ $\sim$ $v_{1}$ și $u_{2)$ $\sim$ $v_{2}$	$G_{V_{1},E_{1}}\times H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(2E_{1}E_ {2})}$
Lucrări lexicografice sau $G\cdot H$ $G[H]$	u 1 ∼ v 1 sau ( u 1 = v 1 și u 2 ∼ v 2 )	$G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1}V_{2}^{2})}$
Produs puternic (produs normal) $G\boxtimes H$	( 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 )	$G_{V_{1},E_{1}}\boxtimes H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(V_{1}E_ {2}+V_{2}E_{1}+2E_{1}E_{2})}$
Produs conormal al graficelor (produs disjunct) $G*H$	u 1 ∼ v 1 sau u 2 ∼ v 2
Produs modular	${\displaystyle (u_{1}\sim v_{1))$ și sau $u_{2}\sim v_{2})$ ${\displaystyle (u_{1}\nu \sim v_{1))$ și $u_{2}\nu \sim v_{2})$
produs rădăcină	vezi articolul	$G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_ {1}+E_{1})}$
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] $G\ltimes H$	$(u_{1}=v_{1})$ sau și ${\displaystyle (u_{1}\sim v_{1))$ $u_{2}\nu \sim v_{2})$

Î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 .

Mnemonic

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. $K_{2}$ $K_{2}\square K_{2}$ $K_{2}\times K_{2)$ $K_{2}\boxtimes K_{2)$ $K_{2}\square K_{2}$ $K_{2}\boxtimes K_{2)$ $G[H]$

Vezi și

Operații pe grafice

Note

↑ 1 2 David E. Roberson, Laura Mancinska. Omomorfisme grafice pentru jucătorii cuantici . — 2012.
↑ R. Bačík, S. Mahajan. Calculatoare și combinatorică. - 1995. - T. 959. - P. 566, Programarea semidefinită și aplicațiile ei la problemele NP. — (Note de curs în Informatică). — ISBN 3-540-60216-X . - doi : 10.1007/BFb0030878 .

Literatură

Imrich, Wilfried; Klavzar, Sandi. Grafice de produs: Structură și recunoaștere . - Wiley, 2000. - ISBN 0-471-37039-8 . .