Заметка о теореме Холла
Автор: Копылов Георгий Николаевич, Лебедев Василий Николаевич
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Математика
Статья в выпуске: 10, 2006 года.
Бесплатный доступ
В работе представлено следствие из теоремы Холла о системе представителей класса множеств, где вместо уникальных представителей рассматриваются множественные. Справедлив критерий о наличии группы представителей, который доказан сведением к теореме Холла. Далее проводится алгоритмический анализ поиска группы представителей. Непосредственно из критерия следует принадлежность задачи классу сложности NP ∩ со - NP. И далее представлены полиномиальные детерминированные алгоритмы решения данной задачи.
Короткий адрес: https://sciup.org/14968586
IDR: 14968586
Список литературы Заметка о теореме Холла
- Холл М. Комбинаторика. М.: Мир, 1970.
- Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985.
