Re: Найти покpытие столбцов стpоками

From

Vitaly Slobodskoy (2:5015/128.22)

To

Andrew Plyako

Date

2002-10-24T21:35:35Z

Area

RU.ALGORITHMS

Здравствуйте, //Andrew Plyako//, САНТЕХНИКА вызывали?!? Так так, у вас потекло 23.10.02... *ТЫ хочешь поговорить об этом??*

 ET>> Может есть какой-то мат. аппаpат для pешения данной задачи.
 AP> Если я правильно понимаю твой вопрос, то это -- поиск минимальной клики в
 AP> графе. 
 Это не верно. Клика - такое множество вершин, при котором граф, индуцированный
этим множеством - полный. Соответственно, это есть задача на max, ибо одна
любая вершина является кликой. А что же это на самом деле за задача на языке
графов, мне до сих пор не понятно, потому что условие сформулировано плохо.

 AP> NP-полная задача. 
 таковой является, если быть точным, поиск НАИБОЛЬШЕЙ клики.

-----------------
Надеюсь, хоть чем-то мог быть полезен! И, это... в следующий раз закрывайте
кран!

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)