связность графа Опции

[zeus]

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

[hardcase]

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

[Michael_Rybak]

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

[zeus]

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

а как можно проверять связность графа, тоже нужен алгоритм?

[Michael_Rybak]

Связность графа проверяешь так: алгоритмом Флойда заполняешь матрицу достижимости, а потом проверяешь, что все пары вершин - связаны.

[zeus]

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

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

[Michael_Rybak]

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

Пусть у нас 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() по очереди вызовется для каждого набора. В ней ты проверяешь, связен ли граф с такими удаленными дугами, и если да, считаешь количество удаленных ребер, запоминая интересующий тебя максимум.

[zeus]

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

Пусть у нас 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 () вызваем для каждой вершины? и прости за непонятливость, для кокого набора, набора пар вершин или набора ребер исходящих из вершины?