Частковий куб

У теорії графів частковий куб — це підграф гіперкуба, що зберігає відстані (в термінах графів) — відстань між будь-якими двома вершинами підграфу така ж, як у початковому графіШаблон:Sfn. Еквівалентно, частковий куб — це граф, вершини якого можна позначити бітовими рядками однакової довжини, так що відстань між двома вершинами в графі дорівнює відстані Геммінга між цими двома позначками. Така розмітка називається розміткою Геммінга і вона представляє ізометричне вкладення часткового куба в гіперкуб.

Історія

В. ФірсовШаблон:Sfn першим досліджував ізометричні вкладення графів у гіперкуби. Графи, що дозволяють такі вкладення, описані Д. ДжоковичемШаблон:Sfn і П. ВінклеромШаблон:Sfn, пізніше отримали назву «часткові куби». Окремо ці ж структури в термінології сімейств множин, а не розмітки гіперкубів, досліджували, серед інших, В. Кузьмін і С. ОвчинніковШаблон:Sfn, а також Фалмагне і ДойнонШаблон:SfnШаблон:Sfn.

Приклади

Приклад часткового куба з розміткою Геммінга у вершинах. Граф є також медіанним графом.

Будь-яке дерево є частковим кубом. Припустимо, що дерево T має m ребер і номери цих ребер (в довільному порядку) від 0 до m − 1. Виберемо довільну кореневу вершину r для дерева, і надамо кожній вершині v позначку (бітовий рядок) довжиною m біт, у якій стоїть 1 у позиції i, якщо ребро i лежить на шляху з r до v в дереві T. Наприклад, сама вершина r матиме позначку з нулів, а всі сусідні їй вершини будуть мати 1 в одній позиції, і т. д. Тоді відстань Геммінга між будь-якими двома позначками дорівнюватиме відстані між відповідними вершинами дерева, так що така розмітка показує, що дерево T є частковим кубом.

Будь-який граф гіперкуба є сам частковим кубом, який можна розмітити різними бітовими рядками з довжиною, що дорівнює розмірності гіперкуба.

Складніші приклади:

• Розглянемо граф, вершини якого складаються з усіх можливих бітових рядків довжиною Шаблон:Nobr, які мають або n, або Шаблон:Nobr ненульових біт. Дві вершини цього графу суміжні, якщо їх мітки відрізняються на єдиний біт. Така розмітка визначає вкладення цього графу в гіперкуб (граф усіх бітових рядків заданої довжини з тією ж умовою суміжності). Отриманий граф є двочастинним кнезеровим графом. Граф, отриманий таким способом з n = 2, має 20 вершин і 30 ребер і називається графом Дезарга.
• Всі медіанні графи є частковими кубамиШаблон:Sfn. Дерева і гіперкуби є окремими випадками медіанних графів. Оскільки до медіанних графів належать рамкові графи, Шаблон:Не перекладено і куби Фібоначчі, а також покривні графи скінченних дистрибутивних ґраток, всі вони є частковими кубами.
• Графи, двоїсті конфігураціям прямих на евклідовій площині, є частковими кубами. У загальнішому вигляді, для будь-якої Шаблон:Не перекладено у евклідовому просторі будь-якої розмірності граф, що має вершину для кожної комірки конфігурації і ребро для будь-яких двох суміжних комірок, є частковим кубомШаблон:Sfn.
• Частковий куб, у якому кожна вершина має рівно три сусіди, відомий як кубічний частковий куб. Хоча деякі нескінченні сімейства кубічних часткових кубів відомі, разом з іншими спорадичними прикладами, єдиний відомий кубічний частковий куб, який не є планарним, — це граф ДезаргаШаблон:Sfn.
• Граф, що лежить в основі будь-якого антиматроїда, що має вершину для кожної множини в антиматроїді і ребро для будь-яких двох множин, що відрізняються єдиним елементом, завжди є частковим кубом.
• Прямий добуток будь-якої скінченної множини часткових кубів є іншим частковим кубомШаблон:Sfn.

Співвідношення Джоковича — Вінклера

