В теорії графів «кактус» (іноді використовується назва кактусове дерево) — це зв'язний граф, в якому будь-які два прості цикли мають не більше, ніж одну спільну вершину. Еквівалентно, будь-яке ребро в такому графі належить максимум одному простому циклу. Еквівалентно (для нетривіального кактуса), будь-який блок (максимальний підграф без шарнірів) є ребром або циклом.
Властивості Кактуси є зовніпланарними графами. Будь-яке псевдодерево є кактусом.
Сімейство графів, у яких кожна компонента є кактусом, замкнуті за операціями взяття мінора графу. Це сімейство графів можна описати зазначенням єдиного забороненого мінора, «алмаза» з чотирма вершинами, утвореного видаленням ребра з повного графу K4.
Алгоритми та застосування Деякі задачі про розміщення об'єктів, які є NP-складними для графів загального вигляду, як і деякі інші завдання на графах, можуть бути вирішені за поліноміальний час для кактусів.
Оскільки кактуси є частковими випадками зовніпланарних графів, багато задач комбінаторної оптимізації на графах можуть бути розв'язані за поліноміальний час.
Кактусами подаютьсь електричні кола, які мають корисні застосування. Раннє використання кактусів було пов'язане з поданням операційних підсилювачів.
Кактуси також недавно були використані в порівняльній геноміці як засіб подання зв'язків між різними геномами або частинами геномів.
Якщо кактус зв'язний і кожна з його вершин належить не більше ніж двом блокам, його називають декабристомдекабрист — популярний кімнатний вид кактусів. Будь-який багатогранний граф має підграфом «декабриста», який включає всі вершини графу, — факт, який грає істотну роль у доведенні Лейтона і Мойтри, що будь-який багатогранний граф має в евклідову площину, в якому вершини отримують координати так, що стає успішним у процесі розсилання повідомлень між усіма парами вершин.
Історія Кактуси вперше вивчалися під назвою дерево Хусімі, наданою їм Френком Харарі і Джорджем Юджином Уленбеком на честь Коді Хусімі, який працював з цими графами. У тій самій статті використовується назва «кактус» для графів цього типу, в яких будь-який цикл є трикутником, але нині дозволені цикли довільної довжини.
Тим часом назву «дерево Хусімі» стали використовувати для графів, у яких кожен блок є повним графом. Ця назва має мало спільного з роботою Хусімі, і для графів цього сімейства тепер використовується більш доречний термін «блоковий граф», а термін дерево Хусімі використовується все рідше.
Примітки
Література
Посилання Application of Cactus Graphs in Analysis and Design of Electronic Circuits