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

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

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

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

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

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

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

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

Див. також

Примітки

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

Література

  • 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 (15 січня). — С. 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 (15 січня). — DOI:10.1109/TIT.1979.1055985.