В теории графов«кактус» (иногда используется название кактусовое дерево) — это связный граф, в котором любые два простых цикла имеют не более одной общей вершины. Эквивалентно, любое ребро в таком графе принадлежит максимум одному простому циклу. Эквивалентно (для нетривиального кактуса), любой блок (максимальный подграф без шарниров) является ребром или циклом.
Семейство графов, в которых каждая компонента является кактусом, замкнуты по операциям взятия минора графа. Это семейство графов можно описать указанием единственного запрещённого минора, «алмаза» с четырьмя вершинами, образованного удалением ребра из полного графаK4[1].
Кактусы также недавно были использованы в сравнительной геномике[англ.] как средство представления связей между различными геномами или частями геномов[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.
