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

Свойства

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

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

Алгоритмы и приложения

Некоторые задачи о размещении объектов , являющиеся NP-трудными для графов общего вида, как и некоторые другие задачи на графах, могут быть решены за полиномиальное время для кактусов .

Поскольку кактусы являются специальными случаями внешнепланарных графов , многие задачи комбинаторной оптимизации на графах могут быть решены за полиномиальное время .

Кактусы представляют электрические цепи , имеющие полезные свойства. Раннее приложение кактусов было связано с представлением операционных усилителей .

Кактусы также недавно были использованы в (англ.) ( как средство представления связей между различными геномами или частями геномов .

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

История

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

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

Примечания

Литература

• 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 : .
• Boaz Ben-Moshe, Binay Bhattacharya, Qiaosheng Shi. Algorithms and Computation, 16th Int. Symp., ISAAC 2005. — Springer-Verlag, 2005. — Т. 3827. — С. 693–703. — ( ). — doi : .
• Blaz Zmazek, Janez Zerovnik. Ninth International Conference on Information Visualisation (IV'05). — 2005. — С. 536–541. — ISBN 0-7695-2397-8 . — doi : .
• Н.М. Корнеенко. Комбинаторные алгоритмы на классе графов // Известия Национальной академии наук Беларуси СЕРИЯ ФИЗИКО-ТЕХНИЧЕСКИХ НАУК. — 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 : .
• 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 : .
• 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 : .
• Tom Leighton, Ankur Moitra. Some Results on Greedy Embeddings in Metric Spaces // . — 2010. — Т. 44 , вып. 3 . — С. 686–705 . — doi : .
• 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 : .
• Kodi Husimi. // Journal of Chemical Physics. — 1950. — Т. 18 , вып. 5 . — С. 682–684 . — doi : .

Ссылки