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

В теории графов «кактус» (иногда используется название кактусовое дерево) — это связный граф, в котором любые два простых цикла имеют не более одной общей вершины. Эквивалентно, любое ребро в таком графе принадлежит максимум одному простому циклу. Эквивалентно (для нетривиального кактуса), любой блок (максимальный подграф без шарниров) является ребром или циклом.

Кактусы являются внешнепланарными графами. Любое псевдодерево является кактусом.

Семейство графов, в которых каждая компонента является кактусом, замкнуты по операциям взятия минора графа. Это семейство графов можно описать указанием единственного запрещённого минора, «алмаза» с четырьмя вершинами, образованного удалением ребра из полного графа K₄^[1].

Кактусы, являясь частным случаем внешнепланарных графов, позволяют решать некоторые NP-трудные задачи о размещении объектов и другие задачи на графах за полиномиальное время, что было показано в работах Бен-Моше, Бхаттачарьи и Ши^[2], а также Змазека и Зеровника^[3]. Благодаря своей структуре, кактусы также упрощают решение многих задач комбинаторной оптимизации^[4].

Одним из ранних применений кактусов стало моделирование электрических цепей, особенно в контексте представления операционных усилителей, что исследовали Ниши и Чуа^[5][6][7]. В более поздних исследованиях кактусы нашли применение в сравнительной геномике для визуализации связей между геномами или их фрагментами^[8].

Связный кактус, у которого каждая вершина принадлежит не более чем двум блокам, называют декабристом ^[9]. Интересно, что любой полиэдральный граф содержит подграф-«декабрист», включающий все его вершины. Этот факт сыграл ключевую роль в доказательстве Лейтона и Мойтры^[10], утверждающем, что любой полиэдральный граф допускает жадное вложение в евклидову плоскость. Такое вложение позволяет назначать вершинам координаты так, что жадный алгоритм маршрутизации успешно доставляет сообщения между любыми парами вершин^[11].

Кактусы впервые изучались под названием деревья Хусими, данным им Фрэнком Харари и Джорджем Юджином Уленбеком в честь работавшего с этими графами японского физика, иностранного члена РАН^[12] Кодзи Фусими^[13][14] (в русскоязычной литературе по графам фамилию транскрибируют как Хусими^[15][16]). В той же статье используется название "кактус" для графов этого типа, в которых любой цикл является треугольником, но ныне разрешены циклы любой длины.

Между тем название дерево Хусими стали использовать для графов, в которых каждый блок является полным графом. Это название имеет мало общего с работой Хусими, и для графов этого семейства теперь используется более уместный термин «блоковый граф», а термин дерево Хусими используется всё реже.

• 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.

• Application of Cactus Graphs in Analysis and Design of Electronic Circuits