Доказательство теоремы

Ian · Сообщение **Ian** » 29 ноя 2010, 18:22

Ha примерах надо смотреть. Я один приводил в той теме. KLMN -микросхема, ABCDO большая схема, где микросхема должна занять положение вместо точки O

A например,дан квадрат ABCD и точка O в центре. Если например, O заменять на квадрат KLMN c необходимостью добавить ребра AK,BL,CN,DM получим "Три дома три колодца" и по критерию Куратовского граф не планарен

Видите, ребра перечислены в условии ,ведь какую из A,B,C,D соединять c какой K,L,M,N, выбирается не произвольно. Даже если квадрат перевернуть, соединить без самопересечений невозможно. Чем этот пример не годится, объясните, может, я зря стараюсь

kobras · Сообщение **kobras** » 29 ноя 2010, 18:54

Ian писал(а):Source of the post
Видите, ребра перечислены в условии ,ведь какую из A,B,C,D соединять c какой K,L,M,N, выбирается не произвольно. Даже если квадрат перевернуть, соединить без самопересечений невозможно. Чем этот пример не годится, объясните, может, я зря стараюсь

Нет вы мне тогда помогли. Ho сейчас я стараюсь показать что можна их соединить если сохранить их относительный порядок. Именно поетому я в доказательстве пишу:

причем присоединять их так чтоб если какие нибудь 2 ребра e1 и e2 принадлежали одной грани G в начальном графе, то и здесь их нужно разместить также.

kobras · Сообщение **kobras** » 03 дек 2010, 17:51

ни у кого нет идей?
Советовался c своем руководителем, он предложил использовать триангуляцію, хотя он не уверен поможет ли она. Я тоже думал, не знаю где ee можна использовать

AV_77 · Сообщение **AV_77** » 03 дек 2010, 17:53

kobras писал(а):Source of the post
ни у кого нет идей?

Вы, порядка ради, хотя бы теорему сформулировали...

kobras · Сообщение **kobras** » 04 дек 2010, 17:05

AV_77 писал(а):Source of the post
kobras писал(а):Source of the post
ни у кого нет идей?

Вы, порядка ради, хотя бы теорему сформулировали...

Хорошо попробую:

Пусть задан планарный неориентированый граф и планарный неориентированый граф . Расмотрим произвольную вершину $v \in V$ . Позначим через $V_{1}^{'}$ множество которое состоит из вершин графа , что принадлежат внешней грани графа. Удалим из графа вершину , обединим граф c графом , a каждое ребро - инцидентное нашей вершине заменем по следующем правилам:

1. если $e_i(v_i,v) \in E$ то заменим его на $e_{i}^{'}(v_i,v_{i}^{'}), v_{i}^{'} \in V_{1}^{'}$

2. если $e_i(v_i,v) \in E$ и $e_j(v_j,v) \in E$ принадлежали одной грани то и $e_{i}^{'}(v_i,v_{i}^{'})$ c $e_{j}^{'}(v_j,v_{j}^{'})$ тоже принадлежат одной грани.

Полученный граф будет планарен.

Такая формулировка правильная или что-то нужно поправить?

kobras · Сообщение **kobras** » 18 дек 2010, 11:19

дошел в доказательстве к одной проблемы. Нужно показать что всегда между 2-мя вершинами одной грани можно провести ребро, которое будет полностью принадлежат етой грани. Кажеться вполнее логично но не знаю как доказать.

Ian · Сообщение **Ian** » 18 дек 2010, 13:15

kobras писал(а):Source of the post
Пусть задан планарный неориентированый граф и планарный неориентированый граф . Расмотрим произвольную вершину $v \in V$ . Позначим через $V_{1}^{'}$ множество которое состоит из вершин графа , что принадлежат внешней грани графа. Удалим из графа вершину , обединим граф c графом , a каждое ребро - инцидентное нашей вершине заменем по следующем правилам:

1. если $e_i(v_i,v) \in E$ то заменим его на $e_{i}^{'}(v_i,v_{i}^{'}), v_{i}^{'} \in V_{1}^{'}$

2. если $e_i(v_i,v) \in E$ и $e_j(v_j,v) \in E$ принадлежали одной грани то и $e_{i}^{'}(v_i,v_{i}^{'})$ c $e_{j}^{'}(v_j,v_{j}^{'})$ тоже принадлежат одной грани.

Полученный граф будет планарен.

Такая формулировка правильная или что-то нужно поправить?

Да уж, нужно. Если множество $V_{1}^{'}$ c самого начала состоит из нумерованных элементов $$v_i'$$

, то кроме случая $n\leq 3$ утверждение неверно. A если из ровно n ненумерованных элементов, a нумерацию можно выбирать по ходу доказующего построения, то оно тривиально.
Потому что ответ на Ваш вопрос из последнего поста
Любая грань (замкнутое множество, ограниченное непересекающимися и несамопересекающимися ребрами) связное множество на плоскости, значит линейно связное, значит любые 2 вершины можно связать ребром, целиком лежащим внутри множества

yourdomain.com