Прямое произведение графов

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Декартово произведение графов.

Декартово произведение или прямое произведение [1] G [math]\displaystyle{ \square }[/math] H графов G и H — это граф, такой, что

  • множество вершин графа G [math]\displaystyle{ \square }[/math] H — это прямое произведение V(G) × V(H)
  • любые две вершины (u,u') и (v,v') смежны в G [math]\displaystyle{ \square }[/math] H тогда и только тогда, когда
    • либо u=v и u' смежна v' в H
    • либо u' =v' и u смежна v в G.

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

Обозначение G × H порой используется и для декартова произведения графов, но чаще оно используется для другой конструкции, известной как тензорное произведение графов. Символ квадратика чаще используется и является недвусмысленным для декартова произведения графов. Он показывает визуально четыре ребра, получающиеся в результате декартова произведения двух рёбер[3]

Примеры

  • Декартово произведение двух рёбер является циклом с четырьмя вершинами: K2 [math]\displaystyle{ \square }[/math] K2=C4.
  • Декартово произведение K2 и пути является лестницей.
  • Декартово произведение двух путей является решёткой.
  • Декартово произведение n рёбер является гиперкубом:
[math]\displaystyle{ (K_2)^{\square n}=Q_n. }[/math]
Таким образом, декартово произведение двух графов гиперкубов является другим гиперкубом — Qi [math]\displaystyle{ \square }[/math] Qj=Qi+j.

Свойства

Если связный граф является декартовым произведением, его можно разложить единственным образом на произведение простых множителей, графов, которые нельзя разложить на произведение графов [4][5]. Однако, Имрих и Клавжар[6] описали несвязный граф, который можно представить двумя различными путями как декартово произведение простых графов:

(K1 + K2 + K22) [math]\displaystyle{ \square }[/math] (K1 + K23)=(K1 + K22 + K24) [math]\displaystyle{ \square }[/math] (K1 + K2),

где знак плюс означает несвязное объединение, а верхний индекс означает кратное декартово произведение.

Декартово произведение является вершинно-транзитивным графом тогда и только тогда, когда каждое из его множителей является вершинно-транзитивным[7].

Декартово произведение является двудольным тогда и только тогда, когда каждый из его множителей является двудольным. Более обще, хроматическое число декартова произведения удовлетворяет уравнению

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

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

α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G [math]\displaystyle{ \square }[/math] H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.

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

γ(G [math]\displaystyle{ \square }[/math] H) ≥ γ(G)γ(H).

Алгебраическая теория графов

Алгебраическую теорию графов можно использовать для анализа декартова произведения графов. Если граф [math]\displaystyle{ G_1 }[/math] имеет [math]\displaystyle{ n_1 }[/math] вершин и [math]\displaystyle{ n_1\times n_1 }[/math] матрицу смежности [math]\displaystyle{ \mathbf A_1 }[/math], а граф [math]\displaystyle{ G_2 }[/math] имеет [math]\displaystyle{ n_2 }[/math] вершин и [math]\displaystyle{ n_2\times n_2 }[/math] матрицу смежности [math]\displaystyle{ \mathbf A_2 }[/math], то матрица смежности декартова произведения двух графов задаётся формулой

[math]\displaystyle{ \mathbf A_{1\square 2}=\mathbf A_1 \otimes \mathbf E_{n_2} + \mathbf E_{n_1} \otimes \mathbf A_2 }[/math],

где [math]\displaystyle{ \otimes }[/math] означает произведение Кронекера матриц, а [math]\displaystyle{ \mathbf E_n }[/math] означает [math]\displaystyle{ n\times n }[/math] единичную матрицу[9].

История

Согласно Имриху и Клавжару[6] декартовы произведения графов определили в 1912 Уайтхед и Рассел. Произведение графов неоднократно переоткрывалось позже, в частности, Гертом Сабидусси[4].

Примечания

  1. ↑ Визинг использовал термин «декартово произведение», в статье «Прямое произведение» то же произведение называется прямым.
  2. ↑ (Imrich, Peterin 2007). Для более ранних алгоритмов полиномиального времени см. статью Фейгенбаума, Хершбергерга и Шеффера (Feigenbaum, Hershberger, Schäffer 1985), а также статью Ауренхаммера, Хагауэра и Имриха(Aurenhammer, Hagauer, Imrich 1992).
  3. ↑ Hahn, Sabidussi, 1997.
  4. ↑ 4,0 4,1 Sabidussi, 1960.
  5. ↑ 5,0 5,1 Визинг, 1963.
  6. ↑ 6,0 6,1 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. — С. 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.

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Прямое_произведение_графов&oldid=5812421