Архив форума

Не подскажите на чём хотя бы основано решение задачи Толстые хоббиты?

Понятно, что у нас есть ЧУМ, и нам нужно найти его ширину. Теорема Дилуорса гласит, что ширина ЧУМа равна минимальному количеству цепей, на которые этот ЧУМ можно разбить. Соответственно, ищем транзитивное замыкание графа, разбиваем его на цепи (см. решение в Кормене). Далее выбираем по одной вершине в каждой цепи так,чтобы они не были сравинмы друг с другом. Авторское решение вроде бы похожее.

Что за аббревиатура ЧУМ?
Нигде не встречал такую!

ЧУМ = Частично-упорядоченное множество (partially ordered set). Ознакомиться с ними и с теоремой Дилворта (Dilworth's theorem) можно здесь http://en.wikipedia.org/wiki/Dilworth's_theorem и здесь http://en.wikipedia.org/wiki/Partially_ordered_set . На русском языке здесь http://belsky.narod.ru/v2/download/mathemat/courses/tgik/ ( лекция 8 )