Редактирование: Список заданий по АСД

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 144: Строка 144:
 
# В регулярном графе $G$ степень любой вершины $k$ и $\lambda(G) \ge k - 1$. Докажите, что в $G$ есть полное паросочетание.
 
# В регулярном графе $G$ степень любой вершины $k$ и $\lambda(G) \ge k - 1$. Докажите, что в $G$ есть полное паросочетание.
 
# Докажите, что ребра кубического графа можно раскрасить в разные цвета так, что для каждого цвета существует ровно три ребра этого цвета, причем они представляют собой простой путь.
 
# Докажите, что ребра кубического графа можно раскрасить в разные цвета так, что для каждого цвета существует ровно три ребра этого цвета, причем они представляют собой простой путь.
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число операций relabel с каждой вершиной не превышает $3V$.
+
 
# Пусть $f$ - поток, а $f'$ - псевдопоток (выполнены все аксиомы, кроме сохранения потока). Пусть в вершине $u$ есть положительный избыток $f'$. Докажите, что в $G_f$ есть путь из $u$ до некоторой вершины, в которой есть положительный недостаток $f'$ по ненасыщенным ребрам.
 
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число насыщающих операций push есть $O(VE)$.
 
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число ненасыщающих операций push есть $O(V^2E)$.
 
# Докажите, что в алгоритме масштабирования стоимостей для поиска потока минимальной стоимости на каждой фазе число ненасыщающих операций push есть $O(V^2E)$.
 
# Пусть $f^*$ - поток минимальной стоимости. Пусть поток $f$ является $\varepsilon$-оптимальным, причем $\varepsilon(f)=\varepsilon$. Пусть $\varepsilon' < \varepsilon/V$. Докажите, что если $f'$ является $\varepsilon'$-оптимальным потоком, то существует ребро, поток $f'$ по которому совпадает с потоком $f^*$, а поток $f$ - нет.
 
# Докажите, что если $\varepsilon(f) = \varepsilon$ и $f'$ получен из $f$ дополнением по циклу минимальной средней стоимости, то $\varepsilon(f')\le (1-1/V)\varepsilon$.
 
 
</wikitex>
 
</wikitex>

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)