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

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

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

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

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

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

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

Примеры

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

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

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

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

Свойства

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

$(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}),$

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

$(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})$

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

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

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

$\chi (G\mathbin {\square } H)=\max\{\chi (G),\chi (H)\}.$

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

$\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)|\}.$

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

$\gamma (G\mathbin {\square } H)\geq \gamma (G)\gamma (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\mathbin {\square } 2}=\mathbf {A} _{1}\otimes \mathbf {I} _{n_{2}}+\mathbf {I} _{n_{1}}\otimes \mathbf {A} _{2}$,

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

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

Если рассматривать граф как категорию , объекты которой являются вершинами, а морфизмы — путями в графе, декартово произведение графов соответствует забавному тензорному произведению категорий. Декартово произведение графов — это одно из двух произведений графов, которые превращают категорию графов и гомоморфизмов графов в симметричную замкнутую моноидальную категорию (в отличие от просто симметричной моноидальной), а другое — тензорное произведение графов . Внутренний дом $[G,H]$ поскольку декартово произведение графов имеет гомоморфизмы графов из $G$ к $H$ как вершины, а « неестественные преобразования » между ними как ребра.

История

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

Ссылки

• Ауренхаммер, Ф .; Хагауэр, Дж.; Имрич, В. (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 , МР   0808453 .
• Хан, Геня; Сабидусси, Герт (1997), Симметрия графа: алгебраические методы и приложения , Серия институтов передовых научных исследований НАТО, том. 497, Спрингер, с. 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), «Распознавание декартовых произведений в линейном времени», Discrete Mathematics , 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), «Графы с заданной группой и заданными теоретико-графическими свойствами», Canadian Journal of Mathematics , 9 : 515–525, doi : 10.4153/CJM-1957-060-7 , MR   0094810 .
• Сабидусси, Г. (1960), «Умножение графов», Mathematical Journal , 72 : 446–457, doi : 10.1007/BF01162967 , hdl : 10338.dmlcz/102459 , MR   0209177 .
• Визинг, В.Г. (1963), "Декартово произведение графов", Vycisl. Системы , 9 :30–43, МР   0209178 .
• Вебер, Марк (2013), «Свободные произведения алгебр высших операд», TAC , 28 (2): 24–65 .

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

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