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₄.
Декартово произведение 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].

Гипотеза Хедетниеми утверждает связанное равенство для тензорного произведения графов. Число независимости декартовых произведений непросто вычислить, но, как показал Визинг^[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. — С. 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. — С. 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. — ISBN 978-0-7923-4668-5.
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. — С. 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. — С. 377—388. — doi:10.1002/cnm.753.
G. Sabidussi. Graphs with given group and given graph-theoretical properties // Canadian Journal of Mathematics. — 1957. — Т. 9. — С. 515—525. — doi:10.4153/CJM-1957-060-7.
G. Sabidussi. Graph multiplication // Mathematische Zeitschrift. — 1960. — Т. 72. — С. 446—457. — doi:10.1007/BF01162967.
В. Г. Визинг. Декартово произведение графов // Вычислительные системы. — 1963. — Т. 9. — С. 30—43.