Русская Википедия:Кактус (теория графов)

Материал из Онлайн справочника
Версия от 14:41, 21 августа 2023; EducationBot (обсуждение | вклад) (Новая страница: «{{Русская Википедия/Панель перехода}} thumb|225px|Пример кактуса В теории графов '''«кактус»''' (иногда используется название '''кактусовое дерево''') — это связный граф, в котором любые два простых цикла и...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигацииПерейти к поиску

Файл:Cactus graph.svg
Пример кактуса

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

Свойства

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

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

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

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

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

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

Кактусы также недавно были использованы в Шаблон:Нп3 как средство представления связей между различными геномами или частями геномовШаблон:Sfn.

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

История

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

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

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ декабрист — популярный комнатный вид кактуса
  2. ↑ Шаблон:Cite web
  3. ↑ Шаблон:Cite web
  4. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Кактус_(теория_графов)&oldid=10059889