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

В теории графов декартово произведение G $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$H графов G и H - это такой граф, что

• набор вершин графа G $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$H является декартовым произведением V (G) × V (H); и
• две вершины (u, u ') и (v, v') смежны в G $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$H тогда и только тогда, когда либо
  • u = v и u 'смежно с v' в H, or
  • u '= v' и u смежно с v в G.

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

Операция ассоциативна, поскольку графики (F $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$G) $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$H и F $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$(G $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$H) естественно изоморфны. Операция коммутативна как операция над изоморфизмом классами графов, и, более строго, над графами G $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$H и H $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$G естественно изоморфны, но это не коммутативно как операция на помеченных графах.

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

• 1 Примеры
• 2 Свойства
• 3 Алгебраический граф теория
• 4 Теория категорий
• 5 История
• 6 Примечания
• 7 Ссылки
• 8 Внешние ссылки

• Декартово произведение двух ребер - это цикл на четырех вершинах: K 2$◻\; \{\backslash \; displaystyle\; \backslash \; square\}$K2= C 4.
• Декартово произведение K 2 и графа путей - это лестничный граф.
• Декартово произведение двух графов-путей - это сеточный граф.
• Декартово произведение n ребер представляет собой гиперкуб:

$(K\; 2)\; ◻\; n\; =\; Q\; n.\; \{\backslash \; displaystyle\; (K\_\; \{2\})\; ^\; \{\backslash \; square\; n\}\; =\; Q\_\; \{n\}.\}$

Таким образом, декартово произведение двух графов гиперкуба является еще одним гиперкубом: Q i$◻\; \{\; \backslash \; displaystyle\; \backslash \; square\}$Qj= Q i + j.

• Декартово произведение двух медианных графов является еще одним медианным графом.
• Граф вершин и ребер n- призма - это декартово произведение K 2$◻\; \{\backslash \; displaystyle\; \backslash \; square\}$Cn.
• График ладьи - это декартово произведение двух полных графов.

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

(K1+ K 2 + K 2) $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$(K1+ K 2) = (K 1 + K 2 + K 2) $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$(K1+ K 2),

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

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

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

χ (G $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$H) = max {χ (G), χ (H)}.

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

α (G) α (H) + min {| V (G) | -α (G), | V (H) | -α (H)} ≤ α (G $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$H) ≤ min {α (G) | V (H) |, α (H) | V (G) |}.

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

γ (G $◻\; \{\backslash \; displaystyle\; \backslash \; square\}$H) ≥ γ (G) γ (H

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

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

Теория алгебраических графов может использоваться для анализа произведения декартовых графов. Если граф $G\; 1\; \{\backslash \; displaystyle\; G\_\; \{1\}\}$имеет $n\; 1\; \{\backslash \; displaystyle\; n\_\; \{1\}\}$вершин и $n\; 1\; \times \; n\; 1\; \{\backslash \; displaystyle\; n\_\; \{1\}\; \backslash \; times\; n\_\; \{1\}\}$матрица смежности $A\; 1\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{A\}\; \_\; \{1\}\}$, и граф $G\; 2\; \{\backslash \; displaystyle\; G\_\; \{2\}\}$имеет $n\; 2\; \{\backslash \; displaystyle\; n\_\; \{2\}\}$вершин и $n\; 2\; \times \; n\; 2\; \{\backslash \; displaystyle\; n\_\; \{2\}\; \backslash \; times\; n\_\; \{2\}\}$матрица смежности $A\; 2\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{A\}\; \_\; \{2\}\}$, тогда матрица смежности декартова произведения обоих графов имеет вид

$A\; 1\; ◻\; 2\; =\; A\; 1\; \otimes \; I\; n\; 2\; +\; I\; n\; 1\; \otimes \; A\; 2\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{A\}\; \_\; \{1\; \backslash \; square\; 2\}\; =\; \backslash \; mathbf\; \{A\}\; \_\; \{1\}\; \backslash \; otimes\; \backslash \; mathbf\; \{I\}\; \_\; \{n\_\; \{2\}\}\; +\; \backslash \; mathbf\; \{I\}\; \_\; \{n\_\; \{1\}\}\; \backslash \; otimes\; \backslash \; mathbf\; \{A\}\; \_\; \{2\}\}$,

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

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

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

• Ауренхаммер, Ф. ; Hagauer, J.; Имрих, В. (1992), "Факторизация декартового графа при логарифмической стоимости на ребро", Вычислительная сложность, 2 (4): 331–349, doi : 10.1007 / BF01200428, MR 1215316.
• Файгенбаум, Джоан ; Хершбергер, Джон ; Шеффер, Алехандро А. (1985), «Алгоритм с полиномиальным временем для нахождения простых факторов графов декартовых произведений», Дискретная прикладная математика, 12(2): 123–138, doi : 10.1016 / 0166-218X (85) 90066-6, MR 0808453.
• Хан, Гена; Сабидусси, Герт (1997), Симметрия графа: алгебраические методы и приложения, Серия институтов перспективной науки НАТО, 497, Springer, p. 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), Графы и их декартовы произведения, А. К. Петерс, ISBN 1-56881-429-1.
• Имрих, Вильфрид ; Петерин, Изток (2007), «Распознавание декартовых произведений в линейном времени», Дискретная математика, 307 (3–5): 472–483, doi : 10.1016 / j.disc.2005.09.038, MR 2287488.
• Kaveh, A.; Рахами, Х. (2005), «Унифицированный метод для собственного разложения продуктов графа», Коммуникации в численных методах в разработке с биомедицинскими приложениями, 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), «Декартово произведение графов», Vycisl. Sistemy, 9 : 30–43, MR 0209178.
• Вебер, Марк (2013), «Бесплатные произведения алгебр высших операд», TAC, 28 (2): 24–65.

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