Пятница 15 ноября, 15-15, ауд. 203

Пятница, 15 ноября, ауд. 203. Начало в 15:15.

Докладчик: Д.В. Карпов (ПОМИ РАН).

Тема: Минимальные двусвязные графы.

Abstract

Двусвязный граф называется минимальным, если при удалении любого его ребра теряется двусвязность. В работе доказано, что для любого минимального двусвязного графа

существует последовательность минимальных двусвязных графов

, ...,

, в которой граф

имеет только вершины степеней 2 и 3, а каждый следующий граф получается из предыдущего стягиванием ребра, соединяющего две вершины степени не менее 3.

В работе изучаются минимальные двусвязные графы, содержащие наименьшее возможное число вершин степени~2. Обозначим множество таких графов на

вершинах через

. Как известно, в графах из

должно быть ровно по

вершин степени~2. Доказывается, что для

при

состоит из графов вида

, где

--- дерево на

вершинах, степени вершин которого не превосходят 3. Граф

строится из двух копий дерева

: к каждой паре соответствующих вершин которых добавляются смежные с ними вершины степени 2 (так, чтобы степени всех вершин исходных двух деревьев стали равнны 3). Графы из

и

также характеризованы с помощью графов вида

.