Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 07.12.2011, 08:58   #1
Aida.
Новичок
Джуниор
 
Регистрация: 07.12.2011
Сообщений: 1
Вопрос Программа выделения подмножества в графе (Pascal)

Уже не знаю даже как её сделать...пожалуйста, помогите кому не сложно..

Задача: Граф, задаваемый вершинами и ребрами:
А={1,…,16}, т.е. граф состоит из n=16 вершин
21 ребро V={(1,10),(2,13),(3,13), (3,14),(4,5),(4,7),(4,14),(4,15),(5 ,6),(6,7),(7,15),(7,16),(8,16),(8,9 ),(10,11), (10,12),(11,12),(12,13),(14,15),(14 ,16),(15,16)}

Свойство «опорности» подмножества W входящего в A:
для всякой вершины а принадлежащей A\W найдется вершина x принадлежащая W, такая что a и x соединены в графе ребром.

Алгоритм построения минимального опорного подмножества (n шагов):
i-ый шаг – пусть уже построено множество Wi-1 (при i=1 множество W0=A);
В графе нет ребер, соединяющих вершину а, с вершинами множества Wi-1;
В A\Wi-1 имеется такая вершина y, что в графе есть ребро (ai,y) и нет других ребер между y и вершинами из Wi-1;
Если удовлетворяет хотя бы одному из них, то полагается W=Wi-1 в прротивном случае Wi получается из Wi-1. выбрасыванием вершины ai.

После выполнения n шагов множества Wn искомое.

Заранее спасибо.
Aida. вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
программа поиска маршрутов на графе Jlena Помощь студентам 0 11.05.2011 17:33
Как найти максимальный подграф или клику в неориентированном графе?(PASCAL)) Artur1992 Помощь студентам 0 17.02.2011 16:31
Поиск подмножества Lodyr Общие вопросы C/C++ 15 27.11.2010 21:38
Нахождение максимального подмножества Lodyr Общие вопросы C/C++ 0 10.11.2010 23:09