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

Перейти к навигацииПерейти к поиску
Пример кактуса

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

Свойства

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

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

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

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

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

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

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

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

История

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

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

Примечания

  1. ↑ El-Mallah, Colbourn, 1988, с. 354–362.
  2. ↑ Ben-Moshe, Bhattacharya, Shi, 2005, с. 693–703.
  3. ↑ Zmazek, Zerovnik, 2005, с. 536–541.
  4. ↑ Корнеенко, 1984, с. 215–217.
  5. ↑ Nishi, Chua [2], 1986, с. 398–405.
  6. ↑ Nishi, Chua [1], 1986, с. 381–397.
  7. ↑ Nishi, 1991, с. 766–769.
  8. ↑ Paten, Diekhans и др., 2010, с. 410–425.
  9. ↑ декабрист — популярный комнатный вид кактуса
  10. ↑ Leighton, Moitra, 2010.
  11. ↑ Leighton, Moitra, 2010, с. 686–705.
  12. ↑ Фусими Кодзи. | ИС АРАН. Дата обращения: 1 июля 2022. Архивировано 4 июня 2021 года.
  13. ↑ Harary, Uhlenbeck, 1953, с. 315–322.
  14. ↑ Husimi, 1950, с. 682–684.
  15. ↑ К. А. Зарецкий, “О деревьях Хусими”, Матем. заметки, 9:3 (1971), 253–262; Math. Notes, 9:3 (1971), 150–154. Дата обращения: 27 августа 2020. Архивировано 4 июня 2021 года.
  16. ↑ Расин О. В. Алгоритм проверки изоморфизма деревьев Хусими / О. В. Расин // Известия Уральского государственного университета. — 2004. — № 30. — С. 126-136. Дата обращения: 27 августа 2020. Архивировано 4 июня 2021 года.

Литература

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

Ссылки