задан 13 Июн '17 16:07

Попробовала рисовать, но не уверена, что это так. Помогите, пожалуйста, с выборов ответов.

(13 Июн '17 16:09) olga5

необходимое условие — если граф непланарный, то он должен содержать больше 4 вершин, степень которых больше 3, или больше 5 вершин степени больше 2.

(13 Июн '17 17:39) Williams Wol...

Не поняла. Что из этого следует?

(13 Июн '17 17:42) olga5

Да, любой. В силу теоремы Куратовского, граф непланарен т. и т.т., когда он содержит подграфы, гомеоморфные либо K5, либо K3.3. Но K5 содержит 10 ребер, а K3.3 - девять.

(13 Июн '17 18:33) knop
10|600 символов нужно символов осталось
1

Критерий Понтрягина-Куратовского гласит, что граф планарен тогда и только тогда, когда в нем можно выделить подграф, гомеоморфный $%K_5$% или $%K_{3,3},$% но тогда нужно не менее 9 ребер.

ссылка

отвечен 13 Июн '17 18:33

изменен 13 Июн '17 18:34

10|600 символов нужно символов осталось
1

Теорме Понтрягина - Куратовского проста в применении, и она могла иметься в виду -- особенно с учётом того, что задание имеет форму теста. Но доказательство у неё сложное, поэтому представляет интерес более "ручное" рассуждение.

Если в графе есть вершины степени 2, то их можно удалить, не нарушая свойства планарности. То же для вершин степени 1: их всегда можно добавить к планарной картинке вместе с соединяющим ребром.

В итоге вопрос сводится к графу, где все вершины имеют степень >=3 (это общий факт). Тогда, если вершин n, то рёбер не меньше 3n/2, то есть 3n<=16, и n<=5. Остаётся заметить, что граф с 4 вершинами планарен, а для 5 вершин планарным будет граф даже с 9 рёбрами (полный граф без одного ребра) -- такая картинка легко рисуется.

Правда, оценку 8 не заменить на 9 ввиду непланарности графа K_{3,3}. При такой замене мы получили бы неравенство 3n<=18, и тогда возникает случай n=6, для которого есть контрпример.

ссылка

отвечен 14 Июн '17 2:11

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×548

задан
13 Июн '17 16:07

показан
639 раз

обновлен
14 Июн '17 2:11

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

по почте:

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

по RSS:

Ответы

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

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