|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Slobodskoy 2:5015/128.22 24 Oct 2002 21:35:35
To : Andrew Plyako
Subject : Re: Hайти покpытие столбцов стpоками
--------------------------------------------------------------------------------
Здравствуйте, //Andrew Plyako//, САHТЕХHИКА вызывали?!? Так так, у вас потекло
23.10.02... *ТЫ хочешь поговорить об этом??*
ET>> Может есть какой-то мат. аппаpат для pешения данной задачи.
AP> Если я правильно понимаю твой вопрос, то это -- поиск минимальной клики в
AP> графе.
Это не верно. Клика - такое множество вершин, при котором граф, индуцированный
этим множеством - полный. Соответственно, это есть задача на max, ибо одна
любая вершина является кликой. А что же это на самом деле за задача на языке
графов, мне до сих пор не понятно, потому что условие сформулировано плохо.
AP> NP-полная задача.
таковой является, если быть точным, поиск HАИБОЛЬШЕЙ клики.
-----------------
Hадеюсь, хоть чем-то мог быть полезен! И, это... в следующий раз закрывайте
кран!
Slobodskoy Vitaly
e-mail: vital@mail.nnov.ru
fido: 2:5015/128.22
--- WP/95 Rel 1.78E (215.0) Reg.
* Origin: И создал бог мужику женщину..Существо получилось ГЛУПОЕ, но забавное
: (2:5015/128.22)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
