Home

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

  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-1 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-2 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-3 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-4 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-5 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-6 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-7 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-8 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-9 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-10 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-11 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-12 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-13 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-14 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-15 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-16 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-17 has been created.
  • The directory /tmp/drutex-0c6ad9adaa0522b1926bdc360c6a8d4c-18 has been created.

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

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

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

Abstract

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

В работе изучаются минимальные двусвязные графы, содержащие наименьшее возможное число вершин степени~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!.