Loading AI tools
зв'язний граф, у якому будь-які два прості цикли мають не більше однієї спільної вершини З Вікіпедії, вільної енциклопедії
В теорії графів «кактус» (іноді використовується назва кактусове дерево) — це зв'язний граф, в якому будь-які два прості цикли мають не більше, ніж одну спільну вершину. Еквівалентно, будь-яке ребро в такому графі належить максимум одному простому циклу. Еквівалентно (для нетривіального кактуса), будь-який блок (максимальний підграф без шарнірів) є ребром або циклом.
Кактуси є зовніпланарними графами. Будь-яке псевдодерево є кактусом.
Сімейство графів, у яких кожна компонента є кактусом, замкнуті за операціями взяття мінора графу. Це сімейство графів можна описати зазначенням єдиного забороненого мінора, «алмаза» з чотирма вершинами, утвореного видаленням ребра з повного графу K4[1].
Деякі задачі про розміщення об'єктів, які є NP-складними для графів загального вигляду, як і деякі інші завдання на графах, можуть бути вирішені за поліноміальний час для кактусів[2][3].
Оскільки кактуси є частковими випадками зовніпланарних графів, багато задач комбінаторної оптимізації на графах можуть бути розв'язані за поліноміальний час[4].
Кактусами подаютьсь електричні кола, які мають корисні застосування. Раннє використання кактусів було пов'язане з поданням операційних підсилювачів[5][6][7].
Кактуси також недавно[коли?] були використані в порівняльній геноміці як засіб подання зв'язків між різними геномами або частинами геномів[8].
Якщо кактус зв'язний і кожна з його вершин належить не більше ніж двом блокам, його називають декабристом[9]. Будь-який багатогранний граф має підграфом «декабриста», який включає всі вершини графу, — факт, який грає істотну роль у доведенні Лейтона і Мойтри[10], що будь-який багатогранний граф має жадібне вкладення[ru] в евклідову площину, в якому вершини отримують координати так, що жадібний алгоритм відсилання[en] стає успішним у процесі розсилання повідомлень між усіма парами вершин[11].
Кактуси вперше вивчалися під назвою дерево Хусімі, наданою їм Френком Харарі і Джорджем Юджином Уленбеком на честь Коді Хусімі, який працював з цими графами[12][13]. У тій самій статті використовується назва «кактус» для графів цього типу, в яких будь-який цикл є трикутником, але нині дозволені цикли довільної довжини.
Тим часом назву «дерево Хусімі» стали використовувати для графів, у яких кожен блок є повним графом. Ця назва має мало спільного з роботою Хусімі, і для графів цього сімейства тепер використовується більш доречний термін «блоковий граф», а термін дерево Хусімі використовується все рідше[прояснити].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.