Пятница, 15 ноября, ауд. 203. Начало в 15:15.
Докладчик: Д.В. Карпов (ПОМИ РАН).
Тема: Минимальные двусвязные графы.
В работе изучаются минимальные двусвязные графы, содержащие наименьшее возможное число вершин степени~2. Обозначим множество таких графов на вершинах через
. Как известно, в графах из
должно быть ровно по
вершин степени~2. Доказывается, что для
при
состоит из графов вида
, где
--- дерево на
вершинах, степени вершин которого не превосходят 3. Граф
строится из двух копий дерева
: к каждой паре соответствующих вершин которых добавляются смежные с ними вершины степени 2 (так, чтобы степени всех вершин исходных двух деревьев стали равнны 3). Графы из
и
также характеризованы с помощью графов вида
.