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

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

Определение

Позволять ${ displaystyle G}$ и ${ displaystyle H}$ - два графа с одинаковым числом ребер, где ${ displaystyle G}$ имеет больше вершин, чем ${ displaystyle H}$ . Затем мы говорим, что ${ displaystyle H}$ это слияние ${ displaystyle G}$ если есть биекция ${ Displaystyle фи: от E (G) до E (H)}$ и сюрприз ${ Displaystyle psi: от V (G) до V (H)}$ и выполняется следующее:

Если ${ displaystyle x}$ , ${ displaystyle y}$ две вершины в ${ displaystyle G}$ куда ${ Displaystyle psi (x) neq psi (y)}$ , и оба ${ displaystyle x}$ и ${ displaystyle y}$ примыкают по краю ${ displaystyle e}$ в ${ displaystyle G}$ , тогда ${ Displaystyle psi (х)}$ и ${ displaystyle psi (y)}$ примыкают по краю ${ Displaystyle фи (е)}$ в ${ displaystyle H}$ .
Если ${ displaystyle e}$ это петля на вершине ${ Displaystyle х в V (G)}$ , тогда ${ Displaystyle фи (е)}$ это петля на ${ displaystyle psi (x) in H}$ .
Если ${ displaystyle e}$ присоединяется ${ Displaystyle х, у в V (G)}$ , куда ${ Displaystyle х neq y}$ , но ${ Displaystyle psi (x) = psi (y)}$ , тогда ${ Displaystyle фи (е)}$ это петля на ${ Displaystyle psi (х)}$ .^[3]

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

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

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

Пример

Рисунок 1: Объединение полного графа на пяти вершинах.

На рисунке 1 показано объединение ${ displaystyle K_ {5}}$ . Ясно видна инвариантность раскраски ребер и гамильтонова разложения. Функция ${ displaystyle phi}$ является биекцией и обозначена на рисунке буквами. Функция ${ displaystyle psi}$ приведено в таблице ниже.

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

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

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

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

Примечания

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