Сильний добуток графів G і H - це граф, такий, що:
- множина вершин є прямим добутком
- різні вершини (u, u ') і (v, v') пов'язані ребром у тоді і тільки тоді, коли
- u = v і u' суміжна з v', або
- u' = v' і u суміжна з v, або
- u суміжна з v і u' суміжна з v'.
Сильний добуток є об'єднанням прямого добутку і тензорного добутку.
Сильний добуток називається також нормальним добутком або AND добутком. Добуток уперше ввів Сабідуссі 1960 року. Сильний добуток контрастує зі слабким добутком, але ці два добутки відрізняються, тільки якщо застосовуються до нескінченних графів.
Наприклад, граф ходів короля, граф, у якому вершинами є клітинки шахової дошки, а ребра представляють можливі ходи короля, є сильним добутком двох шляхів.
Слід бути обережним, коли термін зустрічається в літературі, оскільки назву сильний добуток використовують і для позначення тензорного добутку.
Див. також
Примітки
- Imrich, Klavžar, Rall, 2008.
- Sabidussi, 1960, с. 446–457.
- Berend, Korach, Zucker, 2005, с. 335–341.
- Lovász, 1979, с. 2.
Література
- Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Graphs and their Cartesian Product. — A. K. Peters, 2008. — .
- Graph multiplication // Math. Z.. — 1960. — Т. 72 (17 липня). — С. 446–457. — DOI: .
- 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 (17 липня). — DOI: .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Silnij dobutok G H displaystyle G boxtimes H grafiv G i H ce graf takij sho mnozhina vershin G H displaystyle G boxtimes H ye pryamim dobutkom V G V H displaystyle V G times V H rizni vershini u u i v v pov yazani rebrom u G H displaystyle G boxtimes H todi i tilki todi koli u v i u sumizhna z v abo u v i u sumizhna z v abo u sumizhna z v i u sumizhna z v Graf hodiv korolya silnij dobutok dvoh shlyahiv Silnij dobutok ye ob yednannyam pryamogo dobutku i tenzornogo dobutku Silnij dobutok nazivayetsya takozh normalnim dobutkom abo AND dobutkom Dobutok upershe vviv Sabidussi 1960 roku Silnij dobutok kontrastuye zi slabkim dobutkom ale ci dva dobutki vidriznyayutsya tilki yaksho zastosovuyutsya do neskinchennih grafiv Napriklad graf hodiv korolya graf u yakomu vershinami ye klitinki shahovoyi doshki a rebra predstavlyayut mozhlivi hodi korolya ye silnim dobutkom dvoh shlyahiv Slid buti oberezhnim koli termin zustrichayetsya v literaturi oskilki nazvu silnij dobutok vikoristovuyut i dlya poznachennya tenzornogo dobutku Div takozhDobutok grafiv Pryamij dobutok grafiv Tenzornij dobutok grafivPrimitkiImrich Klavzar Rall 2008 Sabidussi 1960 s 446 457 Berend Korach Zucker 2005 s 335 341 Lovasz 1979 s 2 LiteraturaWilfried Imrich Sandi Klavzar Douglas F Rall Graphs and their Cartesian Product A K Peters 2008 ISBN 1 56881 429 1 Graph multiplication Math Z 1960 T 72 17 lipnya S 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 amp Theoretical Computer Science 2005 S 335 341 Discrete Mathematics amp Theoretical Computer Science Proceedings Laszlo Lovasz On the Shannon Capacity of a Graph IEEE Transactions on Information Theory 1979 T IT 25 vip 1 17 lipnya DOI 10 1109 TIT 1979 1055985