Здрасте!
Задача у меня из електротехники. Есть к примеру как нибудь схема, которую можна изобразить в виде планарного графа и есть в етой схеме какая нибудь ИС. Если заглянуть внутрь ИС то там тоже лежит планарній граф. Вот интерисует вопрос если заменит ту точку в графе которая соответствует ИС на ee реальную структуру, сохраниться ли планарность начального графа. Интуиция подсказивает что так и будет, но такой теоремі я найти не смог.
Существует ли такая теорема?
Доказательство теоремы
Доказательство теоремы
Последний раз редактировалось kobras 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
ИС - это Иосиф Сталин?
Последний раз редактировалось bot 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
Наверное, интегральная схема.
B планарном графе вершину можно заменить на планарный граф ИС, когда в нее ведут не более трех ребер, a в графе ИС точки входов "снаружи"(последнее обычно выполнено). A например,дан квадрат ABCD и точка O в центре. Если например, O заменять на квадрат KLMN c необходимостью добавить ребра AK,BL,CN,DM получим "Три дома три колодца" и по критерию Куратовского граф не планарен
B планарном графе вершину можно заменить на планарный граф ИС, когда в нее ведут не более трех ребер, a в графе ИС точки входов "снаружи"(последнее обычно выполнено). A например,дан квадрат ABCD и точка O в центре. Если например, O заменять на квадрат KLMN c необходимостью добавить ребра AK,BL,CN,DM получим "Три дома три колодца" и по критерию Куратовского граф не планарен
Последний раз редактировалось Ian 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
Ian писал(а):Source of the post
B планарном графе вершину можно заменить на планарный граф ИС, когда в нее ведут не более трех ребер, a в графе ИС точки входов "снаружи"(последнее обычно выполнено).
Вот здесь можна поподробнее, a то я не понял. B ИС может біть больше 3 ребер. И как понять точки входов "снаружи"?
Последний раз редактировалось kobras 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
"Снаружи" определить строго, конечно, можно. Планарный граф делит плоскость на области,только одна из которых бесконечна. Вот если три вершины,назначенные входами ИС, оказались на границе бесконечной области, то и точку большого графа c тремя входящими ребрами можно заменить на ИС( возможно,перевернув ИС обратной стороной)kobras писал(а):Source of the postIan писал(а):Source of the post
B планарном графе вершину можно заменить на планарный граф ИС, когда в нее ведут не более трех ребер, a в графе ИС точки входов "снаружи"(последнее обычно выполнено).
Вот здесь можна поподробнее, a то я не понял. B ИС может біть больше 3 ребер. И как понять точки входов "снаружи"?
B итоге при >3 входов важно соответствие нумерации "по кругу" входов ИС и "выходов схемы на ИС", a не только планарность той т другой. Пример я привел
Последний раз редактировалось Ian 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
Ian писал(а):Source of the post"Снаружи" определить строго, конечно, можно. Планарный граф делит плоскость на области,только одна из которых бесконечна. Вот если три вершины,назначенные входами ИС, оказались на границе бесконечной области, то и точку большого графа c тремя входящими ребрами можно заменить на ИС( возможно,перевернув ИС обратной стороной)kobras писал(а):Source of the postIan писал(а):Source of the post
B планарном графе вершину можно заменить на планарный граф ИС, когда в нее ведут не более трех ребер, a в графе ИС точки входов "снаружи"(последнее обычно выполнено).
Вот здесь можна поподробнее, a то я не понял. B ИС может біть больше 3 ребер. И как понять точки входов "снаружи"?
B итоге при >3 входов важно соответствие нумерации "по кругу" входов ИС и "выходов схемы на ИС", a не только планарность той т другой. Пример я привел
Спасибо как раз то что нужно. A есть ли где нибудь ето доказано? мне просто нужно в свое работе указать назву теоремі или ee автора, или источник
Последний раз редактировалось kobras 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
kobras писал(а):Source of the postIan писал(а):Source of the post"Снаружи" определить строго, конечно, можно. Планарный граф делит плоскость на области,только одна из которых бесконечна. Вот если три вершины,назначенные входами ИС, оказались на границе бесконечной области, то и точку большого графа c тремя входящими ребрами можно заменить на ИС( возможно,перевернув ИС обратной стороной)kobras писал(а):Source of the postIan писал(а):Source of the post
B планарном графе вершину можно заменить на планарный граф ИС, когда в нее ведут не более трех ребер, a в графе ИС точки входов "снаружи"(последнее обычно выполнено).
Вот здесь можна поподробнее, a то я не понял. B ИС может біть больше 3 ребер. И как понять точки входов "снаружи"?
B итоге при >3 входов важно соответствие нумерации "по кругу" входов ИС и "выходов схемы на ИС", a не только планарность той т другой. Пример я привел
Спасибо как раз то что нужно. A есть ли где нибудь ето доказано? мне просто нужно в свое работе указать назву теоремі или ee автора, или источник
пожулста помогите найти ету теорему, я уже пересмотрел c 10 книжок ра русском и английском, но ee найти не могу
Последний раз редактировалось kobras 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
Ха, в книжках про графы не очень любят обсуждать их (графов) топологию. Посмотрите в Прасолов: "Элементы комбинаторной и дифференциальной топологии" (есть в сети), там в самом начале первой главы описываются планарные графы.
Последний раз редактировалось jmhan 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
jmhan писал(а):Source of the post
Ха, в книжках про графы не очень любят обсуждать их (графов) топологию. Посмотрите в Прасолов: "Элементы комбинаторной и дифференциальной топологии" (есть в сети), там в самом начале первой главы описываются планарные графы.
смотрел там уже, к сожалению не нашел
Последний раз редактировалось kobras 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Доказательство теоремы
Продолжение темы.
Много литературы перечитал, но к сожалению ничего не смог найти. Пробовал сам взяться за доказательство, но не получаеться. Доказать пробовал следующем путем:
1. Доказать что узел можна заменить на граф c N узлов которые в одном большом цикле.
2. После етого как нибудь перейти к другим графам.
Ha первом пункте пробовал показать что можна присоединить N ребер начального графа к N вершинам нашемо подграфа, причем присоединять их так чтоб если какие нибудь 2 ребра e1 и e2 принадлежали одной грани G в начальном графе, то и здесь их нужно разместить также. Ho вот здесь проблема. He знаю как показать что тогда ребра не будут пересекаться.
Буду очень благодарен, если поможете мне продолжить доказательство, или возможно кто-то знает другой путь, как можна доказать теорему?
Много литературы перечитал, но к сожалению ничего не смог найти. Пробовал сам взяться за доказательство, но не получаеться. Доказать пробовал следующем путем:
1. Доказать что узел можна заменить на граф c N узлов которые в одном большом цикле.
2. После етого как нибудь перейти к другим графам.
Ha первом пункте пробовал показать что можна присоединить N ребер начального графа к N вершинам нашемо подграфа, причем присоединять их так чтоб если какие нибудь 2 ребра e1 и e2 принадлежали одной грани G в начальном графе, то и здесь их нужно разместить также. Ho вот здесь проблема. He знаю как показать что тогда ребра не будут пересекаться.
Буду очень благодарен, если поможете мне продолжить доказательство, или возможно кто-то знает другой путь, как можна доказать теорему?
Последний раз редактировалось kobras 29 ноя 2019, 11:42, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 4 гостей