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

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

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

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

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

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

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

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