Кактус граф
В теории графов кактус ( иногда называемый кактусовым деревом ) — это связный граф , в котором любые два простых цикла имеют не более одной общей вершины. Эквивалентно, это связный граф, в котором каждое ребро принадлежит не более чем одному простому циклу или (для нетривиального кактуса), в котором каждый блок (максимальный подграф без вершины среза ) является ребром или циклом.
Кактусы являются внешнепланарными графами . Каждое псевдодерево — это кактус. Нетривиальный граф является кактусом тогда и только тогда, когда каждый блок является либо простым циклом , либо одним ребром.
Семейство графов, в котором каждая компонента является кактусом, замкнуто сверху вниз относительно второстепенных графовых операций. Это семейство графов может быть охарактеризовано единственным запрещенным минором , четырехвершинным ромбовидным графом , образованным удалением ребра из полного графа K 4 . [1]
Треугольный кактус — это особый тип кактусового графа, в котором каждый цикл имеет длину три и каждое ребро принадлежит циклу. Например, графы дружбы , образованные набором треугольников, соединенных вместе в одной общей вершине, представляют собой треугольные кактусы. Треугольные кактусы являются не только графами кактусов, но и блочными графами и локально линейными графами .
Треугольные кактусы обладают тем свойством, что они остаются связанными, если из них удалить любое совпадение ; для данного количества вершин они имеют наименьшее возможное количество ребер с этим свойством. Каждое дерево с нечетным числом вершин можно увеличить до треугольного кактуса, добавив к нему ребра, что даст минимальное увеличение со свойством оставаться связанным после удаления соответствия. [2]
Самый большой треугольный кактус в любом графе может быть найден за полиномиальное время с помощью алгоритма матроидной проблемы четности . Поскольку треугольные графы кактусов являются планарными графами , самый большой треугольный кактус можно использовать в качестве приближения к самому большому плоскому подграфу, что является важной подзадачей планаризации . В качестве алгоритма аппроксимации этот метод имеет коэффициент аппроксимации 4/9, наиболее известный для задачи максимального плоского подграфа. [3]
