В теории графов , разделе математики, несвязное объединение графов - это операция, которая объединяет два или более графа для формирования более крупного графа. Это аналогично непересекающемуся объединению множеств и строится путем превращения множества вершин результата в несвязное объединение множеств вершин данных графов, а также путем превращения множества ребер результата в несвязное объединение ребер множества данных графов. Любое непересекающееся объединение двух или более непустых графов обязательно несвязно .
Обозначение [ править ]
Непересекающееся объединение также называется суммой графов и может быть представлено либо знаком плюс, либо обведенным знаком плюс: если и - два графа, то или обозначает их непересекающееся объединение. [1]
Связанные классы графов [ править ]
Некоторые специальные классы графов могут быть представлены с помощью операций непересекающегося объединения. В частности:
- В лесах являются непересекающимися объединениями дерев . [2]
- В кластерных графах являются непересекающимися объединениями полных графов . [3]
- В 2-регулярных графах являются непересекающимися объединениями графов цикла . [4]
В более общем смысле каждый граф представляет собой несвязное объединение связных графов , его связных компонентов .
В cographs являются графиками , которые могут быть построены из одного вершинных графов с помощью комбинации непересекающихся союза и комплемента операций. [5]
Ссылки [ править ]
- ^ Розен, Кеннет Х. (1999), Справочник по дискретной и комбинаторной математике , дискретной математике и ее приложениям, CRC Press, стр. 515, ISBN 9780849301490
- ^ Гроссман, Джерролд В. (1990), Дискретная математика: Введение в концепции, методы и приложения , Macmillan, p. 627, ISBN 9780023483318
- ^ Кластерные графы , Информационная система по классам графов и их включениям, доступ 2016-06-26.
- ^ Chartrand, Гэри; Чжан, Пинг (2013), Первый курс теории графов , Dover Books on Mathematics, Courier Corporation, стр. 201, ISBN 9780486297309
- ^ Корнейл, Д.Г .; Lerchs, H .; Стюарт Burlingham, Л. (1981), "комплемент приводимых граф", Дискретная прикладная математика , 3 (3): 163-174, DOI : 10.1016 / 0166-218X (81) 90013-5 , МР 0619603
