Декартово произведение графов

Операция в теории графов

Декартово произведение двух графов

В теории графов декартово произведение G □ H графов G и H — это граф, такой что :

• множество вершин G □ H является декартовым произведением V ( G ) × V ( H ) ; и
• две вершины ( u , v ) и ( u' , v' ) являются смежными в G □ H тогда и только тогда, когда либо
  • u = u' и v смежна с v' в H , или
  • v = v' и u смежна сu ' в G.

Декартово произведение графов иногда называют ящичным произведением графов [Harary 1969].

Операция ассоциативна , поскольку графы ( F □ G ) □ H и F □ ( G □ H ) естественно изоморфны . Операция коммутативна как операция над классами изоморфизма графов, и, что более строго, графы G □ H и H □ G естественно изоморфны , но она не коммутативна как операция над помеченными графами .

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

Примеры

• Декартово произведение двух ребер представляет собой цикл на четырех вершинах: K ₂ □ K ₂ = C ₄ .
• Декартово произведение K2 _и графа путей является лестничным графом .
• Декартово произведение двух графов путей представляет собой решетчатый граф .
• Декартово произведение n ребер представляет собой гиперкуб:

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

Таким образом, декартово произведение двух графов гиперкуба представляет собой еще один гиперкуб: Q _i □ Q _j = Q _i+j .

• Декартово произведение двух медианных графов — это еще один медианный граф.
• Граф вершин и ребер n- призмы — это граф декартова произведения K ₂ □ C _n .
• Граф ладьи представляет собой декартово произведение двух полных графов.

Характеристики

Если связный граф является декартовым произведением, его можно однозначно разложить на множители как произведение простых множителей, графов, которые сами по себе не могут быть разложены как произведения графов. ^[2] Однако Имрих и Клавжар (2000) описывают несвязный граф, который можно выразить двумя различными способами как декартово произведение простых графов:

${\displaystyle (K_{1}+K_{2}+K_{2}^{2})\mathbin {\square } (K_{1}+K_{2}^{3})=(K_{1}+K_{2}^{2}+K_{2}^{4})\mathbin {\square } (K_{1}+K_{2}),}$

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

${\displaystyle {\begin{aligned}(1+x+x^{2})(1+x^{3})&=(1+x^{2}+x^{4})(1+x)\\&=1+x+x^{2}+x^{3}+x^{4}+x^{5}\\&=(1+x)(1+x+x^{2})(1-x+x^{2})\end{aligned}}}$

Оба фактора и не являются неприводимыми многочленами , но их факторы включают отрицательные коэффициенты, и, таким образом, соответствующие графы не могут быть разложены. В этом смысле неудача уникальной факторизации на (возможно, несвязных) графах сродни утверждению, что многочлены с неотрицательными целыми коэффициентами являются полукольцом , которое не удовлетворяет свойству уникальной факторизации . ${\displaystyle 1+x^{3}}$ ${\displaystyle 1+x^{2}+x^{4}}$

Декартово произведение вершинно транзитивно тогда и только тогда, когда каждый из его множителей вершинно транзитивен. ^[3]

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

${\displaystyle \chi (G\mathbin {\square } H)=\max\{\chi (G),\chi (H)\}.}$ ^[4]

Гипотеза Хедетниеми устанавливает связанное равенство для тензорного произведения графов . Число независимости декартова произведения не так легко вычисляется, но, как показал Визинг (1963), оно удовлетворяет неравенствам

${\displaystyle \alpha (G)\alpha (H)+\min\{|V(G)|-\alpha (G),|V(H)|-\alpha (H)\}\leq \alpha (G\mathbin {\square } H)\leq \min\{\alpha (G)|V(H)|,\alpha (H)|V(G)|\}.}$

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

${\displaystyle \gamma (G\mathbin {\square } H)\geq \gamma (G)\gamma (H).}$

Декартово произведение графов единичных расстояний — это еще один граф единичных расстояний. ^[5]

Графы декартовых произведений могут быть эффективно распознаны за линейное время . ^[6]

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

Алгебраическая теория графов может быть использована для анализа декартова произведения графов. Если граф имеет вершины и матрицу смежности , а граф имеет вершины и матрицу смежности , то матрица смежности декартова произведения обоих графов задается как ${\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\mathbin {\square } 2}=\mathbf {A} _{1}\otimes \mathbf {I} _{n_{2}}+\mathbf {I} _{n_{1}}\otimes \mathbf {A} _{2}}$,

