. Вершинами графа D_n являются диагонали правильного n-угольника, стороны диагоналями не считаются. Две вершины графа (диагонали многоугольника) соединены ребром тогда и только тогда, когда эти диагонали пересекаются во внутренней точке, пересечения по вершинам не считаются. Найдите максимальный размер независимого множества в графе D_n.

задан 24 Сен 4:43

На русский язык это как понимаю переводится как найти максимальное по мощности подмножество непересекающихся внутри многоугольника диагоналей? n-3 как-нибудь вроде по индукции.

(24 Сен 11:55) mihailm

Да, тут всё просто. Проведём независимые диагонали. Они разбивают выпуклый n-угольник на отдельные многоугольники, у каждого из которых вершины содержатся среди исходных. Если там есть не треугольники, то в них проводим дополнительные диагонали. Получается, что максимальное по включению независимое множество -- это триангуляция. В ней n-2 треугольника, то есть n-3 диагонали. Отсюда следует, что максимальный по количеству размер равен n-3.

(24 Сен 13:10) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×643
×14

задан
24 Сен 4:43

показан
74 раза

обновлен
24 Сен 13:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru