Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > Нужен алгоритм решения задачи в графе!!

Автор: lleiton 8.11.2005, 21:34

Задача звучит следующим образом: найти в произвольном графе минимальное доминирующее множество (естественно граф у нас связен).
так вот нужен алгоритм решения это задачи! у кого какие варианты?)

Автор: Guest 9.11.2005, 08:52

"минимальное доминирующее множество" - это МОД (минимальное остовное дерево) или нет?

Автор: Rick 9.11.2005, 09:36

я не понял, чего тебе надо, ну если это МОД, то есть такой вариант:

графы вводятся в блокнот, например:
2 6
1 3 2
1 4 2
1 2 3
2 8 5
и т.д.

2 6 - "2" это начальный граф, "6" - конечный
1 3 2 - граф "1" соединен с "3", длина ребра "2"

Код



const dlina=9;

var
  Form1: TForm1;
  graf: array [1..dlina,1..dlina] of integer;
  vrem, max, min, nah, kon:Integer;
  implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var
m,n,rez:Integer;
begin
assignfile(input,'input.txt');
reset(input);
read(input,nah);read(input,kon);
while not(EOF(input)) do
begin
read(input,m);read(input,n);read(input,rez);
graf[m,n]:=rez;
end;
closefile(input);
vrem:=0;
max:=0;
min:=100;
travel(nah);
edit1.Text:=inttostr(min); {мин оставное дерево}
edit2.Text:=inttostr(max);{макс остовное дерево}
end;

procedure tform1.travel(v:Integer); {алгоритм нахождения МОД}
var
w:Integer;
begin
 for w:=1 to kon do begin
  if (v=kon) and (vrem>max) then max:=vrem;
  if (v=kon) and (vrem<min) then min:=vrem;
  if graf[v,w]<>0 then begin
  vrem:=vrem+graf[v,w];
  travel(w);
  vrem:=vrem-graf[v,w];
  end;
 end;
end;

end.

Добавлено @ 11:00

спутал, это алгоритм нахождения кратчайшего пути от одного графа к другому smile

Автор: nworm 9.11.2005, 15:50

Можно реализовать алгоритм вычисления всех наименьших внешне устойчивых множеств вершин графа G = (V,E) (внешне устойчивое множество = доминирующее множество вершин).
1. Построить формулу
F = & (xu V ( V xv))
u in V (u,v) in E
условие внешней устойчивости графа G.
2. Построить минимальную ДНФ D формулы F.
3. Для каждого дизъюнктивного слагаемого К = xuxv...xw в D получить соответствующее ему минимальное внешне устойчивое множество вершин S = {u,v,...,w}.
4. Из полученных минимальных внешне устойчивых множеств вершин выбрать все наименьшие.
Пример. Вычислим все наименьшие внешне устойчивые множества вершин графа G - (V,E) = ({1,2,3, 4, 5, б, 7}, {(1,2), (1,3), (1,5), (1,6), (2,3), (3,4), (3,6), (4, 5), (4, 7), (5, 6), (6,7)}). Условие внешней устойчивости для графа G
F = & (u V ( V v)) = (1V2V3V5V6)(2V1V3)(3V1V2V4V6)&(4V3V5V7)(5V1V4V6)(6V1V3V5V7)(7V4V6) = 156 V 17 V 246 V 247 V 257 V 245 V 256 V 267 V 357 V 36 V 34 V 14.
Все минимальные внешне устойчивые множества: {l , 5 , 6} , {l , 7} , {2,4,6}, {2,4,7}, {2,5,7}, {2,4,5}, {2,5,6}, {2,6,7}, {3,5,7} {3, 6} , {3,4}, {1,4}. Из полученных множеств выбираем наименьшие по мощности. Они и составят все наименьшие внешне устойчивые множества вершин: {1,7}; {3,6}; {3,4}; {1,4}.

Автор: lleiton 9.11.2005, 15:58

не ребята....это немного не то....мне нужно именно Минимальное Доминирующее Множество найти в графе
сейчас дам определение: подмножества вершин графа Y называется доминирующим мнодеством, если любая вершина из множества X\Y смежна по крайней мере с одной вершиной из Y.

то есть тут всё предельно просто - нам надо найти множество вершин графа такое , чтобы все оставшиейся вершины графа были смежны(то есть являются концами одного ребра) по крайней мере с одной из вершин нашего множества, которое мы ищем.
естественно что таких множеств можно найти огромное количество, поэтому мы именно ищем МИНИМАЛЬНОЕ доминирующее множество(то есть найменьшее количество вершин нам надо найти). алгоритм его нахождения мне и надо найти.....а потом ещё прогу написат которая бы его реализовывала...но для начала хотя бы алгоритм

Автор: nworm 9.11.2005, 17:32

А чем приведённый мной алгоритм не нравится. Нарисуйте на бумажке пример. Как будто всё сходится smile

А потом вопрос: ориентированный ли граф? Должен ли алгоритм обладать какими-то хорошими свойствами?

Автор: lleiton 9.11.2005, 18:58

твой алгоритм ещё не видел)) когда писал препоследний топ , его ещё не было)) сейчас бууд смотреть на сколкьо он правильный)))
спасибо nworm
Добавлено @ 19:04
nworm у меня вопросик , что вообще такое Внешне устойчивое множество?? в поределении Доминирующего множество его ещё называют внешен устойчивым . а вот что это такое мне немного непонятно.....объясни если не сложно)

Автор: nworm 9.11.2005, 21:50

Тайный смысл понятия «внешне устойчивое множество» мне не знаком. Единственно, что я знаю:

доминирующее множество вершин = внешне устойчивое множество.

Автор: lleiton 10.11.2005, 01:38

эт я тоже знаю))))

Автор: lleiton 10.11.2005, 23:41

что т я не очень понял алгоритм nworm....может объяснит кто? или предложите другой более доступный алгоритм......

Автор: nworm 11.11.2005, 20:09

А что именно непонятно? В книжке откуда я его брал есть программа только на прологе. Поэтому, видимо, её бессмысленно приводить.