IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Доминируюшие множества, Помогите найти!
сообщение
Сообщение #1


Гость






Сколько в нете не искал-так и не смог найти метод нахождения минимального доминирующего множества и связанных с ним задач. Кто знает-пожалуйста, расскажите или киньте ссылочку!
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


Если писал функции в маткаде (или хотя бы умеешь их читать) - вот здесь посмотри: http://www.exponenta.ru/soft/mathcad/stud12/index.asp
Алгоритм поиска основан на вычислении степеней вершин графа и выборе вершины с наибольшей степенью в качестве доминирующей.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Это по-моему не правильный алгоритм
Вот контрпример:
(1)-----(3)--
--(2)--(4)---
-----(5)-----
--(6)---(7)--
(8)-------(9)
Вершина 1 связана с 2, 2 с 5, 3-с 4,4 с 5, 8 с 6, 6 с 5, 9 с 7, 7 с 5
Минимальное доминирующее множество-{2,4,6,7} и вершина 5 с найбольшей степенью в него не входит

МатКад читать не умею, честно говоря
Я имел ввиду не програмную реализацию, а алгоритм
З.Ы.Не знаешь, где взять Маскад и учебник по нему? Заранее спасибо
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


вот еще что нашла:
http://rain.ifmo.ru/cat/view.php/theory/gr...t/covering-2004


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Спасибо, тут я тоже уже был
Тогдя я поставлю вопрос по-другому
Может, кто-нибуть знает, где в нете найти серьезную книгу по теории графов типа Оре или Харари или грека(не помню фамилии) Все что я находил-или пустые ссылки на Рапид или в формате *.ps, а он у меня ничем не читается...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Грек - это Кристофидес? Качай здесь (DJVU, ссылка рабочая, только что проверил): http://sci-lib.com/one_book.php?book_num=100444
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Да, тот самый грек, спасибо! И все вроде-бы есть....
Может, ты тогда(по ходу дела) знаешь сайт с классическими алгоритмами, где их действительно МНОГО( а не так, как в алголисте)?Если знаешь-кинь ссылочку, пожл
Спасибо заранее и за Кристофидеса!
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 2:12
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name