WikiSort.ru - Не сортированное

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

Свойства

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

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

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

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

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

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

Кактусы также недавно были использованы в сравнительной геномике^[en] как средство представления связей между различными геномами или частями геномов^[8].

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

История

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

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

Примечания

Литература

• 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. {{{заглавие}}} // 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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.