Декартів добуток графів

Декартів добуток графів

Декартів добуток або прямий добуток 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 часом використовується і для декартового добутку графів, але частіше воно використовується для іншої конструкції, відомої як тензорний добуток графів. Символ квадратика частіше використовується і є недвозначним для декартового добутку графів. Він показує візуально чотири ребра, що виходять внаслідок декартового добутку двох ребер.Шаблон:Sfn

Приклади

• Декартів добуток двох ребер є циклом з чотирма вершинами: K₂ $◻$ K₂=C_4.
• Декартів добуток K₂ і шляху є драбиною.
• Декартів добуток двох шляхів є решіткою.
• Декартів добуток n ребер є гіперкубом:

$(K_2{)}^{◻n}=Q_n.$

Таким чином, декартів добуток двох графів гіперкубів є іншим гіперкубом — Q_i $◻$ Q_j=Q_i+j.

• Декартів добуток двох медіанних графів є іншим медіанного графом.
• Граф вершин і ребер n-кутної призми є декартовим добутком K₂ $◻$ C_n.
• Туровий граф є декартовим добутком двох повних графів.

Властивості

Якщо зв'язний граф є декартовим добутком, його можна розкласти єдиним способом на добуток простих множників, графів, які не можна розкласти на добуток графівШаблон:SfnШаблон:Sfn. Однак, Імріх і КлавжарШаблон:Sfn описали незв'язний граф, який можна подати двома різними способами як декартовий добуток простих графів:

(K₁ + K₂ + K₂²) $◻$ (K₁ + K₂³) = (K₁ + K₂² + K₂⁴) $◻$ (K₁ + K₂), де знак плюс означає незв'язне об'єднання, а верхній індекс означає кратний декартів добуток.

Декартів добуток є вершинно-транзитивним графом тоді і тільки тоді, коли кожен з його множників є вершинно-транзитивнимШаблон:Sfn.

Декартів добуток є двочастковим тоді і тільки тоді, коли кожен з його множників є двочастковим. Загальніше, хроматичне число декартового добутку задовольняє рівнянню

χ(G $◻$ H)=max {χ(G), χ(H)}Шаблон:Sfn.

Шаблон:Нп стверджує пов'язану рівність для тензорного добутку графів. Число незалежності декартових добутків непросто обчислити, але, як показав ВізінгШаблон:Sfn, число незалежності задовольняє нерівностям

α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G $◻$ H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.

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

γ(G $◻$ H) ≥ γ(G)γ(H).

Алгебрична теорія графів

Алгебричну теорію графів можна використовувати для аналізу декартового добутку графів. Якщо граф $G_1$ має $n_1$ вершин і $n_1\times n_1$ матрицю суміжності ${𝐀}_1$, а граф $G_2$ має $n_2$ вершин і $n_2\times n_2$ матрицю суміжності ${𝐀}_2$, то матриця суміжності декартового добутку двох графів задається формулою

${𝐀}_{1◻2}={𝐀}_1\otimes {𝐄}_{n_2}+{𝐄}_{n_1}\otimes {𝐀}_2$ ,

де $\otimes$ означає добуток Кронекера матриць, а ${𝐄}_n$ означає $n\times n$ одиничну матрицюШаблон:Sfn.

Історія

За Імріхом і КлавжаруШаблон:Sfn декартові добутки графів визначили 1912 року Вайтгед і Расселл. Добуток графів неодноразово перевідкривали пізніше, зокрема, Герт СабідуссіШаблон:Sfn.

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття

Посилання

• Шаблон:Mathworld