RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Межкафедральный семинар МФТИ по дискретной математике
8 октября 2014 г. 18:30, г. Долгопрудный, МФТИ, Корпус Прикладной Математики, 115
 


Деревья и структура связности графа

Д. В. Карпов

Ленинградское отделение Математического института им. В. А. Стеклова РАН

Количество просмотров:
Эта страница:109

Аннотация: Первая проблема, которой посвящён доклад — выделение в связном графе остовного дерева с большим количеством листьев. Будет рассказано о различных оценках на это количество и показаны серии примеров графов, на которых оценки достигаются. Вторая проблема — построение дерева, отображающего структуру разбиения $k$-связного графа его $k$-вершинными разделяющими множества. Для связных графов есть классическое дерево блоков и точек сочленения, которое широко применяется в теории графов (причём не только в теории связности). Уже для двухсвязного графа аналогичная конструкция намного сложнее. Мы расскажем про такую конструкцию для $k=2$ и ее применение, а также про различные обобщения на случай $k>2$. В докладе будет рассказано об истории этих вопросов и некоторых новых результатах автора.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020