Багато теорем про часткові куби спираються прямо або побічно на деяке бінарне відношення, визначене на ребрах графу. Це відношення, вперше описане ДжоковичемШаблон:Sfn, позначається $\mathrm{\Theta }$. Вінклер дав еквівалентне визначення співвідношення в термінах відстаніШаблон:Sfn. Два ребра $e=\{x,y\}$ і $f=\{u,v\}$ перебувають у відношенні $\mathrm{\Theta }$ (записується $e\mathrm{\Theta }f$), якщо $d(x,u)+d(y,v)=d(x,v)+d(y,u)$. Це відношення є рефлексивним і симетричним, але, в загальному випадку, не транзитивним.

Вінклер показав, що зв'язний граф є частковим кубом тоді і тільки тоді, коли він є двочастковим і відношення $\mathrm{\Theta }$ транзитивнеШаблон:SfnШаблон:Sfn. У цьому випадку відношення утворює відношення еквівалентності і кожен клас еквівалентності відокремлює два зв'язних підграфи графу один від одного. Розмітку Геммінга можна отримати призначенням одного біта в кожній позначці для кожного класу еквівалентності співвідношення Джоковича — Вінклера. В одному з двох зв'язних підграфів, розділених співвідношенням еквівалентності ребер, позначки мають 0 у відповідній позиції, а в іншому зв'язному підграфі всі позначки в тій самій позиції мають 1.

Розпізнавання

Часткові куби можна розпізнати і побудувати для них розмітку Геммінга за час $O(n^2)$, де $n$ — число вершин графуШаблон:Sfn. Якщо задано частковий куб, можна безпосередньо побудувати класи еквівалентності відношення Джоковича — Вінклера використовуючи пошук у ширину від кожної вершини за загальний час $O(nm)$. Алгоритм розпізнавання з часом роботи $O(n^2)$ прискорює пошук, використовуючи для здійснення множинних пошуків у ширину за один прохід графу паралелізм бітового рівня, потім використовується окремий алгоритм для перевірки, що отримано правильну розмітку часткового куба.

Розмірність

Ізометрична розмірність часткового куба — це мінімальна розмірність гіперкуба, в який можна вкласти граф ізометрично і вона дорівнює числу класів еквівалентності відношення Джоковича — Вінклера. Наприклад, ізометрична розмірність дерева з $n$ вершинами дорівнює числу його ребер, $n-1$. Вкладення часткового куба в гіперкуб такої розмірності єдине з точністю до симетрій гіперкубаШаблон:SfnШаблон:Sfn.

Будь-який гіперкуб, а тому і будь-який частковий куб, можна вкласти ізометрично в цілочисельну ґратку і розмірність ґратки для часткового куба — це мінімальна розмірність цілочисельної ґратки, в яку можна вкласти частковий куб. Розмірність ґратки може виявитися істотно меншою від ізометричної розмірності. Наприклад, для дерева вона дорівнює половині числа листків у дереві (з округленням до найближчого цілого). Розмірність ґратки для будь-якого графу і вкладення в ґратку мінімальної розмірності можна знайти за поліноміальний час алгоритмом, заснованим на пошуку найбільшого парування в допоміжному графі.

Визначаються й інші типи розмірностей часткового куба, засновані на специфічніших структурахШаблон:SfnШаблон:Sfn.

Застосування до теорії хімічних графів

Ізометричні вкладення графів у гіперкуб мають важливе застосування в хімічній теорії графів. Бензоїдний граф — це граф, що складається з вершин і ребер, які лежать на циклі і всередині циклу в шестикутній ґратці. Такі графи є молекулярними графами бензоїдних вуглеводнів, великого класу органічних молекул. Кожен такий граф є частковим кубом. Розмітку Геммінга такого графу можна використати для обчислення індексу Вінера відповідної молекули, який можна використовувати для передбачення деяких хімічних властивостей. Інша молекулярна структура, утворена вуглецем, структура алмазу, також відповідає частковим кубамШаблон:Sfn.

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття Як процитовано в Шаблон:Harvard citation.
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга. См. главу 5, «Partial Cubes», стр. 127—181.
• Шаблон:Стаття