11.3.5. Связь знп с другими задачами

Известно, что ЗНП относится к числу трудоемких задач, и для ее решения при­меняются переборные алгоритмы с теми или иными улучшениями. На рис. 11.1 приведена схема (см. [И]), показывающая связь ЗНП и некоторых Других задач. На этой схеме стрелка от задачи А к задаче Б означает, что решение задачи А влечет за собой решение задачи Б.

Комментарии

Обсуждение переборных задач в этой главе носит в основном ознакомитель­ный характер. Для получения более точной и детальной информации следует обратиться к специальной литературе, прежде всего к фундаментальной кни­ге [4]. Алгоритм построения максимальных независимых множеств заимствован из [11]. Здесь этот алгоритм использован прежде всего в качестве примера для иллюстрации способов и особенностей решения переборных задач.

Упражнения

Доказать, что а₀ ^ fti,a\ ^ Аз-

Написать алгоритм построения всех клик графа.

Доказать, что наименьшее доминирующее множество является независи­мым.