Лексикографическое произведение или суперпозиция графов — конструкция графа по данным двум. Если связи рёбер в двух графах являются отношениями порядка, то связь рёбер в их лексикографическом произведении является соответствующим лексикографическим порядком — отсюда название.
Лексикографическое произведение первым изучал Феликс Хаусдорф.
Определение
графов и — это граф, такой, что Множество вершин графа есть ; то есть прямое произведение множеств вершин графов и . Любые две вершины и смежны в тогда и только тогда, когда либо смежна в , либо и смежна в .
Свойства Лексикографическое произведение в общем случае не коммутативно: . Однако оно удовлетворяет дистрибутивному закону для дизъюнктного объединения: .
Для дополнений выполняется: .
Число независимости лексикографического произведения можно легко вычислить из его сомножителей : .
Кликовое число лексикографического произведения мультипликативно: .
Хроматическое число лексикографического произведения равно b-кратному хроматическому числу графа G для b, равному хроматическому числу H: , где .
Лексикографическое произведение двух графов является совершенным графом тогда и только тогда, когда оба множителя совершенны.
Задача распознавания, является ли граф лексикографическим произведением по сложности эквивалентна .
Примечания
Литература
Ссылки
Категория:Произведение графов