Связность графа: различия между версиями

== Основные результаты ==

Нижние границы для k-связных остовных подграфов

Каждая вершина k-связного графа имеет по меньшей мере k инцидентных ей дуг. Следовательно, сумма степеней всех его вершин составляет по меньшей мере kn, где n – количество вершин графа. Поскольку в эту сумму каждое ребро входит дважды, мощность множества ребер составляет не менее kn/2. Назовем ее нижней границей степени. Несколько расширив эту идею, мы получим более сильную нижнюю границу мощности k-связного остовного подграфа исходного графа. Пусть Dk – подграф, у которого каждая вершина имеет степень не меньше k. В отличие от k-связного подграфа, Dk не имеет ограничений по связности. Согласно вышеприведенному рассуждению, Dk имеет не менее kn/2 ребер. Сведя задачу к задаче паросочетания, мы сможем вычислить Dk минимальной мощности за полиномиальное время; этот вариант будет называться нижней границей по паросочетанию.

Были предложены гибридные подходы, использующие покрытие путями и циклами для создания специфического DFS-дерева исходного графа и затем организации 2-связного дерева за счет удаления ребер везде, где это возможно. Использование таких подходов позволяет получить следующие коэффициенты аппроксимации в лучшем случае: 5/4 для задачи 2-ECSS, 9/7 для 2-VCSS и 5/4 для 2-VCSS в 3-связных графах.

== Применение ==