| freidom | Дата: Среда, 30.11.2011, 16:12 | Сообщение # 1 |
 Главный тут
Группа: Администраторы
Сообщений: 273
Статус: Offline
|
- Построить транзитивное замыкание неорграфа и орграфа. Доказать корректность алгоритма с урока (письменно, на бумаге или в файле) или привести контрпример.
- Венгерский алгоритм поиска максимальных паросочетаний: разобраться и с его помощью решить задачу I с ВКОШПа.
Корректность:
Рассмотрим 2 вершины с номерами i, j. После транзитивного замыкания между ними появится ребро тогда и только тогда, когда между ними есть цепочка элементов i=a1, a2, a2, ..., a(n-1), an=j, причём есть рёбра a1-a2, a2-a3, ..., a(n-1)-an. Будем доказывать по индукции. База: n = 3. Тогда при прохождении алгоритма через вершину a2 появится ребро i-j, то есть всё хорошо. Пусть теперь n > 3. Пусть первой из вершин a2...a(n-1) алгоритм посещает вершину ak. Тогда появится ребро между вершинами a(k-1)-a(k+1). Прекрасно, тогда выкинем вершину ak из пути (она уже ни на что не влияет) и получим путь длиной (n-1). Теорема доказана.
|
| |
| |
