PROFILPELAJAR.COM

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

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

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

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

Приклади

Декартів добуток двох ребер є циклом з чотирма вершинами: 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.
Туровий граф є декартовим добутком двох повних графів.

Властивості

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

(K₁ + K₂ + K₂²)

\square

(K₁ + K₂³) = (K₁ + K₂² + K₂⁴)

\square

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

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

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

χ(G

\square

H)=max {χ(G), χ(H)}^[8].

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

α(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$ одиничну матрицю^[9].

Історія

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

Примітки

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

Література

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