Непересекающееся объединение графов - Disjoint union of graphs

Кластера граф , несвязное объединение полных графов

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

Обозначение

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

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

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

• В лесах являются непересекающимися объединениями дерев .
• В кластерных графах являются непересекающимися объединениями полных графов .
• В 2-регулярных графах являются непересекающимися объединениями графов цикла .

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

В cographs являются графиками , которые могут быть построены из одного вершинных графов с помощью комбинации непересекающихся союза и комплемента операций.

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