Видите, ребра перечислены в условии ,ведь какую из A,B,C,D соединять c какой K,L,M,N, выбирается не произвольно. Даже если квадрат перевернуть, соединить без самопересечений невозможно. Чем этот пример не годится, объясните, может, я зря стараюсьA например,дан квадрат ABCD и точка O в центре. Если например, O заменять на квадрат KLMN c необходимостью добавить ребра AK,BL,CN,DM получим "Три дома три колодца" и по критерию Куратовского граф не планарен
Доказательство теоремы
Доказательство теоремы
Ha примерах надо смотреть. Я один приводил в той теме. KLMN -микросхема, ABCDO большая схема, где микросхема должна занять положение вместо точки O
Последний раз редактировалось Ian 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
Ian писал(а):Source of the post
Видите, ребра перечислены в условии ,ведь какую из A,B,C,D соединять c какой K,L,M,N, выбирается не произвольно. Даже если квадрат перевернуть, соединить без самопересечений невозможно. Чем этот пример не годится, объясните, может, я зря стараюсь
Нет вы мне тогда помогли. Ho сейчас я стараюсь показать что можна их соединить если сохранить их относительный порядок. Именно поетому я в доказательстве пишу:
причем присоединять их так чтоб если какие нибудь 2 ребра e1 и e2 принадлежали одной грани G в начальном графе, то и здесь их нужно разместить также.
Последний раз редактировалось kobras 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
ни у кого нет идей?
Советовался c своем руководителем, он предложил использовать триангуляцію, хотя он не уверен поможет ли она. Я тоже думал, не знаю где ee можна использовать
Советовался c своем руководителем, он предложил использовать триангуляцію, хотя он не уверен поможет ли она. Я тоже думал, не знаю где ee можна использовать
Последний раз редактировалось kobras 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
Вы, порядка ради, хотя бы теорему сформулировали...
Последний раз редактировалось AV_77 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
Хорошо попробую:
Пусть задан планарный неориентированый граф и планарный неориентированый граф . Расмотрим произвольную вершину . Позначим через множество которое состоит из вершин графа , что принадлежат внешней грани графа. Удалим из графа вершину , обединим граф c графом , a каждое ребро - инцидентное нашей вершине заменем по следующем правилам:
1. если то заменим его на
2. если и принадлежали одной грани то и c тоже принадлежат одной грани.
Полученный граф будет планарен.
Такая формулировка правильная или что-то нужно поправить?
Последний раз редактировалось kobras 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
дошел в доказательстве к одной проблемы. Нужно показать что всегда между 2-мя вершинами одной грани можно провести ребро, которое будет полностью принадлежат етой грани. Кажеться вполнее логично но не знаю как доказать.
Последний раз редактировалось kobras 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
Да уж, нужно. Если множество c самого начала состоит из нумерованных элементов , то кроме случая утверждение неверно. A если из ровно n ненумерованных элементов, a нумерацию можно выбирать по ходу доказующего построения, то оно тривиально.kobras писал(а):Source of the postПусть задан планарный неориентированый граф и планарный неориентированый граф . Расмотрим произвольную вершину . Позначим через множество которое состоит из вершин графа , что принадлежат внешней грани графа. Удалим из графа вершину , обединим граф c графом , a каждое ребро - инцидентное нашей вершине заменем по следующем правилам:
1. если то заменим его на
2. если и принадлежали одной грани то и c тоже принадлежат одной грани.
Полученный граф будет планарен.
Такая формулировка правильная или что-то нужно поправить?
Потому что ответ на Ваш вопрос из последнего поста
Любая грань (замкнутое множество, ограниченное непересекающимися и несамопересекающимися ребрами) связное множество на плоскости, значит линейно связное, значит любые 2 вершины можно связать ребром, целиком лежащим внутри множества
Последний раз редактировалось Ian 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 1 гость