где обозначает произведение Кронекера матриц, а обозначает единичную матрицу . ^[7] Матрица смежности декартова графового произведения, таким образом, является суммой Кронекера матриц смежности факторов. ${\displaystyle \otimes }$ ${\displaystyle \mathbf {I} _{n}}$ ${\displaystyle n\times n}$

Теория категорий

Рассматривая граф как категорию , чьи объекты являются вершинами, а чьи морфизмы являются путями в графе, декартово произведение графов соответствует забавному тензорному произведению категорий. Декартово произведение графов является одним из двух графовых произведений, которые превращают категорию графов и гомоморфизмов графов в симметричную замкнутую моноидальную категорию (в отличие от просто симметричной моноидальной), другое является тензорным произведением графов . ^[8] Внутренний hom для декартового произведения графов имеет графовые гомоморфизмы от до в качестве вершин и «неестественные преобразования» между ними в качестве ребер. ^[8] ${\displaystyle [G,H]}$ ${\displaystyle G}$ ${\displaystyle H}$

История

Согласно Имриху и Клавжару (2000), декартовы произведения графов были определены в 1912 году Уайтхедом и Расселом . Они были неоднократно переоткрыты позднее, в частности Гертом Сабидусси  (1960).

Примечания

1. Хан и Сабидусси (1997).
2. Сабидусси (1960); Визинг (1963).
3. Имрих и Клавжар (2000), Теорема 4.19.
4. Сабидусси (1957).
5. Хорват и Писански (2010).
6. Имрих и Петерин (2007). Более ранние алгоритмы с полиномиальным временем см. в Feigenbaum, Hershberger & Schäffer (1985) и Aurenhammer, Hagauer & Imrich (1992).
7. Кавех и Рахами (2005).
8. Вебер 2013.

Ссылки

• Ауренхаммер, Ф.; Хагауэр, Дж.; Имрих, В. (1992), «Декартова факторизация графа с логарифмической стоимостью на ребро», Computational Complexity , 2 (4): 331–349, doi :10.1007/BF01200428, MR  1215316.
• Фейгенбаум, Джоан ; Хершбергер, Джон ; Шеффер, Алехандро А. (1985), «Алгоритм полиномиального времени для нахождения простых множителей графов декартовых произведений», Discrete Applied Mathematics , 12 (2): 123–138, doi : 10.1016/0166-218X(85)90066-6 , MR  0808453.
• Хан, Геня; Сабидусси, Герт (1997), Симметрия графа: алгебраические методы и приложения, Серия передовых научных институтов НАТО, т. 497, Springer, стр. 116, ISBN 978-0-7923-4668-5.
• Хорват, Борис; Писански, Томаж (2010), «Продукты графов единичных расстояний», Дискретная математика , 310 (12): 1783–1792, doi : 10.1016/j.disc.2009.11.035 , MR  2610282.
• Имрих, Вильфрид ; Клавжар, Санди (2000), Графы продуктов: структура и распознавание , Wiley, ISBN 0-471-37039-8.
• Имрих, Вильфрид ; Клавжар, Санди; Ралл, Дуглас Ф. (2008), Графы и их декартовы произведения , AK Peters, ISBN 1-56881-429-1.
• Имрих, Вильфрид ; Петерин, Изток (2007), «Распознавание декартовых произведений за линейное время», Дискретная математика , 307 (3–5): 472–483, doi : 10.1016/j.disc.2005.09.038 , MR  2287488.
• Кавех, А.; Рахами, Х. (2005), «Унифицированный метод собственного разложения графовых произведений», Communications in Numerical Methods in Engineering with Biomedical Applications , 21 (7): 377–388, doi :10.1002/cnm.753, MR  2151527.
• Сабидусси, Г. (1957), «Графы с заданной группой и заданными теоретико-графовыми свойствами», Канадский математический журнал , 9 : 515–525, doi :10.4153/CJM-1957-060-7, MR  0094810.
• Сабидусси, Г. (1960), «Умножение графов», Mathematische Zeitschrift , 72 : 446–457, doi : 10.1007/BF01162967, hdl : 10338.dmlcz/102459 , MR  0209177.
• Визинг, В.Г. (1963), «Декартово произведение графов», Вычисл. системы , 9 : 30–43, MR  0209178.
• Вебер, Марк (2013), «Свободные произведения высших операдных алгебр», TAC , 28 (2): 24–65.

Внешние ссылки

• Вайсштейн, Эрик В. «Декартово произведение графов». MathWorld .