Соединение (теория графов)

У этого термина существуют и другие значения, см. Соединение (значения).

Соединение в теории графов — бинарная операция, комбинирующая два графа ${\displaystyle G_{1}=(V_{1},E_{1})}$ и ${\displaystyle G_{2}=(V_{2},E_{2})}$ без общих вершин путём соединения каждой вершины одного графа со всеми вершинами другого графа^[1] в граф ${\displaystyle G_{1}\nabla G_{2}}$ следующим образом:

• множество вершин: ${\displaystyle V(G_{1}\nabla G_{2})=V_{1}\cup V_{2}}$,
• множество рёбер: ${\displaystyle E(G_{1}\nabla G_{2})=E_{1}\cup E_{2}\cup \{uv\mid u\in V_{1},v\in V_{2}\}}$.

Другими словами, соединение содержит все вершины и рёбра из обоих исходных графов, плюс новые рёбра, соединяющие каждую вершину графа ${\displaystyle G_{1}}$ с каждой вершиной графа ${\displaystyle G_{2}}$.

Кроме инфикса ${\displaystyle \nabla }$ иногда используется знак ${\displaystyle +}$.

Примеры

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

• полный двудольный граф: ${\displaystyle K_{m,n}={\overline {K}}_{m}\nabla {\overline {K}}_{n}}$ (соединение двух независимых множеств),
• колесо: ${\displaystyle W_{n}=C_{n}\nabla K_{1}}$ (соединение цикла и одиночной вершины),
• вентилятор: ${\displaystyle F_{n}=P_{n}\nabla K_{1}}$ (соединение пути и одиночной вершины).

Любой нетривиальный полный граф может быть представлен как соединение меньших полных графов.

Граф дружеских отношений ${\displaystyle Fr_{n}}$ для ${\displaystyle n=2t+1}$ получается соединением ${\displaystyle K_{1}}$ с ${\displaystyle t}$ несвязными копиями ${\displaystyle K_{2}}$^[2].

Свойства

Операция соединения коммутативна для непомеченных графов: ${\displaystyle G_{1}\nabla G_{2}\cong G_{2}\nabla G_{1}}$.

Если ${\displaystyle G_{1}}$ имеет ${\displaystyle p_{1}}$ вершин и ${\displaystyle q_{1}}$ рёбер, а ${\displaystyle G_{2}}$ имеет ${\displaystyle p_{2}}$ вершин и ${\displaystyle q_{2}}$ рёбер, то ${\displaystyle G_{1}\nabla G_{2}}$ имеет:

• вершин: ${\displaystyle p_{1}+p_{2}}$,
• рёбер: ${\displaystyle q_{1}+q_{2}+p_{1}p_{2}}$

Диаметр ${\displaystyle G_{1}\nabla G_{2}}$ не превосходит 2 (при условии, что оба графа непустые)^[2].

Хроматическое число соединения удовлетворяет выражению:

${\displaystyle \chi (G_{1}\nabla G_{2})=\chi (G_{1})+\chi (G_{2})}$.

Это свойство выполняется, потому что вершины из ${\displaystyle G_{1}}$ и ${\displaystyle G_{2}}$ должны использовать различные цвета (поскольку они все смежны друг с другом), a внутри каждого исходного графа сохраняется минимальная раскраска.

Локализуемое хроматическое число^[3] ${\displaystyle \chi _{L}(G)}$ является уточнением хроматического числа, при котором вершины одного цвета должны быть различимы по расстоянию до классов цветов. Для операции соединения, когда ${\displaystyle G_{1}}$ и ${\displaystyle G_{2}}$ являются связными графами диаметром, не превосходящим 2^[2]:

${\displaystyle \chi _{L}(G_{1}+G_{2})=\chi _{L}(G_{1})+\chi _{L}(G_{2})}$.

Этот результат распространяется на определённые семейства графов. Например, для колёсного графа ${\displaystyle W_{n}=K_{1}+C_{n}}$^[2]:

${\displaystyle \chi _{L}(W_{n})=1+\chi _{L}(C_{n})}$

В отличие от хроматического числа локализуемое хроматическое число соединения не всегда разлагается аддитивно. Например, ${\displaystyle \chi _{L}(P_{10})=3}$, но ${\displaystyle \chi _{L}(P_{10}+P_{10})=8\neq 3+3}$.

Для конкретных семейств графов:

• ${\displaystyle \chi _{L}(K_{m}\nabla P_{n})}$ определено для всех значений ${\displaystyle m}$ и ${\displaystyle n}$
• ${\displaystyle \chi _{L}(K_{m}\nabla C_{n})}$ определено, включая специальный случай вентиляторов ${\displaystyle W_{n}=K_{1}\nabla C_{n}}$
• ${\displaystyle \chi _{L}(C_{m}\nabla C_{n})}$ определено для всех пар циклов

Определённые соединения графов порождают полностью расширяемые графы. Например, если ${\displaystyle G}$- полностью расширяемый граф, то ${\displaystyle G\nabla K_{n}}$ также является полностью расширяемым графом с тем же порядком расширения, что и у ${\displaystyle G}$^[1].

Приложения

Операция соединения моделирует полную интеграцию двух отдельных вычислительных сетей, при которой каждый узел одной сети может напрямую взаимодействовать с каждым узлом другой. Такая структура актуальна при слиянии корпоративных сетей или в процессах интеграции облачных вычислений^[1].

Операция объединения моделирует полное взаимодействие между двумя различными группами, например, когда сливаются две исследовательские команды и все участники одной команды устанавливают связи со всеми участниками другой.

В параллельных и системах распределённых вычислений соединение графов моделирует сценарии, когда любая задача из одного набора может быть назначена любому процессору или узлу из другого набора, предоставляя основу для анализа оптимальных стратегий планирования задач^[1].