Декартів добуток графів

Декартів добуток графів

Декартів добуток або прямий добуток G $\square$ H графів G і H — це граф, такий, що

• множина вершин графу G $\square$ H — це декартів добуток V(G) × V(H)
• будь-які дві вершини (u, u') і (v, v') суміжні в G $\square$ H тоді і тільки тоді, коли
  • або u=v і u' суміжна v' в H
  • або u' =v' і u суміжна v в G.

Декартів добуток можна розпізнати ефективно за лінійний час. Операція є комутативною як операція на класах ізоморфізмів графів, і строгіше, графи G $\square$ H і H $\square$ G природно ізоморфні, але операція не є комутативною як операція на розмічених графах. Операція є також асоціативною, оскільки графи (F $\square$ G) $\square$ H і F $\square$ (G $\square$ H) природно ізоморфні.

Позначення G × H часом використовується і для декартового добутку графів, але частіше воно використовується для іншої конструкції, відомої як тензорний добуток графів. Символ квадратика частіше використовується і є недвозначним для декартового добутку графів. Він показує візуально чотири ребра, що виходять внаслідок декартового добутку двох ребер.

Приклади

• Декартів добуток двох ребер є циклом з чотирма вершинами: K₂ $\square$ K₂=C_4.
• Декартів добуток K₂ і шляху є драбиною.
• Декартів добуток двох шляхів є решіткою.
• Декартів добуток n ребер є гіперкубом:

$(K_{2})^{\square n}=Q_{n}.$

Таким чином, декартів добуток двох графів гіперкубів є іншим гіперкубом — Q_i $\square$ Q_j=Q_i+j.

• Декартів добуток двох медіанних графів є іншим медіанного графом.
• Граф вершин і ребер n-кутної призми є декартовим добутком K₂ $\square$ C_n.
• Туровий граф є декартовим добутком двох повних графів.

Властивості

Якщо зв'язний граф є декартовим добутком, його можна розкласти єдиним способом на добуток простих множників, графів, які не можна розкласти на добуток графів. Однак, Імріх і Клавжар описали незв'язний граф, який можна подати двома різними способами як декартовий добуток простих графів:

(K₁ + K₂ + K₂²) $\square$ (K₁ + K₂³) = (K₁ + K₂² + K₂⁴) $\square$ (K₁ + K₂), де знак плюс означає незв'язне об'єднання, а верхній індекс означає кратний декартів добуток.

Декартів добуток є вершинно-транзитивним графом тоді і тільки тоді, коли кожен з його множників є вершинно-транзитивним.

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

χ(G $\square$ H)=max {χ(G), χ(H)}.

Гіпотеза Хедетніємі стверджує пов'язану рівність для тензорного добутку графів. Число незалежності декартових добутків непросто обчислити, але, як показав Візінг, число незалежності задовольняє нерівностям

α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G $\square$ H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.

Гіпотеза Візінга стверджує, що число домінування декартового добутку задовольняє нерівності

γ(G $\square$ H) ≥ γ(G)γ(H).

Алгебрична теорія графів

Алгебричну теорію графів можна використовувати для аналізу декартового добутку графів. Якщо граф $G_{1}$ має $n_{1}$ вершин і $n_{1}\times n_{1}$ матрицю суміжності $\mathbf {A} _{1}$, а граф $G_{2}$ має $n_{2}$ вершин і $n_{2}\times n_{2}$ матрицю суміжності $\mathbf {A} _{2}$, то матриця суміжності декартового добутку двох графів задається формулою

$\mathbf {A} _{1\square 2}=\mathbf {A} _{1}\otimes \mathbf {E} _{n_{2}}+\mathbf {E} _{n_{1}}\otimes \mathbf {A} _{2}$ ,

де $\otimes$ означає добуток Кронекера матриць, а $\mathbf {E} _{n}$ означає $n\times n$ одиничну матрицю.

Історія

За Імріхом і Клавжару декартові добутки графів визначили 1912 року Вайтгед і Расселл. Добуток графів неодноразово перевідкривали пізніше, зокрема, Герт Сабідуссі.

Література

• F. Aurenhammer, J. Hagauer, W. Imrich. Cartesian graph factorization at logarithmic cost per edge // Computational Complexity. — 1992. — Т. 2, вип. 4 (10 листопада). — С. 331—349. — DOI:10.1007/BF01200428.
• Joan Feigenbaum, John Hershberger, Alejandro A. Schäffer. A polynomial time algorithm for finding the prime factors of Cartesian-product graphs // Discrete Applied Mathematics. — 1985. — Т. 12, вип. 2 (10 листопада). — С. 123—138. — DOI:10.1016/0166-218X(85)90066-6.
• Geňa Hahn, Gert Sabidussi. Graph symmetry: algebraic methods and applications. — Springer, 1997. — Т. 497. — С. 116. — (NATO Advanced Science Institutes Series) — ISBN 978-0-7923-4668-5. Архівовано з джерела 17 листопада 2021
• Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8.
• Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Graphs and their Cartesian Products. — A. K. Peters, 2008. — ISBN 1-56881-429-1.
• Wilfried Imrich, Iztok Peterin. Recognizing Cartesian products in linear time // Discrete Mathematics. — 2007. — Т. 307, вип. 3—5 (10 листопада). — С. 472—483. — DOI:10.1016/j.disc.2005.09.038.
• A. Kaveh, H. Rahami. A unified method for eigendecomposition of graph products // Communications in Numerical Methods in Engineering with Biomedical Applications. — 2005. — Т. 21, вип. 7 (10 листопада). — С. 377—388. — DOI:10.1002/cnm.753.
• G. Sabidussi. Graphs with given group and given graph-theoretical properties // Canadian Journal of Mathematics. — 1957. — Т. 9 (10 листопада). — С. 515—525. — DOI:10.4153/CJM-1957-060-7.
• G. Sabidussi. Graph multiplication // Mathematische Zeitschrift. — 1960. — Т. 72 (10 листопада). — С. 446—457. — DOI:10.1007/BF01162967.
• В. Г. Визинг. Декартово произведение графов // Вычислительные системы. — 1963. — Т. 9 (10 листопада). — С. 30—43.

Посилання

• Weisstein, Eric W. Декартів добуток графів(англ.) на сайті Wolfram MathWorld.