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