Кактус (теорія графів): відмінності між версіями
Створено шляхом перекладу сторінки «Кактус (теория графов)» |
(Немає відмінностей)
|
Версія за 01:48, 14 лютого 2020
В теорії графів «кактус» (іноді використовується назва кактусове дерево) - це зв'язний граф, в якому будь-які два прості цикли мають не більше, ніж одну спільну вершину. Еквівалентно, будь-яке ребро в такому графі належить максимум одному простому циклу. Еквівалентно (для нетривіального кактуса), будь-який блок (максимальний підграф без шарнірів) є ребром або циклом.
Властивості
Кактуси є зовнішньопланарними графами . Будь-яке псевдодерево є кактусом.
Сімейство графів, у яких кожна компонента є кактусом, замкнуті за операціями взяття мінора графа. Це сімейство графів можна описати зазначенням єдиного забороненого мінору , «алмаза» з чотирма вершинами, утвореного видаленням ребра з повного графа K4[1].
Алгоритми та застосування
Деякі задачі про розміщення об'єктів[ru], які є NP-складними для графів загального вигляду, як і деякі інші завдання на графах, можуть бути вирішені за поліноміальний час для кактусів[2][3].
Оскільки кактуси є частковими випадками зовнішньопланарних графів, багато задач комбінаторної оптимізації на графах можуть бути розв'язані за поліноміальний час[4].
Кактусами подаютьсь електричні кола, які мають корисні застосування. Раннє використання кактусів було пов'язане з поданням операційних підсилювачів[5][6][7].
Кактуси також недавно[коли?] були використані в порівняльній геноміці як засіб подання зв'язків між різними геномами або частинами геномів[8].
Якщо кактус зв'язний і кожна з його вершин належить не більше ніж двом блокам, його називають декабристом[9]. Будь-який багатогранний граф має підграфом «декабриста», який включає всі вершини графа, - факт, який грає істотну роль у доведенні Лейтона і Мойтри[10], що будь-який багатогранний граф має жадібне вкладення[ru] в евклідову площину, в якому вершини отримують координати так, що жадібний алгоритм відсилання[en] стає успішним у процесі розсилання повідомлень між усіма парами вершин[11].
Історія
Кактуси вперше вивчалися під назвою
"дерево Хусімі", наданою їм Френком Харарі і Джорджем Юджином Уленбеком на честь Коді Хусімі, який працював з цими графами[12][13]. У тій самій статті використовується назва "кактус" для графів цього типу, в яких будь-який цикл є трикутником, але нині дозволені цикли довільної довжини.
Тим часом назву "дерево Хусімі" стали використовувати для графів, у яких кожен блок є повним графом. Ця назва має мало спільного з роботою Хусімі, і для графів цього сімейства тепер використовується більш доречний термін «блоковий граф», а термін дерево Хусімі використовується все рідше[прояснити].
Примітки
- ↑ El-Mallah, Colbourn, 1988, с. 354–362.
- ↑ Ben-Moshe, Bhattacharya, Shi, 2005, с. 693–703.
- ↑ Zmazek, Zerovnik, 2005, с. 536–541.
- ↑ Корниенко, 1984, с. 215–217.
- ↑ Nishi, Chua [2], 1986, с. 398–405.
- ↑ Nishi, Chua [1], 1986, с. 381–397.
- ↑ Nishi, 1991, с. 766–769.
- ↑ Paten, Diekhans и др., 2010, с. 410–425.
- ↑ декабрист — популярный комнатный вид кактуса
- ↑ Leighton, Moitra, 2010.
- ↑ Leighton, Moitra, 2010, с. 686–705.
- ↑ Harary, Uhlenbeck, 1953, с. 315–322.
- ↑ Husimi, 1950, с. 682–684.
Література
- Ehab El-Mallah, Charles J. Colbourn. // IEEE Transactions on Circuits and Systems. — 1988. — Т. 35, вип. 3. — С. 354–362. — DOI: .
- Boaz Ben-Moshe, Binay Bhattacharya, Qiaosheng Shi. {{{Заголовок}}}. — Springer-Verlag, 2005. — Т. 3827. — С. 693–703. — (Lecture Notes in Computer Science) — DOI:
- Blaz Zmazek, Janez Zerovnik. {{{Заголовок}}}. — 2005. — С. 536–541. — ISBN 0-7695-2397-8. — DOI:
- Н.М. Корниенко. // Известия Национальной академии наук Беларуси СЕРИЯ ФИЗИКО-ТЕХНИЧЕСКИХ НАУК. — 1984. — Вип. 3. — С. 109-111.
- Tetsuo Nishi, Leon O. Chua. // IEEE Transactions on Circuits and Systems. — 1986. — Т. 33, вип. 4. — С. 398–405. — DOI: .
- Tetsuo Nishi, Leon O. Chua. // IEEE Transactions on Circuits and Systems. — 1986. — Т. 33, вип. 4. — С. 381–397. — DOI: .
- Tetsuo Nishi. {{{Заголовок}}}. — 1991. — С. 766–769.
- Benedict Paten, Mark Diekhans, Dent Earl, John St. John, Jian Ma, Bernard Suh, David Haussler. // Lecture Notes in Computer Science. — 2010. — Т. 6044. — С. 410–425. — (Lecture Notes in Computer Science). — ISBN 978-3-642-12682-6. — DOI: .
- Tom Leighton, Ankur Moitra. [1] // Discrete & Computational Geometry. — 2010. — Т. 44, вип. 3. — С. 686–705. — DOI: .
- Frank Harary, George E. Uhlenbeck. // Proceedings of the National Academy of Sciences. — 1953. — Т. 39, вип. 4. — С. 315–322. — DOI: .
- Kodi Husimi. // Journal of Chemical Physics. — 1950. — Т. 18, вип. 5. — С. 682–684. — DOI: .
Посилання
- Application of Cactus Graphs in Analysis and Design of Electronic Circuits