Объединение графов

В теории графов объединение графов — это связь между двумя графами (один граф является объединением другого). Подобные отношения включают подграфы и миноры . Объединения могут предоставить способ уменьшить граф до более простого, сохраняя при этом определенную структуру. Затем объединение можно использовать для изучения свойств исходного графа в более понятном контексте. Приложения включают в себя встраивания, ^[1] вычисление распределения по родам, ^[2] и гамильтоновы разложения .

Определение

Позволять $G$ и $H$ — два графа с одинаковым числом ребер, где $G$ имеет больше вершин, чем $H$ . Тогда мы говорим, что $H$ представляет собой объединение $G$ если существует биекция $\phi :E(G)\to E(H)$ и сюръекция $\psi :V(G)\to V(H)$ и имеют место следующие утверждения:

Если $x$ , $y$ две вершины в $G$ где $\psi (x)\neq \psi (y)$ и оба $x$ и $y$ соседствуют по краю $e$ в $G$ , затем $\psi (x)$ и $\psi (y)$ соседствуют по краю $\phi (e)$ в $H$ .
Если $e$ это петля на вершине $x\in V(G)$ , затем $\phi (e)$ это цикл включен $\psi (x)\in H$ .
Если $e$ присоединяется $x,y\in V(G)$ , где $x\neq y$ , но $\psi (x)=\psi (y)$ , затем $\phi (e)$ это цикл включен $\psi (x)$ . ^[3]

Обратите внимание, что пока $G$ может быть графиком или псевдографом , обычно бывает так, что $H$ это псевдограф.

Характеристики

Раскраски ребер инвариантны к слиянию. Это очевидно, поскольку все ребра между двумя графами находятся в биекции друг с другом. Однако, что может быть неочевидно, так это то, что если $G$ представляет собой полный граф вида $K_{2n+1}$ , и мы раскрашиваем ребра так, чтобы задать гамильтоново разложение (разложение на гамильтоновы пути , тогда эти ребра также образуют гамильтоново разложение в $H$ .

Пример

Рисунок 1 иллюстрирует объединение $K_{5}$ . Инвариантность раскраски ребер и разложения Гамильтона хорошо видна. Функция $\phi$ является биекцией и на рисунке обозначен буквами. Функция $\psi$ приведено в таблице ниже.

$v\in V(G)$	$\psi (v)$
$v_{1}$	$u_{2}$
$v_{2}$	$u_{2}$
$v_{3}$	$u_{1}$
$v_{4}$	$u_{3}$
$v_{5}$	$u_{2}$

гамильтоновы разложения

Один из способов использования объединений — найти гамильтоновы разложения полных графов с 2 n + 1 вершинами. ^[4] Идея состоит в том, чтобы взять граф и создать его объединение, края которого окрашены в $n$ цвета и удовлетворяет определенным свойствам (называемым контурным гамильтоновым разложением). Затем мы можем «обратить» объединение, и у нас останется $K_{2n+1}$ раскрашены в гамильтоновом разложении.

В ^[3] Хилтон описывает метод для этого, а также метод нахождения всех гамильтоновых разложений без повторения. Методы основаны на предложенной им теореме, которая утверждает (примерно), что если у нас есть схематическое гамильтоновое разложение, мы могли бы прийти к нему, сначала начав с гамильтонового разложения полного графа, а затем найдя для него объединение.

Примечания

^ Гросс, Такер 1987
^ Валовой 2011 г.
^ Перейти обратно: ^а ^б Хилтон 1984 г.
^ Бахманиан, Аминь; Роджер, Крис, 2012 г.

Ссылки

Бахманян, Амин; Роджер, Крис (2012), «Что такое объединение графов?» , Обернский университет
Хилтон, AJ W (1984), «Гамильтоновы разложения полных графов» , Журнал комбинаторной теории , серия B 36, 125–134
Гросс, Джонатан Л.; Такер, Томас В. (1987), Топологическая теория графов, Courier Dover Publications , 151
Гросс, Джонатан Л. (2011), «Распределение кубических внешнепланарных графов по родам» , Журнал графовых алгоритмов и приложений , Vol. 15, нет. 2, стр. 295–316.

[gross-1] Гросс, Такер 1987

[jlg2-2] Валовой 2011 г.

[hilton-3] Перейти обратно: ^а ^б Хилтон 1984 г.

[barg-4] Бахманиан, Аминь; Роджер, Крис, 2012 г.

[1]

[2]

[3]

[4]