LCME Понедельник, 24.04.2017, 02:26
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
Страница 1 из 11
Модератор форума: anatoliy 
Форум » Домашние задания » Программирование » Домашнее задание от 30.11 (Графы)
Домашнее задание от 30.11
freidomДата: Среда, 30.11.2011, 16:12 | Сообщение # 1
Главный тут
Группа: Администраторы
Сообщений: 273
Репутация: 20
Статус: 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). Теорема доказана.
Прикрепления: trans.java(2Kb)
 
Форум » Домашние задания » Программирование » Домашнее задание от 30.11 (Графы)
Страница 1 из 11
Поиск:

Copyright Freidom © 2017 Хостинг от uCoz