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

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

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

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

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

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

Приклади

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

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

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

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

Властивості

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

(K₁ + K₂ + K₂^2) ${\displaystyle \square }$ (K₁ + K₂^3) = (K₁ + K₂^2 + K₂^4) ${\displaystyle \square }$ (K₁ + K₂), де знак плюс означає незв'язне об'єднання, а верхній індекс означає кратний декартів добуток.

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

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

χ(G ${\displaystyle \square }$ H)=max {χ(G), χ(H)}[8].

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

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

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

γ(G ${\displaystyle \square }$ H) ≥ γ(G)γ(H).

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

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

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

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

Історія

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

Примітки

1. Візінг використав термін «декартів добуток».
2. (Imrich, Peterin, 2007). Для раніших алгоритмів поліноміального часу див. статтю Фейгенбаума, Гершберґерґа і Шеффера (Feigenbaum, Hershberger, Schäffer, 1985), а також статтю Авренгаммера, Гаґаувера і Імріха (Aurenhammer, Hagauer, Imrich, 1992).
3. Hahn, Sabidussi, 1997.
4. Sabidussi, 1960.
5. Визинг, 1963.
6. Imrich, Klavžar, 2000.
7. Imrich, Klavžar, 2000, с. Theorem 4.19.
8. Sabidussi, 1957.
9. Kaveh, Rahami, 2005.

Література

• F. Aurenhammer, J. Hagauer, W. Imrich. Cartesian graph factorization at logarithmic cost per edge // Computational Complexity. — 1992. — Т. 2, вип. 4 (26 грудня). — С. 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 (26 грудня). — С. 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 (26 грудня). — С. 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 (26 грудня). — С. 377—388. — DOI:10.1002/cnm.753.
• G. Sabidussi. Graphs with given group and given graph-theoretical properties // Canadian Journal of Mathematics. — 1957. — Т. 9 (26 грудня). — С. 515—525. — DOI:10.4153/CJM-1957-060-7.
• G. Sabidussi. Graph multiplication // Mathematische Zeitschrift. — 1960. — Т. 72 (26 грудня). — С. 446—457. — DOI:10.1007/BF01162967.
• В. Г. Визинг. Декартово произведение графов // Вычислительные системы. — 1963. — Т. 9 (26 грудня). — С. 30—43.

Посилання

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