Просмотр кода страницы Лексикографическое произведение графов

[[Файл:Graph-lexicographic-product.svg|thumb|300px|Лексикографическое произведение графов.]]

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

Лексикографическое произведение первым изучал [[Хаусдорф, Феликс|Феликс Хаусдорф]]{{r|Haus}}.

==Определение==

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

==Свойства==
*Лексикографическое произведение в общем случае [[Коммутативная операция|не коммутативно]]: <math>G \cdot H \neq H \cdot G</math>. Однако оно удовлетворяет [[Дистрибутивность|дистрибутивному закону]] для [[Дизъюнктное объединение|дизъюнктного объединения]]: <math>(A + B) \cdot C = A \cdot C + B \cdot C</math>.

*Для [[Дополнение графа|дополнений]] выполняется: <math>\mathrm{C}(G \cdot H) = \mathrm{C}(G) \cdot \mathrm{C}(H)</math>.

*[[Задача о независимом множестве|Число независимости]] лексикографического произведения можно легко вычислить из его сомножителей {{r|GeSt}}:
*:<math>\alpha(G \cdot H) = \alpha(G)\alpha(H)</math>.

*[[Клика (теория графов)|Кликовое число]] лексикографического произведения мультипликативно:
*:<math>\omega(G \cdot H) = \omega(G)\omega(H)</math>.

*[[Раскраска графов|Хроматическое число]] лексикографического произведения равно [[Дробная раскраска#Определения|''b''-кратному хроматическому числу]] графа ''G'' для ''b'', равному хроматическому числу ''H'':
*:<math>\chi(G \cdot H) = \chi_b(G)</math>, где <math>b = \chi(H)</math>.

*Лексикографическое произведение двух графов является [[Совершенный граф|совершенным графом]] тогда и только тогда, когда оба множителя совершенны{{r|RaPa}}.

* Задача распознавания, является ли граф лексикографическим произведением по сложности эквивалентна {{не переведено 5|Задача об изоморфизме графов|задаче об изоморфизме графов||graph isomorphism problem}}.{{r|FeSc}}

==Примечания==
{{reflist|refs=
<ref name=FeSc>{{статья
  |автор=Feigenbaum J., Schäffer A. A.
  |год=1986
  |заглавие=Recognizing composite graphs is equivalent to testing graph isomorphism
  |издание=[[SIAM Journal on Computing]]
  |том=15
  |страницы=619–627
  |mr=0837609
  |doi=10.1137/0215045
  |выпуск=2}}</ref>
<ref name=GeSt>{{статья
  |автор=Geller D., Stahl S.
  |заглавие=The chromatic number and other functions of the lexicographic product
  |издание=[[Journal of Combinatorial Theory]] | series = Series B
  |том=19
  |год=1975
  |страницы= 87–95
  |mr=0392645
  |doi=10.1016/0095-8956(75)90076-3}}</ref>
<ref name=Haus>{{книга
|автор=[[Хаусдорф, Феликс|Felix Hausdorff]]
|заглавие=Grundzüge der Mengenlehre,
|год=1914
|место=Leipzig
}} Перевод: 
{{книга
|автор=Ф. Хаусдорф
|заглавие=Теория множеств
|издательство=Объединённое научно-техническое издательство НКТП СССР. Главная редакция технико-теоретической литературы.
|место=Москва, Ленинград
|год=1937
}}
</ref>

<ref name=RaPa>{{статья
|автор=Ravindra G., Parthasarathy K. R.
|doi = 10.1016/0012-365X(77)90056-5
|выпуск=2
|издание=Discrete Mathematics
|mr=0491304
|страницы=177–186
|заглавие=Perfect product graphs
|том=20
|год=1977}}</ref>
}}

== Литература ==
{{refbegin|colwidth=30em}}
*{{книга
|автор=Wilfried Imrich, Sandi Klavžar
|заглавие=Product Graphs: Structure and Recognition
|ссылка=https://archive.org/details/productgraphsstr0000imri
|издательство=Wiley
|год=2000
|isbn=0-471-37039-8}}
{{refend}}

== Ссылки ==
*{{mathworld | title = Graph Lexicographic Product | urlname = GraphLexicographicProduct}}

[[Категория:Произведение графов]]
{{rq|checktranslate|style}}