Дизъюнктное объединение графов

Кластерный граф — непересекающееся объединение полных графов.

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

Обозначения [ править ]

Непересекающееся объединение также называется суммой графа и может быть представлено либо знаком плюс , либо знаком плюс в кружке: Если $G$ и $H$ два графика, то $G+H$ или $G\oplus H$ обозначает их непересекающееся объединение. ^[1]

Связанные классы графов [ править ]

Некоторые специальные классы графов могут быть представлены с помощью операций непересекающегося объединения. В частности:

Леса представляют собой разрозненные союзы деревьев . ^[2]
Кластерные графы представляют собой непересекающиеся объединения полных графов . ^[3]
представляют 2-регулярные графы собой непересекающиеся объединения графов циклов . ^[4]

В более общем смысле каждый граф представляет собой непересекающееся объединение связных графов и их связных компонентов .

Кографы — это графы, которые можно построить из одновершинных графов с помощью комбинации операций непересекающегося объединения и дополнения . ^[5]

Ссылки [ править ]

^ Розен, Кеннет Х. (1999), Справочник по дискретной и комбинаторной математике , Дискретная математика и ее приложения, CRC Press, стр. 515, ISBN 9780849301490
^ Гроссман, Джеррольд В. (1990), Дискретная математика: введение в концепции, методы и приложения , Macmillan, с. 627, ISBN 9780023483318
^ Кластерные графики , Информационная система по классам графов и их включениям, по состоянию на 26 июня 2016 г.
^ Шартран, Гэри; Чжан, Пин (2013), Первый курс теории графов , Dover Books on Mathematics, Courier Corporation, стр. 201, ISBN 9780486297309
^ Корней, Д.Г. ; Лерхс, Х.; Стюарт Берлингем, Л. (1981), «Дополнительные приводимые графы», Discrete Applied Mathematics , 3 (3): 163–174, doi : 10.1016/0166-218X(81)90013-5 , MR 0619603

[1] Розен, Кеннет Х. (1999), Справочник по дискретной и комбинаторной математике , Дискретная математика и ее приложения, CRC Press, стр. 515, ISBN 9780849301490

[2] Гроссман, Джеррольд В. (1990), Дискретная математика: введение в концепции, методы и приложения , Macmillan, с. 627, ISBN 9780023483318

[3] Кластерные графики , Информационная система по классам графов и их включениям, по состоянию на 26 июня 2016 г.

[4] Шартран, Гэри; Чжан, Пин (2013), Первый курс теории графов , Dover Books on Mathematics, Courier Corporation, стр. 201, ISBN 9780486297309

[5] Корней, Д.Г. ; Лерхс, Х.; Стюарт Берлингем, Л. (1981), «Дополнительные приводимые графы», Discrete Applied Mathematics , 3 (3): 163–174, doi : 10.1016/0166-218X(81)90013-5 , MR 0619603

[1]

[2]

[3]

[4]

[5]