В теории графов «кактус» (иногда используется название кактусовое дерево) — это связный граф, в котором любые два простых цикла имеют не более одной общей вершины. Эквивалентно, любое ребро в таком графе принадлежит максимум одному простому циклу. Эквивалентно (для нетривиального кактуса), любой блок (максимальный подграф без шарниров) является ребром или циклом.
Свойства Кактусы являются внешнепланарными графами. Любое псевдодерево является кактусом.
Семейство графов, в которых каждая компонента является кактусом, замкнуты по операциям взятия минора графа. Это семейство графов можно описать указанием единственного запрещённого минора, «алмаза» с четырьмя вершинами, образованного удалением ребра из полного графа K4.
Алгоритмы и приложения Кактусы, являясь частным случаем внешнепланарных графов, позволяют решать некоторые NP-трудные задачи о размещении объектов и другие задачи на графах за полиномиальное время, что было показано в работах Бен-Моше, Бхаттачарьи и Ши, а также Змазека и Зеровника. Благодаря своей структуре, кактусы также упрощают решение многих задач комбинаторной оптимизации.
Одним из ранних применений кактусов стало моделирование электрических цепей, особенно в контексте представления операционных усилителей, что исследовали Ниши и Чуа. В более поздних исследованиях кактусы нашли применение в для визуализации связей между геномами или их фрагментами.
Связный кактус, у которого каждая вершина принадлежит не более чем двум блокам, называют декабристом декабрист — популярный комнатный вид кактуса. Интересно, что любой полиэдральный граф содержит подграф-«декабрист», включающий все его вершины. Этот факт сыграл ключевую роль в доказательстве Лейтона и Мойтры, утверждающем, что любой полиэдральный граф допускает в евклидову плоскость. Такое вложение позволяет назначать вершинам координаты так, что успешно доставляет сообщения между любыми парами вершин.
История Кактусы впервые изучались под названием деревья Хусими, данным им Фрэнком Харари и Джорджем Юджином Уленбеком в честь работавшего с этими графами японского физика, иностранного члена РАН (в русскоязычной литературе по графам фамилию транскрибируют как Хусими). В той же статье используется название "кактус" для графов этого типа, в которых любой цикл является треугольником, но ныне разрешены циклы любой длины.
Между тем название дерево Хусими стали использовать для графов, в которых каждый блок является полным графом. Это название имеет мало общего с работой Хусими, и для графов этого семейства теперь используется более уместный термин «блоковый граф», а термин дерево Хусими используется всё реже.
Примечания
Литература
Ссылки Application of Cactus Graphs in Analysis and Design of Electronic Circuits
Категория:Семейства графов Категория:Планарные графы Категория:Интегральные схемы