Декартів добуток або прямий добутокВізінг використав термін «декартів добуток». G H графів G і H — це граф, такий, що
множина вершин графу G H — це декартів добуток V(G) × V(H) будь-які дві вершини (u, u') і (v, v') суміжні в G H тоді і тільки тоді, коли або u=v і u' суміжна v' в H або u' =v' і u суміжна v в G.
Декартів добуток можна розпізнати ефективно за лінійний час. Для раніших алгоритмів поліноміального часу див. статтю Фейгенбаума, Гершберґерґа і Шеффера , а також статтю Авренгаммера, Гаґаувера і Імріха .. Операція є комутативною як операція на класах ізоморфізмів графів, і строгіше, графи G H і H G природно ізоморфні, але операція не є комутативною як операція на розмічених графах. Операція є також асоціативною, оскільки графи (F G) H і F (G H) природно ізоморфні.
Позначення G × H часом використовується і для декартового добутку графів, але частіше воно використовується для іншої конструкції, відомої як тензорний добуток графів. Символ квадратика частіше використовується і є недвозначним для декартового добутку графів. Він показує візуально чотири ребра, що виходять внаслідок декартового добутку двох ребер.
Приклади
Декартів добуток двох ребер є циклом з чотирма вершинами: K2 K2=C4. Декартів добуток K2 і шляху є драбиною. Декартів добуток двох шляхів є решіткою. Декартів добуток n ребер є гіперкубом:
Таким чином, декартів добуток двох графів гіперкубів є іншим гіперкубом — Qi Qj=Qi+j.
Декартів добуток двох медіанних графів є іншим медіанного графом. Граф вершин і ребер n-кутної призми є декартовим добутком K2 Cn. Туровий граф є декартовим добутком двох повних графів.
Властивості Якщо зв'язний граф є декартовим добутком, його можна розкласти єдиним способом на добуток простих множників, графів, які не можна розкласти на добуток графів. Однак, Імріх і Клавжар описали незв'язний граф, який можна подати двома різними способами як декартовий добуток простих графів:
(K1 + K2 + K22) (K1 + K23) = (K1 + K22 + K24) (K1 + K2), де знак плюс означає незв'язне об'єднання, а верхній індекс означає кратний декартів добуток.
Декартів добуток є вершинно-транзитивним графом тоді і тільки тоді, коли кожен з його множників є вершинно-транзитивним.
Декартів добуток є двочастковим тоді і тільки тоді, коли кожен з його множників є двочастковим. Загальніше, хроматичне число декартового добутку задовольняє рівнянню
χ(G H)=max {χ(G), χ(H)}.
стверджує пов'язану рівність для тензорного добутку графів. Число незалежності декартових добутків непросто обчислити, але, як показав Візінг, число незалежності задовольняє нерівностям
α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.
Гіпотеза Візінга стверджує, що число домінування декартового добутку задовольняє нерівності
γ(G H) ≥ γ(G)γ(H).
Алгебрична теорія графів Алгебричну теорію графів можна використовувати для аналізу декартового добутку графів. Якщо граф має вершин і матрицю суміжності , а граф має вершин і матрицю суміжності , то матриця суміжності декартового добутку двох графів задається формулою
,
де означає добуток Кронекера матриць, а означає одиничну матрицю.
Історія За Імріхом і Клавжару декартові добутки графів визначили 1912 року Вайтгед і Расселл. Добуток графів неодноразово перевідкривали пізніше, зокрема, Герт Сабідуссі.
Примітки
Література
Посилання