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

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

В теории графов , то декартово произведение G Н графов G и Н представляет собой график , таким образом, что${\ Displaystyle \ квадрат}$

• множество вершин G H - это декартово произведение V ( G ) × V ( H ); и${\ Displaystyle \ квадрат}$
• две вершины ( u, u ' ) и ( v, v' ) смежны в G H тогда и только тогда, когда либо${\ Displaystyle \ квадрат}$
  • u = v и u ' смежно с v' в H , или
  • и « = v» и у примыкает к V в G .

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

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

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

Примеры [ править ]

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

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

Таким образом, декартово произведение двух графов гиперкуба - это еще один гиперкуб: Q _i Q _j = Q _{i + j} .${\ Displaystyle \ квадрат}$

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

Свойства [ править ]

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

(К ₁ + К ₂ + К ₂ ² ) (К ₁ + К ₂ ³ ) = (К ₁ + К ₂ ² + К ₂ ⁴ ) (К ₁ + К ₂ ),${\ Displaystyle \ квадрат}$${\ Displaystyle \ квадрат}$

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

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

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

χ (G H) = max {χ (G), χ (H)}. ^[4]${\ Displaystyle \ квадрат}$

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

α ( G ) α ( H ) + min {| V ( G ) | -α ( G ), | V ( H ) | -α ( H )} ≤ α ( G H ) ≤ min {α ( G ) | V ( H ) |, α ( H ) | V ( G ) |}.${\ Displaystyle \ квадрат}$

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

γ ( G H ) ≥ γ ( G ) γ ( H ).${\ Displaystyle \ квадрат}$

Декартово произведение графов единичных расстояний - это еще один граф единичных расстояний. ^[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}}$,

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

Теория категорий [ править ]

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

История [ править ]

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

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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