“Strong product of graphs”的意思、由来-开放百科全书

In graph theory, the strong product G ⊠ H of graphs G and H is a graph such that^[1]

The strong product is also called the normal product or the AND product.{{fact|reason=This seems a more likely name for the tensor product of graphs, which is sometimes called the strong graph product; the risk that this alternative name was misattributed raises the need for a source.|date=October 2017}} It was first introduced by Sabidussi in 1960.^[2] In that setting, the strong product is contrasted against a weak product, but the two are different only when applied to infinitely many factors.

For example, the king's graph, a graph whose vertices are squares of a chessboard and whose edges represent possible moves of a chess king, is a strong product of two path graphs.^[3]

Care should be exercised when encountering the term strong product in the literature, since it has also been used to denote the tensor product of graphs.^[4]

See also

References

1. ^{{citation |author1=Imrich, Wilfried |author2=Klavžar, Sandi |author3=Rall, Douglas F. | title = Graphs and their Cartesian Product | publisher = A. K. Peters | year = 2008 | isbn = 1-56881-429-1}}.
2. ^{{cite journal | author = Sabidussi, G. | title = Graph multiplication | journal = Math. Z. | volume = 72 | year = 1960 | pages = 446–457 |mr=0209177 | doi = 10.1007/BF01162967}}
3. ^{{citation | last1 = Berend | first1 = Daniel | last2 = Korach | first2 = Ephraim | last3 = Zucker | first3 = Shira | contribution = Two-anticoloring of planar and related graphs | contribution-url = http://www.emis.ams.org/journals/DMTCS/pdfpapers/dmAD0130.pdf | location = Nancy | mr = 2193130 | pages = 335–341 | publisher = Association for Discrete Mathematics & Theoretical Computer Science | series = Discrete Mathematics & Theoretical Computer Science Proceedings | title = 2005 International Conference on Analysis of Algorithms | year = 2005}}.
4. ^See page 2 of {{citation | first = László | last = Lovász | authorlink = László Lovász | title = On the Shannon Capacity of a Graph | journal = IEEE Transactions on Information Theory | volume = IT-25 | issue = 1 | year = 1979 | doi = 10.1109/TIT.1979.1055985}}.