Кактус (теорія графів)

В теорії графів «кактус» (іноді використовується назва кактусове дерево) — це зв'язний граф, в якому будь-які два прості цикли мають не більше, ніж одну спільну вершину. Еквівалентно, будь-яке ребро в такому графі належить максимум одному простому циклу. Еквівалентно (для нетривіального кактуса), будь-який блок (максимальний підграф без шарнірів) є ребром або циклом.

Приклад кактуса

Властивості

Кактуси є зовнішньопланарними графами. Будь-яке псевдодерево є кактусом.

Сімейство графів, у яких кожна компонента є кактусом, замкнуті за операціями взяття мінора графу. Це сімейство графів можна описати зазначенням єдиного забороненого мінора, «алмаза» з чотирма вершинами, утвореного видаленням ребра з повного графу K4[1].

Алгоритми та застосування

Деякі задачі про розміщення об'єктів, які є NP-складними для графів загального вигляду, як і деякі інші завдання на графах, можуть бути вирішені за поліноміальний час для кактусів[2][3].

Оскільки кактуси є частковими випадками зовнішньопланарних графів, багато задач комбінаторної оптимізації на графах можуть бути розв'язані за поліноміальний час[4].

Кактусами подаютьсь електричні кола, які мають корисні застосування. Раннє використання кактусів було пов'язане з поданням операційних підсилювачів[5][6][7].

Кактуси також недавно[коли?] були використані в порівняльній геноміці як засіб подання зв'язків між різними геномами або частинами геномів[8].

Якщо кактус зв'язний і кожна з його вершин належить не більше ніж двом блокам, його називають декабристом[9]. Будь-який багатогранний граф має підграфом «декабриста», який включає всі вершини графу, — факт, який грає істотну роль у доведенні Лейтона і Мойтри[10], що будь-який багатогранний граф має жадібне вкладення в евклідову площину, в якому вершини отримують координати так, що жадібний алгоритм відсилання стає успішним у процесі розсилання повідомлень між усіма парами вершин[11].

Історія

Кактуси вперше вивчалися під назвою дерево Хусімі, наданою їм Френком Харарі і Джорджем Юджином Уленбеком на честь Коді Хусімі, який працював з цими графами[12][13]. У тій самій статті використовується назва «кактус» для графів цього типу, в яких будь-який цикл є трикутником, але нині дозволені цикли довільної довжини.

Тим часом назву «дерево Хусімі» стали використовувати для графів, у яких кожен блок є повним графом. Ця назва має мало спільного з роботою Хусімі, і для графів цього сімейства тепер використовується більш доречний термін «блоковий граф», а термін дерево Хусімі використовується все рідше[прояснити].

Примітки
  1. El-Mallah, Colbourn, 1988, с. 354–362.
  2. Ben-Moshe, Bhattacharya, Shi, 2005, с. 693–703.
  3. Zmazek, Zerovnik, 2005, с. 536–541.
  4. Корниенко, 1984, с. 215–217.
  5. Nishi, Chua [2], 1986, с. 398–405.
  6. Nishi, Chua [1], 1986, с. 381–397.
  7. Nishi, 1991, с. 766–769.
  8. Paten, Diekhans и др., 2010, с. 410–425.
  9. декабрист — популярный комнатный вид кактуса
  10. Leighton, Moitra, 2010.
  11. Leighton, Moitra, 2010, с. 686–705.
  12. Harary, Uhlenbeck, 1953, с. 315–322.
  13. Husimi, 1950, с. 682–684.

Література
  • Ehab El-Mallah, Charles J. Colbourn. The complexity of some edge deletion problems // IEEE Transactions on Circuits and Systems. — 1988. — Т. 35, вип. 3. — С. 354–362. — DOI:10.1109/31.1748.
  • Boaz Ben-Moshe, Binay Bhattacharya, Qiaosheng Shi. Algorithms and Computation, 16th Int. Symp., ISAAC 2005. — Springer-Verlag, 2005. — Т. 3827. — С. 693–703. — (Lecture Notes in Computer Science). — DOI:10.1007/11602613_70.
  • Blaz Zmazek, Janez Zerovnik. Ninth International Conference on Information Visualisation (IV'05). — 2005. — С. 536–541. — ISBN 0-7695-2397-8. — DOI:10.1109/IV.2005.48.
  • Н.М. Корниенко. Комбинаторные алгоритмы на классе графов // Известия Национальной академии наук Беларуси СЕРИЯ ФИЗИКО-ТЕХНИЧЕСКИХ НАУК. — 1984. — Вип. 3. — С. 109-111.
  • Tetsuo Nishi, Leon O. Chua. Topological proof of the Nielsen-Willson theorem // IEEE Transactions on Circuits and Systems. — 1986. — Т. 33, вип. 4. — С. 398–405. — DOI:10.1109/TCS.1986.1085935.
  • Tetsuo Nishi, Leon O. Chua. Uniqueness of solution for nonlinear resistive circuits containing CCCS’s or VCVS’s whose controlling coefficients are finite // IEEE Transactions on Circuits and Systems. — 1986. — Т. 33, вип. 4. — С. 381–397. — DOI:10.1109/TCS.1986.1085934.
  • Tetsuo Nishi. Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore. — 1991. — С. 766–769.
  • Benedict Paten, Mark Diekhans, Dent Earl, John St. John, Jian Ma, Bernard Suh, David Haussler. Research in Computational Molecular Biology // Lecture Notes in Computer Science. — 2010. — Т. 6044. — С. 410–425. — ISBN 978-3-642-12682-6. — DOI:10.1007/978-3-642-12683-3_27.
  • Tom Leighton, Ankur Moitra. Some Results on Greedy Embeddings in Metric Spaces // Discrete & Computational Geometry. — 2010. — Т. 44, вип. 3. — С. 686–705. — DOI:10.1007/s00454-009-9227-6.
  • Frank Harary, George E. Uhlenbeck. On the number of Husimi trees, I // Proceedings of the National Academy of Sciences. — 1953. — Т. 39, вип. 4. — С. 315–322. — DOI:10.1073/pnas.39.4.315.
  • Kodi Husimi. Note on Mayers' theory of cluster integrals // Journal of Chemical Physics. — 1950. — Т. 18, вип. 5. — С. 682–684. — DOI:10.1063/1.1747725.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.