Видите, ребра перечислены в условии ,ведь какую из 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
Доказательство теоремы
Да уж, нужно. Если множествоkobras писал(а):Source of the postПусть задан планарный неориентированый графи планарный неориентированый граф
. Расмотрим произвольную вершину
. Позначим через
множество которое состоит из вершин графа
, что принадлежат внешней грани графа. Удалим из графа
вершину
, обединим граф
c графом
, a каждое ребро
- инцидентное нашей вершине
заменем по следующем правилам:
1. еслито заменим его на
2. еслии
принадлежали одной грани то и
c
тоже принадлежат одной грани.
Полученный граф будет планарен.
Такая формулировка правильная или что-то нужно поправить?
Потому что ответ на Ваш вопрос из последнего поста
Любая грань (замкнутое множество, ограниченное непересекающимися и несамопересекающимися ребрами) связное множество на плоскости, значит линейно связное, значит любые 2 вершины можно связать ребром, целиком лежащим внутри множества
Последний раз редактировалось Ian 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 1 гость