"Записки научных семинаров ПОМИ"
Том 427, стр. 22-40
Дерево разрезов и минимальный $k$-связный граф
Д. В. Карпов
С.-Петербургское
отделение Математического института
им. В А. Стеклова РАН,
Фонтанка 27, С.-Петербург;
Математико-механический
факультет СПбГУ,
С.Петербург, Россия
dvk0@yandex.ru
- Аннотация:
Разрез $k$-связного графа -- это $k$-элементное разделяющее множество,
содержащее хотя бы одно ребро. {\em Дерево разрезов} множества
$\mathfrak S$, состоящего из попарно независимых разезов
$k$-связного графа -- это двудольный граф, вершины одной доли которого
-- это разрезы из $\mathfrak S$, а вершины другой доли
-- части, на которые эти разрезы разбивают граф. Часть $A$ смежна с
разрезом $S$ если и только если она содержит все вершины разреза $S$
и по одному концу каждого его ребра. В статье доказывается,
что построенный таким образом граф является деревом и имеет свойства,
похожие на свойства классического дерева блоков и точек сочленения.
Во второй части статьи конструкция дерева разрезов применяется
для изучения свойств минимальных $k$-связных графов при $k\le 5$.
Библ. -- 11 назв.
- Ключевые слова: связность, дерево, минимальный $k$-связный граф
[connectivity, tree, minimal $k$-connected graph]
Полный текст(.pdf)