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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Пример кактуса

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

Свойства[править | править код]

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

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

Ссылки[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=Кактус_(теория_графов)&oldid=123729465