Home

Пятница 6 апреля, 18-00, ауд. 106

Пятница, 6 апреля, ауд. 106. Начало в 18:00.

Докладчик: Глеб Ненашев (СПбГУ).

Тема: Существование некритические вершин в ориентированных графах.

Abstract

Будет доказано, что в сильно связном орграфе на $ n $ вершинах, с минимальной степенью вершины $ n+1\over 2 $ существует некритическая вершина (то есть, вершина, при удалении которой не нарушается сильная связность). Для сильно связного орграфе на $ n $ вершинах, с минимальной степенью вершины $ n+2\over 2 $ будет доказано существование двух некритических вершин. Серии примеров покажут, что обе оценки --- точные.