Графы, не вложимые в плоскость
Графы, не вложимые в плоскость
Привет! Подскажите пожалуйста, как доказать что граф не вложим в плоскость (т.e. не является планарным), если его ребра - стороны и наименьшие диагонали правильного n-угольника при нечетном n?
Последний раз редактировалось mmm87 29 ноя 2019, 17:12, всего редактировалось 1 раз.
Причина: test
Причина: test
Графы, не вложимые в плоскость
mmm87 писал(а):Source of the post
Привет! Подскажите пожалуйста, как доказать что граф не вложим в плоскость (т.e. не является планарным), если его ребра - стороны и наименьшие диагонали правильного n-угольника при нечетном n?
Непонятна постановка! Что из себя представляет граф?. Если граф представляет из себя правильный n-угольник, то он прекрасно вместе co своими диагоналями разместится на плоскости! A что из себя представляет граф при четном n?
Последний раз редактировалось vicvolf 29 ноя 2019, 17:12, всего редактировалось 1 раз.
Причина: test
Причина: test
Графы, не вложимые в плоскость
Действительно,у 6-угольника то он вложим. Интересно,есть ли об этом какие-то теоремы и типовые методы.mmm87 писал(а):Source of the post
Привет! Подскажите пожалуйста, как доказать что граф не вложим в плоскость (т.e. не является планарным), если его ребра - стороны и наименьшие диагонали правильного n-угольника при нечетном n?
Последний раз редактировалось Ian 29 ноя 2019, 17:12, всего редактировалось 1 раз.
Причина: test
Причина: test
Графы, не вложимые в плоскость
Ian писал(а):Source of the postДействительно,у 6-угольника то он вложим. Интересно,есть ли об этом какие-то теоремы и типовые методы.mmm87 писал(а):Source of the post
Привет! Подскажите пожалуйста, как доказать что граф не вложим в плоскость (т.e. не является планарным), если его ребра - стороны и наименьшие диагонали правильного n-угольника при нечетном n?
Про четное n пока ничего не сказано!
Последний раз редактировалось vicvolf 29 ноя 2019, 17:12, всего редактировалось 1 раз.
Причина: test
Причина: test
Графы, не вложимые в плоскость
Непланаризуемые графы хорошо известны, они включают в себя подграф одного из двух типов: полный 5-вершинный и "три дома - три колодца" (не помню, как он правильно называется). Доказательства непланаризуемости основаны на нахождении этих подграфов.
При любом чётном n вложим, очевидно. Достаточно чётные вершины сдвинуть внутрь многоугольника.
При любом чётном n вложим, очевидно. Достаточно чётные вершины сдвинуть внутрь многоугольника.
Последний раз редактировалось fir-tree 29 ноя 2019, 17:12, всего редактировалось 1 раз.
Причина: test
Причина: test
Графы, не вложимые в плоскость
Действительно, работают и формула Эйлера и упомянутый Muninым критерий Куратовского
Bce есть например на этом PDFe привожу скриншот
Bce есть например на этом PDFe привожу скриншот
Последний раз редактировалось Ian 29 ноя 2019, 17:12, всего редактировалось 1 раз.
Причина: test
Причина: test
Графы, не вложимые в плоскость
И все-таки, как можно использовать формулу Эйлера, например в случае n=7, или как установить, что данный граф включает в себя один из 2 типов графов по критерию Куратовского?
Последний раз редактировалось mmm87 29 ноя 2019, 17:12, всего редактировалось 1 раз.
Причина: test
Причина: test
Графы, не вложимые в плоскость
Для n=7 не сложно.mmm87 писал(а):Source of the post
И все-таки, как можно использовать формулу Эйлера, например в случае n=7, или как установить, что данный граф включает в себя один из 2 типов графов по критерию Куратовского?
Пусть наш граф имеет вершины A, B, C, D, E, F, G и понятно какие ребра. Рассмотрим подграф полученный удалением ребер AG, BC, DE и EF. Он, очевидно, стягиваем к , достаточно заменить вершину E и ребра EG и DE одним ребром.
Для общего случая надо подумать.
Последний раз редактировалось VAL 29 ноя 2019, 17:12, всего редактировалось 1 раз.
Причина: test
Причина: test
Графы, не вложимые в плоскость
Занумеруем 7 вершин по кругу, выбросим ребра(2,3),(4,5),(5,6),(7,1). Вершина 5 стала промежуточной, объединим ребра (3,5) и (5,7) в ребро (3,7) Раскрасив как на рисунке видим что изоморфно -"трем колодцам"mmm87 писал(а):Source of the post
И все-таки, как можно использовать формулу Эйлера, например в случае n=7, или как установить, что данный граф включает в себя один из 2 типов графов по критерию Куратовского?
для произвольного нечетного n>5 удалением ребер делаю промежуточными все вершины между 4й и двумя последними и получаем тот же граф c 6 вершинами.
Пока я тут ковырялся, VAL сделал то же самое,и именно c 5й вершиной. Ну и телепатия
Последний раз редактировалось Ian 29 ноя 2019, 17:12, всего редактировалось 1 раз.
Причина: test
Причина: test
Графы, не вложимые в плоскость
A что за книга, не подскажете? A может даже ссылочку подбросите?
Спасибо!
Последний раз редактировалось jmhan 29 ноя 2019, 17:12, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 25 гостей