Вікіпедія

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

підграф гіперкуба, що зберігає відстані (в термінах графів)

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

Історія ред.

В. Фірсов[2] першим досліджував ізометричні вкладення графів у гіперкуби. Графи, що дозволяють такі вкладення, описані Д. Джоковичем[3] і П. Вінклером[4], пізніше отримали назву «часткові куби». Окремо ці ж структури в термінології сімейств множин, а не розмітки гіперкубів, досліджували, серед інших, В. Кузьмін і С. Овчинніков[5], а також Фалмагне і Дойнон[6][7].

Приклади ред.

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

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

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

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

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

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

Багато теорем про часткові куби спираються прямо або побічно на деяке бінарне відношення, визначене на ребрах графу. Це відношення, вперше описане Джоковичем[3], позначається  . Вінклер дав еквівалентне визначення співвідношення в термінах відстані[4]. Два ребра   і   перебувають у відношенні   (записується  ), якщо  . Це відношення є рефлексивним і симетричним, але, в загальному випадку, не транзитивним.

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

Розпізнавання ред.

Часткові куби можна розпізнати і побудувати для них розмітку Геммінга за час  , де   — число вершин графу[14]. Якщо задано частковий куб, можна безпосередньо побудувати класи еквівалентності відношення Джоковича — Вінклера використовуючи пошук у ширину від кожної вершини за загальний час  . Алгоритм розпізнавання з часом роботи   прискорює пошук, використовуючи для здійснення множинних пошуків у ширину за один прохід графу паралелізм бітового рівня, потім використовується окремий алгоритм для перевірки, що отримано правильну розмітку часткового куба.

Розмірність ред.

Ізометрична розмірність часткового куба — це мінімальна розмірність гіперкуба, в який можна вкласти граф ізометрично і вона дорівнює числу класів еквівалентності відношення Джоковича — Вінклера. Наприклад, ізометрична розмірність дерева з   вершинами дорівнює числу його ребер,  . Вкладення часткового куба в гіперкуб такої розмірності єдине з точністю до симетрій гіперкуба[15][16].

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

Визначаються й інші типи розмірностей часткового куба, засновані на специфічніших структурах[18][19].

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

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

Примітки ред.

  1. ↑ Ovchinnikov, 2011, с. 127, Definition 5.1.
  2. ↑ Фирсов, 1965.
  3. ↑ а б Djoković, 1973.
  4. ↑ а б Winkler, 1984.
  5. ↑ Кузьмин, Овчинников, 1975.
  6. ↑ Falmagne, Doignon, 1997.
  7. ↑ Ovchinnikov, 2011, с. 174.
  8. ↑ Ovchinnikov, 2011, с. 163–165, Section 5.11, "Median Graphs".
  9. ↑ Ovchinnikov, 2011, с. 207–235, Chapter 7, "Hyperplane Arrangements".
  10. ↑ Eppstein, 2006.
  11. ↑ Ovchinnikov, 2011, с. 144–145, Section 5.7, "Cartesian Products of Partial Cubes".
  12. ↑ Winkler, 1984, с. Theorem 4.
  13. ↑ Ovchinnikov, 2011, с. 29, 139, Definition 2.13, Theorem 5.19.
  14. ↑ Eppstein, 2008.
  15. ↑ Ovchinnikov, 2011, с. 142–144, Section 5.6, "Isometric Dimension".
  16. ↑ Ovchinnikov, 2011, с. 157–162, Section 5.10, "Uniqueness of Isometric Embeddings".
  17. ↑ (Hadlock, Hoffman, 1978); (Eppstein, 2005); (Ovchinnikov, 2011), Chapter 6, «Lattice Embeddings», стр. 183—205.
  18. ↑ а б Eppstein, 2009.
  19. ↑ Cabello, Eppstein, Klavžar, 2011.
  20. ↑ (Klavžar, Gutman, Mohar, 1995), Propositions 2.1 and 3.1; (Imrich, Klavžar, 2000), стр. 60; (Ovchinnikov, 2011), Section 5.12, «Average Length and the Wiener Index», стр. 165—168.

Література ред.

  • S. Cabello, D. Eppstein, S. Klavžar. The Fibonacci dimension of a graph // Electronic Journal of Combinatorics. — 2011. — Т. 18, вип. 1 (21 квітня). — arXiv:0903.2507.
  • D. Ž. Djoković. Distance-preserving subgraphs of hypercubes // Journal of Combinatorial Theory. — 1973. — Т. 14, вип. 3 (21 квітня). — С. 263–267. — DOI:10.1016/0095-8956(73)90010-5.
  • David Eppstein. The lattice dimension of a graph // European Journal of Combinatorics. — 2005. — Т. 26, вип. 6 (21 квітня). — С. 585–592. — arXiv:cs.DS/0402028. — DOI:10.1016/j.ejc.2004.05.001.
  • David Eppstein. Cubic partial cubes from simplicial arrangements // Electronic Journal of Combinatorics. — 2006. — Т. 13, вип. 1 (21 квітня). — arXiv:math.CO/0510263. Архівовано з джерела 14 лютого 2012. Процитовано 28 червня 2021.
  • David Eppstein. Proc. 19th ACM-SIAM Symposium on Discrete Algorithms. — 2008. — С. 1258–1266.
  • David Eppstein. Proc. 16th International Symposium on Graph Drawing, Heraklion, Crete, 2008. — Springer-Verlag, 2009. — Т. 5417. — С. 384–389. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-00219-9_37.
  • J.-C. Falmagne, J.-P. Doignon. Stochastic evolution of rationality // Theory and Decision. — 1997. — Т. 43 (21 квітня). — С. 107–138. — DOI:10.1023/A:1004981430688.
  • Фирсов В. В. Об изометрическом вложении графа в булевский куб // Кибернетика. — 1965. — Вип. 6 (21 квітня). — С. 95-96.
  • F. Hadlock, F. Hoffman. Manhattan trees // Utilitas Mathematica. — 1978. — Т. 13 (21 квітня). — С. 55–67. Як процитовано в (Ovchinnikov, 2011).
  • Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — New York : John Wiley & Sons, 2000. — (Wiley-Interscience Series in Discrete Mathematics and Optimization) — ISBN 978-0-471-37039-0.
  • Sandi Klavžar, Ivan Gutman, Bojan Mohar. Labeling of benzenoid systems which reflects the vertex-distance relations // Journal of Chemical Information and Computer Sciences. — 1995. — Т. 35, вип. 3 (21 квітня). — С. 590–593. — DOI:10.1021/ci00025a030. Архівовано з джерела 3 липня 2021. Процитовано 28 червня 2021.
  • В. Б. Кузьмин, С. В. Овчинников. Геометрия пространств предпочтений. I // Автоматика и телемеханика. — 1975. — Вип. 12 (21 квітня). — С. 140-145.
  • Sergei Ovchinnikov. Graphs and Cubes. — Springer, 2011. — (Universitext). См. главу 5, «Partial Cubes», стр. 127—181.
  • Peter M. Winkler. Isometric embedding in products of complete graphs // Discrete Applied Mathematics. — 1984. — Т. 7, вип. 2 (21 квітня). — С. 221–225. — DOI:10.1016/0166-218X(84)90069-6.
Отримано з https://uk.wikipedia.org/w/index.php?title=Частковий_куб&oldid=39470964