IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> связность графа
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


имеется связный орграф с 5 вершинами. необходимо найти наибольшее число дуг, удаление которых оставляет граф связным. помогите с алгоритмом, или если есть где нибудь он дайте ссылку. заранее спасибо
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


code warrior
****

Группа: Пользователи
Сообщений: 484
Пол: Мужской
Реальное имя: Славен

Репутация: -  8  +


Думаю вам нужен алгоритм нахождения минимального остовного дерева.


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Полным перебором пробуешь выбрасывать все возможные наборы дуг, и каждый раз проверяешь, связен ли полученный граф.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Цитата(Michael_Rybak @ 8.09.2007 3:58) *

Полным перебором пробуешь выбрасывать все возможные наборы дуг, и каждый раз проверяешь, связен ли полученный граф.


а как можно проверять связность графа, тоже нужен алгоритм?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Связность графа проверяешь так: алгоритмом Флойда заполняешь матрицу достижимости, а потом проверяешь, что все пары вершин - связаны.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Цитата(Michael_Rybak @ 8.09.2007 3:58) *

Полным перебором пробуешь выбрасывать все возможные наборы дуг, и каждый раз проверяешь, связен ли полученный граф.

Приветик. я уже 2 недели бьюсь с этим вопросом. я не тупой, но графы я не понимаю. Обьясни на пальцах что это за алгоритм полного перебора, как это все иснользовать. Помоги, как можно это зделать все что ты сказал?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


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;
i, j, n_edges: integer;
found: boolean;
begin
n_edges := 10; // на самом деле мы количество ребер вводим из файла а не просто присваиваем
for i := 1 to n_edges do
a[i] := 0;

Process();
while true do begin
// увеличиваем на единичку в двоичной системе, таким образом переходя к следующему варианту
found := false;
for i := n_edges downto 1 do
if a[i] = 0 then begin
a[i] := 1;
for j := i + 1 to n_edges do
a[j] := 0;
found := true;
break;
end;

if not found then break; // дошли до последнего варианта

Process();
end;
end;


В результате процедура Process() по очереди вызовется для каждого набора. В ней ты проверяешь, связен ли граф с такими удаленными дугами, и если да, считаешь количество удаленных ребер, запоминая интересующий тебя максимум.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Цитата(Michael_Rybak @ 20.09.2007 17:00) *

Смотри. Тебе надо перебрать все возможные варианты, когда какие-то дуги есть, а каких-то нет (удалены).

Пусть у нас 5 дуг. Получается у нас 2^5 = 32 варианта: от пустого графа, когда все дуги удалены, до исходного, в котором ничего не удалили.

Эти варианты можно перебрать так. Вариант пусть задается набором из пяти чисел, каждое - 0 или 1. 0 = дуга удалена, 1 = дуга на месте. Нужно перебрать все наборы: 00000, 00001, 00010, 00011, 00100, ..., 11110, 11111. Эти наборы можно перебрать один за другим, просто переходя к каждому следующему, добавляя единичку в двоичной системе:

var a: array [1..100] of integer;
i, j, n_edges: integer;
found: boolean;
begin
n_edges := 10; // на самом деле мы количество ребер вводим из файла а не просто присваиваем
for i := 1 to n_edges do
a[i] := 0;

Process();
while true do begin
// увеличиваем на единичку в двоичной системе, таким образом переходя к следующему варианту
found := false;
for i := n_edges downto 1 do
if a[i] = 0 then begin
a[i] := 1;
for j := i + 1 to n_edges do
a[j] := 0;
found := true;
break;
end;

if not found then break; // дошли до последнего варианта

Process();
end;
end;


В результате процедура Process() по очереди вызовется для каждого набора. В ней ты проверяешь, связен ли граф с такими удаленными дугами, и если да, считаешь количество удаленных ребер, запоминая интересующий тебя максимум.


тоесть, мы процедуру Process () вызваем для каждой вершины? и прости за непонятливость, для кокого набора, набора пар вершин или набора ребер исходящих из вершины?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.09.2020 15:25
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name