Пятница, 6 апреля, ауд. 106. Начало в 18:00.
Докладчик: Глеб Ненашев (СПбГУ).
Тема: Существование некритические вершин в ориентированных графах.
Abstract
Будет доказано, что в сильно связном орграфе на
![$ n $](../../../sites/default/files/tex/31360359740de028d2dd0d2cc8087938c3b61794/index.png)
вершинах, с минимальной степенью вершины
![$ n+1\over 2 $](../../../sites/default/files/tex/512def4858ca49dabe4af7cf57fde0c9e9ee6d02/index.png)
существует
некритическая вершина (то есть, вершина, при удалении которой не нарушается сильная связность).
Для сильно связного орграфе на
![$ n $](../../../sites/default/files/tex/31360359740de028d2dd0d2cc8087938c3b61794/index.png)
вершинах, с минимальной степенью вершины
![$ n+2\over 2 $](../../../sites/default/files/tex/3389e6ca941071d6ea699ba2325d7ea577682f7b/index.png)
будет доказано существование двух некритических вершин. Серии примеров покажут, что обе оценки --- точные.