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

Матеріал з testwiki
Перейти до навігації Перейти до пошуку

У теорії графів частковий куб — це підграф гіперкуба, що зберігає відстані (в термінах графів) — відстань між будь-якими двома вершинами підграфу така ж, як у початковому графіШаблон: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, позначається Θ. Вінклер дав еквівалентне визначення співвідношення в термінах відстаніШаблон:Sfn. Два ребра e={x,y} і f={u,v} перебувають у відношенні Θ (записується eΘf), якщо d(x,u)+d(y,v)=d(x,v)+d(y,u). Це відношення є рефлексивним і симетричним, але, в загальному випадку, не транзитивним.

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

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

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

Розмірність

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

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

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

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

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

Примітки

Шаблон:Reflist

Література

  1. ↑ Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb, Chapter 6, «Lattice Embeddings», стр. 183—205.
  2. ↑ Шаблон:Harvnb, Propositions 2.1 and 3.1; Шаблон:Harvnb, стр. 60; Шаблон:Harvnb, Section 5.12, «Average Length and the Wiener Index», стр. 165—168.
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Частковий_куб&oldid=9134