Home

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

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

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

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

Abstract

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