![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Новичок
Джуниор
Регистрация: 07.12.2011
Сообщений: 1
|
![]()
Уже не знаю даже как её сделать...пожалуйста, помогите кому не сложно..
Задача: Граф, задаваемый вершинами и ребрами: А={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 искомое. Заранее спасибо. |
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
программа поиска маршрутов на графе | 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 |