Декартово произведение графов - Cartesian product of graphs

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

В теория графов, то Декартово произведение грамм ${\displaystyle \square }$ ЧАС графиков грамм и ЧАС такой граф, что

• множество вершин грамм ${\displaystyle \square }$ ЧАС это Декартово произведение V(грамм) × V(ЧАС); и
• две вершины (ты, ты ) и (v, v ' ) смежны в грамм ${\displaystyle \square }$ ЧАС если и только если либо
  • ты = v и ты примыкает к v ' в ЧАС, или же
  • ты = v ' и ты примыкает к v в грамм.

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

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

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

Примеры

• Декартово произведение двух ребер есть цикл на четырех вершинах: K₂ ${\displaystyle \square }$ K₂ = C₄.
• Декартово произведение K₂ и граф путей это лестничный график.
• Декартово произведение двух графов путей есть сеточный график.
• Декартово произведение п ребра - это гиперкуб:

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

Таким образом, декартово произведение двух графы гиперкуба еще один гиперкуб: Q_я ${\displaystyle \square }$ Q_j = Q_{я + j}.

• Декартово произведение двух медианные графики это еще один медианный граф.
• Граф вершин и ребер n-призма - декартов граф произведения K₂ ${\displaystyle \square }$ C_п.
• В график ладьи - декартово произведение двух полных графов.

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

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

(K₁ + K₂ + K₂²) ${\displaystyle \square }$ (K₁ + K₂³) = (K₁ + K₂² + K₂⁴) ${\displaystyle \square }$ (K₁ + K₂),

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

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

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

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

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

α (грамм) α (ЧАС) + min {| V (грамм) | -α (грамм), | V (ЧАС) | -α (ЧАС)} ≤ α (грамм ${\displaystyle \square }$ ЧАС) ≤ min {α (грамм) | V (ЧАС) |, α (ЧАС) | V (грамм)|}.

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

γ (грамм ${\displaystyle \square }$ ЧАС) ≥ γ (грамм) γ (ЧАС).

Декартово произведение графики единичных расстояний - еще один граф единичных расстояний.^[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\square 2}=\mathbf {A} _{1}\otimes \mathbf {I} _{n_{2}}+\mathbf {I} _{n_{1}}\otimes \mathbf {A} _{2}}$,

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

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

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

История

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

Примечания

1. Хан и Сабидусси (1997).
2. Сабидусси (1960); Визинг (1963).
3. Имрих и Клавжар (2000), Теорема 4.19.
4. Сабидусси (1957).
5. Хорват и Писанский (2010).
6. Имрих и Петерин (2007). Для ранее полиномиальное время алгоритмы видят Файгенбаум, Хершбергер и Шеффер (1985) и Ауренхаммер, Хагауэр и Имрих (1992).
7. Кавех и Рахами (2005).
8. Вебер 2013.

Рекомендации

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

внешняя ссылка

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