Лексикографическое произведение графов
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Graph-lexicographic-product.svg/300px-Graph-lexicographic-product.svg.png)
Лексикографическое произведение или суперпозиция графов — конструкция графа по данным двум. Если связи рёбер в двух графах являются отношениями порядка, то связь рёбер в их лексикографическом произведении является соответствующим лексикографическим порядком — отсюда название.
Лексикографическое произведение первым изучал Феликс Хаусдорф[1].
Определение
графов G и H — это граф, такой, что
- Множество вершин графа есть ; то есть прямое произведение множеств вершин графов и .
- Любые две вершины (u,v) и (x,y) смежны в тогда и только тогда, когда либо u смежна x в G, либо и v смежна y в H.
Свойства
- Лексикографическое произведение в общем случае не коммутативно: . Однако оно удовлетворяет дистрибутивному закону для дизъюнктного объединения: .
- Для дополнений выполняется: .
- Число независимости лексикографического произведения можно легко вычислить из его сомножителей [2]:
- .
- Кликовое число лексикографического произведения мультипликативно:
- .
- Хроматическое число лексикографического произведения равно b-кратному хроматическому числу графа G для b, равному хроматическому числу H:
- , где .
- Лексикографическое произведение двух графов является совершенным графом тогда и только тогда, когда оба множителя совершенны[3].
- Задача распознавания, является ли граф лексикографическим произведением по сложности эквивалентна задаче об изоморфизме графов[англ.].[4]
Примечания
- ↑ Felix Hausdorff. Grundzüge der Mengenlehre,. — Leipzig, 1914. Перевод: Ф. Хаусдорф. Теория множеств. — Москва, Ленинград: Объединённое научно-техническое издательство НКТП СССР. Главная редакция технико-теоретической литературы., 1937.
- ↑ Geller D., Stahl S. The chromatic number and other functions of the lexicographic product // Journal of Combinatorial Theory. — 1975. — Т. 19. — С. 87–95. — doi:10.1016/0095-8956(75)90076-3.
- ↑ Ravindra G., Parthasarathy K. R. Perfect product graphs // Discrete Mathematics. — 1977. — Т. 20, вып. 2. — С. 177–186. — doi:10.1016/0012-365X(77)90056-5.
- ↑ Feigenbaum J., Schäffer A. A. Recognizing composite graphs is equivalent to testing graph isomorphism // SIAM Journal on Computing. — 1986. — Т. 15, вып. 2. — С. 619–627. — doi:10.1137/0215045.
Литература
- Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8.
Ссылки
- Weisstein, Eric W. Graph Lexicographic Product (англ.) на сайте Wolfram MathWorld.
Для улучшения этой статьи желательно:
|