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

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

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

Определение

G ⋅ H {displaystyle Gcdot H} графов G и H — это граф, такой, что

• Множество вершин графа G ⋅ H {displaystyle Gcdot H} есть V ( G ) × V ( H ) {displaystyle V(G) imes V(H)} ; то есть прямое произведение множеств вершин графов G {displaystyle G} и H {displaystyle H} .
• Любые две вершины (u,v) и (x,y) смежны в G ⋅ H {displaystyle Gcdot H} тогда и только тогда, когда либо u смежна x в G, либо u = x {displaystyle u=x} и v смежна y в H.

Свойства

• Лексикографическое произведение в общем случае не коммутативно: G ⋅ H ≠ H ⋅ G {displaystyle Gcdot H eq Hcdot G} . Однако оно удовлетворяет дистрибутивному закону для дизъюнктного объединения: ( A + B ) ⋅ C = A ⋅ C + B ⋅ C {displaystyle (A+B)cdot C=Acdot C+Bcdot C} .

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

• Число независимости лексикографического произведения можно легко вычислить из его сомножителей : α ( G ⋅ H ) = α ( G ) α ( H ) {displaystyle alpha (Gcdot H)=alpha (G)alpha (H)} .

• Кликовое число лексикографического произведения мультипликативно: ω ( G ⋅ H ) = ω ( G ) ω ( H ) {displaystyle omega (Gcdot H)=omega (G)omega (H)} .

• Хроматическое число лексикографического произведения равно b-кратному хроматическому числу графа G для b, равному хроматическому числу H: χ ( G ⋅ H ) = χ b ( G ) {displaystyle chi (Gcdot H)=chi _{b}(G)} , где b = χ ( H ) {displaystyle b=chi (H)} .

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

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