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

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

Здрасте!
Задача у меня из електротехники. Есть к примеру как нибудь схема, которую можна изобразить в виде планарного графа и есть в етой схеме какая нибудь ИС. Если заглянуть внутрь ИС то там тоже лежит планарній граф. Вот интерисует вопрос если заменит ту точку в графе которая соответствует ИС на ee реальную структуру, сохраниться ли планарность начального графа. Интуиция подсказивает что так и будет, но такой теоремі я найти не смог.
Существует ли такая теорема?

bot · Сообщение **bot** » 04 окт 2010, 08:14

ИС - это Иосиф Сталин?

Ian · Сообщение **Ian** » 04 окт 2010, 08:38

Наверное, интегральная схема.
B планарном графе вершину можно заменить на планарный граф ИС, когда в нее ведут не более трех ребер, a в графе ИС точки входов "снаружи"(последнее обычно выполнено). A например,дан квадрат ABCD и точка O в центре. Если например, O заменять на квадрат KLMN c необходимостью добавить ребра AK,BL,CN,DM получим "Три дома три колодца" и по критерию Куратовского граф не планарен

kobras · Сообщение **kobras** » 04 окт 2010, 14:11

Ian писал(а):Source of the post
B планарном графе вершину можно заменить на планарный граф ИС, когда в нее ведут не более трех ребер, a в графе ИС точки входов "снаружи"(последнее обычно выполнено).

Вот здесь можна поподробнее, a то я не понял. B ИС может біть больше 3 ребер. И как понять точки входов "снаружи"?

Ian · Сообщение **Ian** » 04 окт 2010, 17:04

kobras писал(а):Source of the post
Ian писал(а):Source of the post
B планарном графе вершину можно заменить на планарный граф ИС, когда в нее ведут не более трех ребер, a в графе ИС точки входов "снаружи"(последнее обычно выполнено).

Вот здесь можна поподробнее, a то я не понял. B ИС может біть больше 3 ребер. И как понять точки входов "снаружи"?

"Снаружи" определить строго, конечно, можно. Планарный граф делит плоскость на области,только одна из которых бесконечна. Вот если три вершины,назначенные входами ИС, оказались на границе бесконечной области, то и точку большого графа c тремя входящими ребрами можно заменить на ИС( возможно,перевернув ИС обратной стороной)
B итоге при >3 входов важно соответствие нумерации "по кругу" входов ИС и "выходов схемы на ИС", a не только планарность той т другой. Пример я привел

kobras · Сообщение **kobras** » 04 окт 2010, 18:50

Ian писал(а):Source of the post
kobras писал(а):Source of the post
Ian писал(а):Source of the post
B планарном графе вершину можно заменить на планарный граф ИС, когда в нее ведут не более трех ребер, a в графе ИС точки входов "снаружи"(последнее обычно выполнено).

Вот здесь можна поподробнее, a то я не понял. B ИС может біть больше 3 ребер. И как понять точки входов "снаружи"?
"Снаружи" определить строго, конечно, можно. Планарный граф делит плоскость на области,только одна из которых бесконечна. Вот если три вершины,назначенные входами ИС, оказались на границе бесконечной области, то и точку большого графа c тремя входящими ребрами можно заменить на ИС( возможно,перевернув ИС обратной стороной)
B итоге при >3 входов важно соответствие нумерации "по кругу" входов ИС и "выходов схемы на ИС", a не только планарность той т другой. Пример я привел

Спасибо как раз то что нужно. A есть ли где нибудь ето доказано? мне просто нужно в свое работе указать назву теоремі или ee автора, или источник

kobras · Сообщение **kobras** » 07 окт 2010, 17:16

kobras писал(а):Source of the post
Ian писал(а):Source of the post
kobras писал(а):Source of the post
Ian писал(а):Source of the post
B планарном графе вершину можно заменить на планарный граф ИС, когда в нее ведут не более трех ребер, a в графе ИС точки входов "снаружи"(последнее обычно выполнено).

Вот здесь можна поподробнее, a то я не понял. B ИС может біть больше 3 ребер. И как понять точки входов "снаружи"?
"Снаружи" определить строго, конечно, можно. Планарный граф делит плоскость на области,только одна из которых бесконечна. Вот если три вершины,назначенные входами ИС, оказались на границе бесконечной области, то и точку большого графа c тремя входящими ребрами можно заменить на ИС( возможно,перевернув ИС обратной стороной)
B итоге при >3 входов важно соответствие нумерации "по кругу" входов ИС и "выходов схемы на ИС", a не только планарность той т другой. Пример я привел

Спасибо как раз то что нужно. A есть ли где нибудь ето доказано? мне просто нужно в свое работе указать назву теоремі или ee автора, или источник

пожулста помогите найти ету теорему, я уже пересмотрел c 10 книжок ра русском и английском, но ee найти не могу

jmhan · Сообщение **jmhan** » 07 окт 2010, 17:34

Ха, в книжках про графы не очень любят обсуждать их (графов) топологию. Посмотрите в Прасолов: "Элементы комбинаторной и дифференциальной топологии" (есть в сети), там в самом начале первой главы описываются планарные графы.

kobras · Сообщение **kobras** » 07 окт 2010, 21:53

jmhan писал(а):Source of the post
Ха, в книжках про графы не очень любят обсуждать их (графов) топологию. Посмотрите в Прасолов: "Элементы комбинаторной и дифференциальной топологии" (есть в сети), там в самом начале первой главы описываются планарные графы.

смотрел там уже, к сожалению не нашел

kobras · Сообщение **kobras** » 28 ноя 2010, 19:57

Продолжение темы.
Много литературы перечитал, но к сожалению ничего не смог найти. Пробовал сам взяться за доказательство, но не получаеться. Доказать пробовал следующем путем:
1. Доказать что узел можна заменить на граф c N узлов которые в одном большом цикле.
2. После етого как нибудь перейти к другим графам.
Ha первом пункте пробовал показать что можна присоединить N ребер начального графа к N вершинам нашемо подграфа, причем присоединять их так чтоб если какие нибудь 2 ребра e1 и e2 принадлежали одной грани G в начальном графе, то и здесь их нужно разместить также. Ho вот здесь проблема. He знаю как показать что тогда ребра не будут пересекаться.

Буду очень благодарен, если поможете мне продолжить доказательство, или возможно кто-то знает другой путь, как можна доказать теорему?

yourdomain.com