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

Объединение наборов вершин и ребер двух графов

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

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

Обозначения

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

Связанные классы графов

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

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

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

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

Рекомендации

1. Розен, Кеннет Х. (1999), Справочник по дискретной и комбинаторной математике, Дискретная математика и ее приложения, CRC Press, стр. 515, ISBN 9780849301490
2. Гроссман, Джеррольд В. (1990), Дискретная математика: введение в концепции, методы и приложения , Macmillan, p. 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