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

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

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

Обозначение

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

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

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

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

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

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

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