Непересекающееся объединение графиков

редактировать

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

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

Обозначение

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

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

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

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

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

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

Ссылки