Сильний добуток графів

Граф ходів короля, сильний добуток двох шляхів

Сильний добуток $G\boxtimes H$ графів G і H - це граф, такий, що:

• множина вершин $G\boxtimes H$ є прямим добутком $V(G)\times V(H)$
• різні вершини (u, u ') і (v, v') пов'язані ребром у $G\boxtimes H$ тоді і тільки тоді, коли
  • u = v і u' суміжна з v', або
  • u' = v' і u суміжна з v, або
  • u суміжна з v і u' суміжна з v'.

Сильний добуток є об'єднанням прямого добутку і тензорного добутку.

Сильний добуток називається також нормальним добутком або AND добутком. Добуток уперше ввів Сабідуссі 1960 року. Сильний добуток контрастує зі слабким добутком, але ці два добутки відрізняються, тільки якщо застосовуються до нескінченних графів.

Наприклад, граф ходів короля, граф, у якому вершинами є клітинки шахової дошки, а ребра представляють можливі ходи короля, є сильним добутком двох шляхів.

Слід бути обережним, коли термін зустрічається в літературі, оскільки назву сильний добуток використовують і для позначення тензорного добутку.

Див. також

• Добуток графів
• Прямий добуток графів
• Тензорний добуток графів

Література

• 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 (18 грудня). — С. 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 (18 грудня). — DOI:10.1109/TIT.1979.1055985.