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

бінарна операція на графах

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

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

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

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

ПрикладиРедагувати

  • Декартів добуток двох ребер є циклом з чотирма вершинами: K2   K2=C4.
  • Декартів добуток K2 і шляху є драбиною.
  • Декартів добуток двох шляхів є решіткою.
  • Декартів добуток n ребер є гіперкубом:
 
Таким чином, декартів добуток двох графів гіперкубів є іншим гіперкубом — Qi   Qj=Qi+j.
  • Декартів добуток двох медіанних графів є іншим медіанного графом.
  • Граф вершин і ребер n-кутної призми є декартовим добутком K2   Cn.
  • Туровий граф[ru] є декартовим добутком двох повних графів.

ВластивостіРедагувати

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

(K1 + K2 + K22)   (K1 + K23) = (K1 + K22 + K24)   (K1 + K2), де знак плюс означає незв'язне об'єднання, а верхній індекс означає кратний декартів добуток.

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

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

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

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

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

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

γ(G   H) ≥ γ(G)γ(H).

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

Алгебричну теорію графів можна використовувати для аналізу декартового добутку графів. Якщо граф   має   вершин і   матрицю суміжності  , а граф   має   вершин і   матрицю суміжності  , то матриця суміжності декартового добутку двох графів задається формулою

  ,

де   означає добуток Кронекера матриць, а   означає   одиничну матрицю[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 (18 листопада). — С. 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 (18 листопада). — С. 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.
  • 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 (18 листопада). — С. 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 (18 листопада). — С. 377—388. — DOI:10.1002/cnm.753.
  • G. Sabidussi. Graphs with given group and given graph-theoretical properties // Canadian Journal of Mathematics. — 1957. — Т. 9 (18 листопада). — С. 515—525. — DOI:10.4153/CJM-1957-060-7.
  • G. Sabidussi. Graph multiplication // Mathematische Zeitschrift. — 1960. — Т. 72 (18 листопада). — С. 446—457. — DOI:10.1007/BF01162967.
  • В. Г. Визинг. Декартово произведение графов // Вычислительные системы. — 1963. — Т. 9 (18 листопада). — С. 30—43.

ПосиланняРедагувати