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

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

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

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

ОпределениеПравить

$G\cdot <!--\; \cdot \; -->H$$G\cdot H$  графов G и H — это граф, такой, что

• Множество вершин графа $G\cdot <!--\; \cdot \; -->H$$G\cdot H$  есть $V(G)\times <!--\; \times \; -->V(H)$$V(G)\times V(H)$ ; то есть прямое произведение множеств вершин графов $G$$G$  и $H$$H$ .
• Любые две вершины (u,v) и (x,y) смежны в $G\cdot <!--\; \cdot \; -->H$$G\cdot H$  тогда и только тогда, когда либо u смежна x в G, либо $u=x$$u=x$  и v смежна y в H.

СвойстваПравить

• Лексикографическое произведение в общем случае не коммутативно: $G\cdot <!--\; \cdot \; -->H\ne <!--\; \ne \; -->H\cdot <!--\; \cdot \; -->G$$G\cdot H\neq H\cdot G$ . Однако оно удовлетворяет дистрибутивному закону для дизъюнктного объединения: $(A+B)\cdot <!--\; \cdot \; -->C=A\cdot <!--\; \cdot \; -->C+B\cdot <!--\; \cdot \; -->C$$(A+B)\cdot C=A\cdot C+B\cdot C$ .

• Для дополнений выполняется: $\mathrm{C}(G\cdot <!--\; \cdot \; -->H)=\mathrm{C}(G)\cdot <!--\; \cdot \; -->\mathrm{C}(H)$$\mathrm {C} (G\cdot H)=\mathrm {C} (G)\cdot \mathrm {C} (H)$ .

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

  $\mathrm{\alpha <!--\; \alpha \; -->}(G\cdot <!--\; \cdot \; -->H)=\mathrm{\alpha <!--\; \alpha \; -->}(G)\mathrm{\alpha <!--\; \alpha \; -->}(H)$$\alpha (G\cdot H)=\alpha (G)\alpha (H)$ .

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

  $\mathrm{\omega <!--\; \omega \; -->}(G\cdot <!--\; \cdot \; -->H)=\mathrm{\omega <!--\; \omega \; -->}(G)\mathrm{\omega <!--\; \omega \; -->}(H)$$\omega (G\cdot H)=\omega (G)\omega (H)$ .

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

  $\mathrm{\chi <!--\; \chi \; -->}(G\cdot <!--\; \cdot \; -->H)={\mathrm{\chi <!--\; \chi \; -->}}_b(G)$$\chi (G\cdot H)=\chi _{b}(G)$ , где $b=\mathrm{\chi <!--\; \chi \; -->}(H)$$b=\chi (H)$ .

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

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

СсылкиПравить

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