Лексикографическое произведение графов

Лексикографическое произведение графов.

Лексикографическое произведение или суперпозиция графов — конструкция графа по данным двум. Если связи рёбер в двух графах являются отношениями порядка, то связь рёбер в их лексикографическом произведении является соответствующим лексикографическим порядком — отсюда название.

Лексикографическое произведение первым изучал Феликс Хаусдорф.

Определение

[math]\displaystyle{ G \cdot H }[/math] графов G и H — это граф, такой, что

• Множество вершин графа [math]\displaystyle{ G \cdot H }[/math] есть [math]\displaystyle{ V(G) \times V(H) }[/math]; то есть прямое произведение множеств вершин графов [math]\displaystyle{ G }[/math] и [math]\displaystyle{ H }[/math].
• Любые две вершины (u,v) и (x,y) смежны в [math]\displaystyle{ G \cdot H }[/math] тогда и только тогда, когда либо u смежна x в G, либо [math]\displaystyle{ u = x }[/math] и v смежна y в H.

Свойства

• Лексикографическое произведение в общем случае не коммутативно: [math]\displaystyle{ G \cdot H \neq H \cdot G }[/math]. Однако оно удовлетворяет дистрибутивному закону для дизъюнктного объединения: [math]\displaystyle{ (A + B) \cdot C = A \cdot C + B \cdot C }[/math].

• Для дополнений выполняется: [math]\displaystyle{ \mathrm{C}(G \cdot H) = \mathrm{C}(G) \cdot \mathrm{C}(H) }[/math].

• Число независимости лексикографического произведения можно легко вычислить из его сомножителей :

  [math]\displaystyle{ \alpha(G \cdot H) = \alpha(G)\alpha(H) }[/math].

• Кликовое число лексикографического произведения мультипликативно:

  [math]\displaystyle{ \omega(G \cdot H) = \omega(G)\omega(H) }[/math].

• Хроматическое число лексикографического произведения равно b-кратному хроматическому числу графа G для b, равному хроматическому числу H:

  [math]\displaystyle{ \chi(G \cdot H) = \chi_b(G) }[/math], где [math]\displaystyle{ b = \chi(H) }[/math].

• Лексикографическое произведение двух графов является совершенным графом тогда и только тогда, когда оба множителя совершенны.

• Задача распознавания, является ли граф лексикографическим произведением по сложности эквивалентна задаче об изоморфизме графов.

Ссылки

• Weisstein, Eric W. Graph Lexicographic Product (англ.) на сайте Wolfram MathWorld.