|
Название: Снова графы, ня. Отправлено: Sirion от Январь 19, 2012, 20:45:40 Пусть у нас есть связный граф на n вершинах. Найти минимальное k=k(n) такое, что независимо от конфигурации этого графа мы можем добавить в него не более k рёбер так, чтобы каждая его вершина содержалась в некотором цикле? Кратные рёбра и петли традиционно запрещены.
Название: Re: Снова графы, ня. Отправлено: zhekas от Январь 19, 2012, 21:26:29 [n/2]
Название: Re: Снова графы, ня. Отправлено: iPhonograph от Январь 19, 2012, 21:45:35 жекас, а для n=2 тоже ?
:) кратные рёбра запрещены, НЯ ! Название: Re: Снова графы, ня. Отправлено: Sirion от Январь 19, 2012, 22:06:28 да, пожалуй, стоит оговорить, что n больше всякого чётного простого числа)
|