Produs puternic al graficelor

Produsul puternic al graficelor G și H este un grafic astfel încât [1] : $G\boxtimes H$

mulţimea vârfurilor este un produs direct $G\boxtimes H$ $V(G)\time V(H)$
vârfurile distincte ( u,u' ) și ( v,v' ) sunt conectate printr-o muchie în dacă și numai dacă $G\boxtimes H$
- u = v și u' este adiacent cu v' , sau
- u' = v' și u este adiacent cu v , sau
- u este adiacent cu v și u' este adiacent cu v' .

Produsul puternic este unirea produsului direct cu produsul tensor .

Produsul puternic este denumit și produs normal sau produs ȘI . Produsul a fost introdus pentru prima dată de Sabidussi în 1960 [2] . Produsul puternic contrastează cu produsul slab , dar cele două produse diferă numai atunci când sunt aplicate la grafice infinite.

De exemplu, graficul mișcărilor regelui , un grafic în care vârfurile sunt celulele tablei de șah , iar muchiile reprezintă posibilele mișcări ale regelui, este un produs puternic a două căi [3] .

Trebuie avut grijă când termenul apare în literatură, deoarece produsul puternic este folosit și pentru a se referi la produsul tensor [4] .

Vezi și

Note

↑ Imrich, Klavžar, Rall, 2008 .
↑ Sabidussi, 1960 , p. 446–457.
↑ Berend, Korach, Zucker, 2005 , p. 335–341.
↑ Lovász, 1979 , p. 2.

Literatură

Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Grafice și produsul lor cartezian. - A. K. Peters, 2008. - ISBN 1-56881-429-1 .
Sabidussi, G. Înmulțirea grafică // Math. Z .. - 1960. - T. 72 . — S. 446–457 . - doi : 10.1007/BF01162967 .
Daniel Berend, Ephraim Korach, Shira Zucker. Two-anticoloring of planare and related graphs // 2005 International Conference on Analysis of Algorithms. - Nancy: Asociația pentru Matematică Discretă și Informatică Teoretică, 2005. - P. 335–341. — (Proceduri de matematică discretă și informatică teoretică).
Laszlo Lovasz. Despre capacitatea Shannon a unui grafic // Tranzacții IEEE pe teoria informației. - 1979. - T. IT-25 , nr. 1 . - doi : 10.1109/TIT.1979.1055985 .