Графы, не вложимые в плоскость

mmm87 · Сообщение **mmm87** » 18 июл 2010, 17:16

Привет! Подскажите пожалуйста, как доказать что граф не вложим в плоскость (т.e. не является планарным), если его ребра - стороны и наименьшие диагонали правильного n-угольника при нечетном n?

vicvolf · Сообщение **vicvolf** » 18 июл 2010, 17:33

mmm87 писал(а):Source of the post
Привет! Подскажите пожалуйста, как доказать что граф не вложим в плоскость (т.e. не является планарным), если его ребра - стороны и наименьшие диагонали правильного n-угольника при нечетном n?

Непонятна постановка! Что из себя представляет граф?. Если граф представляет из себя правильный n-угольник, то он прекрасно вместе co своими диагоналями разместится на плоскости! A что из себя представляет граф при четном n?

Ian · Сообщение **Ian** » 18 июл 2010, 17:33

mmm87 писал(а):Source of the post
Привет! Подскажите пожалуйста, как доказать что граф не вложим в плоскость (т.e. не является планарным), если его ребра - стороны и наименьшие диагонали правильного n-угольника при нечетном n?

Действительно,у 6-угольника то он вложим. Интересно,есть ли об этом какие-то теоремы и типовые методы.

vicvolf · Сообщение **vicvolf** » 18 июл 2010, 17:39

Ian писал(а):Source of the post
mmm87 писал(а):Source of the post
Привет! Подскажите пожалуйста, как доказать что граф не вложим в плоскость (т.e. не является планарным), если его ребра - стороны и наименьшие диагонали правильного n-угольника при нечетном n?
Действительно,у 6-угольника то он вложим. Интересно,есть ли об этом какие-то теоремы и типовые методы.

Про четное n пока ничего не сказано!

fir-tree · Сообщение **fir-tree** » 18 июл 2010, 17:42

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

При любом чётном n вложим, очевидно. Достаточно чётные вершины сдвинуть внутрь многоугольника.

Ian · Сообщение **Ian** » 18 июл 2010, 17:59

Действительно, работают и формула Эйлера и упомянутый Muninым критерий Куратовского
Bce есть например на этом PDFe привожу скриншот

mmm87 · Сообщение **mmm87** » 18 июл 2010, 21:15

И все-таки, как можно использовать формулу Эйлера, например в случае n=7, или как установить, что данный граф включает в себя один из 2 типов графов по критерию Куратовского?

VAL · Сообщение **VAL** » 19 июл 2010, 00:02

mmm87 писал(а):Source of the post
И все-таки, как можно использовать формулу Эйлера, например в случае n=7, или как установить, что данный граф включает в себя один из 2 типов графов по критерию Куратовского?

Для n=7 не сложно.
Пусть наш граф имеет вершины A, B, C, D, E, F, G и понятно какие ребра. Рассмотрим подграф полученный удалением ребер AG, BC, DE и EF. Он, очевидно, стягиваем к $K_{3,3}$ , достаточно заменить вершину E и ребра EG и DE одним ребром.

Для общего случая надо подумать.

Ian · Сообщение **Ian** » 19 июл 2010, 00:14

mmm87 писал(а):Source of the post
И все-таки, как можно использовать формулу Эйлера, например в случае n=7, или как установить, что данный граф включает в себя один из 2 типов графов по критерию Куратовского?

Занумеруем 7 вершин по кругу, выбросим ребра(2,3),(4,5),(5,6),(7,1). Вершина 5 стала промежуточной, объединим ребра (3,5) и (5,7) в ребро (3,7) Раскрасив как на рисунке видим что изоморфно $K_{3,3}$ -"трем колодцам"

для произвольного нечетного n>5 удалением ребер делаю промежуточными все вершины между 4й и двумя последними и получаем тот же граф $K_{3,3}$ c 6 вершинами.

Пока я тут ковырялся, VAL сделал то же самое,и именно c 5й вершиной. Ну и телепатия

jmhan · Сообщение **jmhan** » 22 июл 2010, 18:01

Ian писал(а):Source of the post
привожу скриншот

A что за книга, не подскажете? A может даже ссылочку подбросите?
Спасибо!

yourdomain.com