Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Нужен алгоритм решения задачи в графе!! 
:(
    Опции темы
lleiton
Дата 8.11.2005, 21:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 8.11.2005

Репутация: нет
Всего: нет
Задача звучит следующим образом: найти в произвольном графе минимальное доминирующее множество (естественно граф у нас связен).
так вот нужен алгоритм решения это задачи! у кого какие варианты?)
PM MAIL   Вверх
Guest
Дата 9.11.2005, 08:52 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
"минимальное доминирующее множество" - это МОД (минимальное остовное дерево) или нет?
  Вверх
Rick
Дата 9.11.2005, 09:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 122
Регистрация: 4.11.2005
Где: Новосибирск

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

графы вводятся в блокнот, например:
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

Это сообщение отредактировал(а) Rick - 9.11.2005, 10:59
--------------------
Не бывает атеистов в окопах под огнем   
PM MAIL ICQ   Вверх
nworm
Дата 9.11.2005, 15:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 502
Регистрация: 22.10.2005

Репутация: нет
Всего: 8
Можно реализовать алгоритм вычисления всех наименьших внешне устойчивых множеств вершин графа 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}.
PM MAIL WWW   Вверх
lleiton
Дата 9.11.2005, 15:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 8.11.2005

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

то есть тут всё предельно просто - нам надо найти множество вершин графа такое , чтобы все оставшиейся вершины графа были смежны(то есть являются концами одного ребра) по крайней мере с одной из вершин нашего множества, которое мы ищем.
естественно что таких множеств можно найти огромное количество, поэтому мы именно ищем МИНИМАЛЬНОЕ доминирующее множество(то есть найменьшее количество вершин нам надо найти). алгоритм его нахождения мне и надо найти.....а потом ещё прогу написат которая бы его реализовывала...но для начала хотя бы алгоритм
PM MAIL   Вверх
nworm
Дата 9.11.2005, 17:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 502
Регистрация: 22.10.2005

Репутация: нет
Всего: 8
А чем приведённый мной алгоритм не нравится. Нарисуйте на бумажке пример. Как будто всё сходится smile А потом вопрос: ориентированный ли граф? Должен ли алгоритм обладать какими-то хорошими свойствами?
PM MAIL WWW   Вверх
lleiton
Дата 9.11.2005, 18:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 8.11.2005

Репутация: нет
Всего: нет
твой алгоритм ещё не видел)) когда писал препоследний топ , его ещё не было)) сейчас бууд смотреть на сколкьо он правильный)))
спасибо nworm
Добавлено @ 19:04
nworm у меня вопросик , что вообще такое Внешне устойчивое множество?? в поределении Доминирующего множество его ещё называют внешен устойчивым . а вот что это такое мне немного непонятно.....объясни если не сложно)
PM MAIL   Вверх
nworm
Дата 9.11.2005, 21:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 502
Регистрация: 22.10.2005

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

доминирующее множество вершин = внешне устойчивое множество.
PM MAIL WWW   Вверх
lleiton
Дата 10.11.2005, 01:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 8.11.2005

Репутация: нет
Всего: нет
эт я тоже знаю))))
PM MAIL   Вверх
lleiton
Дата 10.11.2005, 23:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 8.11.2005

Репутация: нет
Всего: нет
что т я не очень понял алгоритм nworm....может объяснит кто? или предложите другой более доступный алгоритм......
PM MAIL   Вверх
nworm
Дата 11.11.2005, 20:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 502
Регистрация: 22.10.2005

Репутация: нет
Всего: 8
А что именно непонятно? В книжке откуда я его брал есть программа только на прологе. Поэтому, видимо, её бессмысленно приводить.
PM MAIL WWW   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0479 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.