Сильное произведение графов

Сильное произведение графов G и H — это граф, такой, что[1]:

  • множество вершин является прямым произведением
  • различные вершины (u,u' ) и (v,v' ) связаны ребром в тогда и только тогда, когда
    • u = v и u' смежна с v' , или
    • u' = v' и u смежна с v, или
    • u смежна с v и u' смежна с v' .
Граф ходов короля, сильное произведение двух путей

Сильное произведение является объединением прямого произведения и тензорного произведения.

Сильное произведение называется также нормальным произведением или AND произведением. Произведение вперве ввёл Сабидусси в 1960 году[2]. Сильное произведение контрастирует со слабым произведением, но эти два произведения отличаются, только если применяются к бесконечным графам.

Например, граф ходов короля, граф, в котором вершинами являются клетки шахматной доски, а рёбра представляют возможные ходы короля, является сильным произведением двух путей[3].

Следует проявлять осторожность, когда термин встречается в литературе, поскольку сильное произведение используется и для обозначения тензорного произведения[4].

См. также

Примечания

Литература

  • Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Graphs and their Cartesian Product. — A. K. Peters, 2008. — ISBN 1-56881-429-1.
  • Sabidussi, G. Graph multiplication // Math. Z.. — 1960. Т. 72. С. 446–457. doi:10.1007/BF01162967.
  • Daniel Berend, Ephraim Korach, Shira Zucker. Two-anticoloring of planar and related graphs // 2005 International Conference on Analysis of Algorithms. — Nancy: Association for Discrete Mathematics & Theoretical Computer Science, 2005. — С. 335–341. — (Discrete Mathematics & Theoretical Computer Science Proceedings).
  • László Lovász. On the Shannon Capacity of a Graph // IEEE Transactions on Information Theory. — 1979. Т. IT-25, вып. 1. doi:10.1109/TIT.1979.1055985.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.