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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 112: Строка 112:
 
# Предложите реализацию алгоритма двух китайцев за $O(E \log E)$.
 
# Предложите реализацию алгоритма двух китайцев за $O(E \log E)$.
 
# Предложите алгоритм поиска остовного дерева с минимальным весом максимального ребра за время равное работе алгоритма поиска MST.
 
# Предложите алгоритм поиска остовного дерева с минимальным весом максимального ребра за время равное работе алгоритма поиска MST.
# Петя в алгоритме Форда-Фалкерсона для поиска паросочетания в двудольном графе сделал ошибку: оставил рёбра между долями графа неориентированными. Построить пример, на котором алгоритм будет работать неправильно.
 
# Доказать теорему Холла: что в двудольном графе $G$ существует полное паросочетание тогда и только тогда, когда для любого множества вершин левой доли $A \subset X$ выполнено $|N(A)| \ge |A|$. ($N(A)$ - множество соседей вершин из $A$)
 
# Докажите, что в регулярном двудольном графе существует полное паросочетание.
 
# Дефектом множества вершин левой доли в графе называется $def(A) = |N(A)| - |A|$. Найти в двудольном графе множество с минимальным дефектом.
 
# Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом вершинно-непересекающихся путей. Сведите эту задачу к задаче о максимальном паросочетании.
 
# Дан ациклический ориентированный граф. Нужно покрыть его минимальным числом реберно-непересекающихся путей.
 
# Докажите, что если в графе единственное полное паросочетание, то в нем есть мост
 
# Предложите алгоритм проверки, что в двудольном графе четное число полных паросочетаний
 
# Предложите алгоритм проверки по двудольному графу и заданному полному паросочетанию, является ли оно единственным в этом графе (за $O(E)$).
 
# Предложите алгоритм для решения следующей задачи за $O(E)$. Дан двудольный граф и полное паросочетание в нем. Требуется выяснить для каждого ребра, лежит ли оно на некотором полном паросочетании.
 
# Задача об устойчивом паросочетании. Задан двудольный граф с равным числом вершин в долях. Для каждой вершины каждой доли известен порядок предпочтения вершин другой доли (каждая вершина знает, какая вершина другой доли ей нравится больше всего, какая вершина на втором месте, и так далее). Паросочетание называется устойчивым, если никакие две вершины не могут обменяться парами, чтобы для каждой из них новый партнер стал более предпочтительным. Требуется построить устойчивое полное паросочетание за $O(VE)$.
 
# Пусть $G$ - регулярный двудольный граф степени $k$. Докажите, что ребра $G$ можно разбить на $k$ полных паросочетаний.
 
# Пусть $G$ - регулярный граф степени $k$, $U \subset V$, $U$ содержит нечетное число вершин и $m$ - число ребер, которые соединяют вершины $U$ с вершинами $V \setminus U$. Тогда $m$ четно тогда и только тогда, когда $k$ четно.
 
# Докажите, что в двусвязном кубическом графе есть полное паросочетание.
 
# Докажите, что если в кубическом графе не более двух мостов, то в нем есть полное паросочетание.
 
# Приведите пример кубического графа, в котором нет полного паросочетания.
 
# Докажите, что если $f$ - поток, и в графе $G_f$ нет циклов отрицательного веса и пути отрицательного веса из $s$ в $t$, то $f$ - поток минимальной стоимости среди всех потоков в $G$ (вне зависимости от величины).
 
# Пусть в графе нет циклов отрицательной стоимости. Рассмотрим алгоритм: начав с нулевого потока, каждый раз дополняем поток вдоль пути минимальной стоимости способности из $s$ в $t$ в остаточной сети. Докажите, что стоимости найденных путей не убывают.
 
# Пусть в графе нет циклов отрицательной стоимости. Предложите алгоритм поиска потока минимальной среди всех потоков стоимости (вне зависимости от величины).
 
# Предложите алгоритм проверки, что в графе единственный минимальный разрез
 
# Докажите реберную теорему Менгера: минимальное число ребер, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу реберно непересекающихся путей из $s$ в $t$.
 
# Докажите вершнинную теорему Менгера: минимальное число вершин, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу вершинно непересекающихся путей из $s$ в $t$ ($s$ и $t$ удалять нельзя).
 
# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
 
# Постройте граф, в котором алгоритм Форда-Фалкерсона (ФФ) находит $\Omega(C_{max})$ путей. Веса всех рёбер целочисленные.
 
# Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(V E)$ дополнений до пути.
 
# Доказать теорему о декомпозиционном барьере. (см. вики-конспекты)
 
# Альтернативная реализация масштабирования потока $-$ на каждом шаге рассматриваем рёбра с пропускной способностью $c \ge 2^{k-i}$. Доказать, что для такой реализации время работы $O(EEk)$.
 
# $f_{max}$ - макс. поток, $f_{blocking}$ - блокирующий поток. Доказать, что $\frac {|f_{blocking}|} { |f_{max}|} $ может быть сколь угодно мало.
 
# Доказать, что если в алгоритме масштабирования использовать алгоритм Диница вместо ФФ, то время работы равно $O(E V k)$.
 
# Доказать, что на графе с целочисленными пропускными способностями рёбер число итераций while в алгоритме Диница равно $O(V^{\frac{2}{3}} {c_{max}}^{\frac{1}{3}})$.
 
# Доказать, что на графе с целочисленными пропускными способностями рёбер число итераций алгоритма Диница равно $O(V^{\frac{1}{2}} * c(G)^{\frac{1}{2}})$.
 

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

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

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