Kaavioiden vahva tuote

Kaavioiden G ja H vahva tulo on sellainen graafi, jossa [1] : $G\boxtimes H$

kärkijoukko on suora tulo $G\boxtimes H$ ${\näyttötyyli V(G)\times V(H)}$
erilliset kärjet ( u,u' ) ja ( v,v' ) yhdistetään reunalla jos ja vain jos $G\boxtimes H$
- u = v ja u' on v' : n vieressä tai
- u' = v' ja u on v : n vieressä tai
- u on v :n vieressä ja u' on v:n vieressä .

Vahva tuote on suoratulon ja tensoritulon liitto .

Vahvaa tuotetta kutsutaan myös normaalituotteeksi tai AND-tuotteeksi . Sabidussi esitteli tuotteen ensimmäisen kerran vuonna 1960 [2] . Vahva tuote eroaa heikosta tuotteesta , mutta nämä kaksi tuotetta eroavat toisistaan vain, kun niitä käytetään äärettömiin kaavioihin.

Esimerkiksi kuninkaan liikkeiden kuvaaja, graafi, jossa kärjet ovat shakkilaudan soluja ja reunat edustavat kuninkaan mahdollisia liikkeitä, on kahden polun vahva tulo [3] .

On oltava varovainen, kun termi esiintyy kirjallisuudessa, sillä vahvaa tuotetta käytetään myös viittaamaan tensorituloon [4] .

Katso myös

Muistiinpanot

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

Kirjallisuus

Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Kaaviot ja niiden suorakulmainen tulo. - A. K. Peters, 2008. - ISBN 1-56881-429-1 .
Sabidussi, G. Graafin kertolasku // Math. Z .. - 1960. - T. 72 . — S. 446–457 . - doi : 10.1007/BF01162967 .
Daniel Berend, Ephraim Korach, Shira Zucker. Taso- ja niihin liittyvien graafien kaksinkertainen värjäys // 2005 International Conference on Analysis of Algorithms. - Nancy: Discrete Mathematics & Theoretical Computer Science, 2005. - S. 335–341. — (Discrete Mathematics & Theoretical Computer Science Proceedings).
László Lovasz. Kuvaajan Shannonin kapasiteetista // IEEE Transactions on Information Theory. - 1979. - T. IT-25 , no. 1 . - doi : 10.1109/TIT.1979.1055985 .