связность графа |
связность графа |
zeus |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 10 Пол: Мужской Репутация: 0 |
имеется связный орграф с 5 вершинами. необходимо найти наибольшее число дуг, удаление которых оставляет граф связным. помогите с алгоритмом, или если есть где нибудь он дайте ссылку. заранее спасибо
|
Michael_Rybak |
Сообщение
#2
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Смотри. Тебе надо перебрать все возможные варианты, когда какие-то дуги есть, а каких-то нет (удалены).
Пусть у нас 5 дуг. Получается у нас 2^5 = 32 варианта: от пустого графа, когда все дуги удалены, до исходного, в котором ничего не удалили. Эти варианты можно перебрать так. Вариант пусть задается набором из пяти чисел, каждое - 0 или 1. 0 = дуга удалена, 1 = дуга на месте. Нужно перебрать все наборы: 00000, 00001, 00010, 00011, 00100, ..., 11110, 11111. Эти наборы можно перебрать один за другим, просто переходя к каждому следующему, добавляя единичку в двоичной системе: var a: array [1..100] of integer; В результате процедура Process() по очереди вызовется для каждого набора. В ней ты проверяешь, связен ли граф с такими удаленными дугами, и если да, считаешь количество удаленных ребер, запоминая интересующий тебя максимум. |
Текстовая версия | 6.05.2024 10:06 |