Версия для печати темы

Автор: zeus 7.09.2007 3:40

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

Автор: hardcase 7.09.2007 23:12

Думаю вам нужен http://algolist.ru/maths/graphs/span.php.

Автор: Michael_Rybak 8.09.2007 7:58

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

Автор: zeus 11.09.2007 0:33

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

Автор: Michael_Rybak 11.09.2007 20:04

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

Автор: zeus 20.09.2007 13:47

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

Автор: Michael_Rybak 20.09.2007 21: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;

Автор: zeus 20.09.2007 23:39

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

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;