Графики и СетиПланарные Графики

Вот еще одна загадка, связанная с теорией графов.

В маленькой деревне есть три дома и три коммунальных предприятия, которые производят воду, электричество и газ. Мы должны подключить каждый из курсов к каждому из коммунальных предприятий, но из-за расположения деревни различные трубы и кабели не могут пересекаться.

Попробуйте подключить каждый из домов к каждой из нижеуказанных коммунальных компаний, не пересекая линии

Как и ранее Кенигсбергские мосты, вы быстро обнаружите, что эта проблема также невозможна. Кажется, что некоторые графики могут быть нарисованы без перекрывающихся ребер - они называются плоскими графами - но другие не могут.

K3 плоская

Полный график K5 самый маленький график, который не является плоским. Любой другой график, который содержит K5 как подграф в некотором роде тоже не плоский. Это включает K6 , K7 и все большие полные графики.

Граф в головоломке трех утилит является двудольным графом K3,3 , Оказывается, что любой непланарный граф должен содержать K5 или K3,3 (или подразделение этих двух графиков) как подграф. Это называется теорема Куратовского .

Planarity

Это планарный график, но ${n} вершины были зашифрованы. Переставьте вершины так, чтобы ни одно из ребер не перекрывалось.

Формула Эйлера

Все плоские графики делят плоскость, на которой они нарисованы, на несколько областей, называемых гранями .

вершин лиц ребер 11 Вершин + Лица

вершин лиц ребер 15 Вершин + Лица

вершин лиц края 25 Вершин + Лица

Сравнивая эти числа, вы заметите, что количество ребер всегда на сколько количество граней плюс количество вершин. Другими словами, F + V = E + 1. Этот результат называется уравнением Эйлера и назван в честь того же математика, который решил задачу Кенигсбергских мостов.

К сожалению, существует бесконечно много графиков, и мы не можем проверить каждый из них, чтобы увидеть, работает ли уравнение Эйлера. Вместо этого мы можем попытаться найти простое доказательство, которое работает для любого графа ...

0 + 1 = 0 + 1

The simplest graph consists of a single vertex. We can easily check that Euler’s equation works.

Let us add a new vertex to our graph. We also have to add an edge, and Euler’s equation still works.

If we want to add a third vertex to the graph we have two possibilities. We could create a small triangle: this adds one vertex, one face and two edges, so Euler’s equation still works.

Instead we could simply extend the line by one: this adds one vertex and one edge, and Euler’s equation works.

Let’s keep going: if we now create a quadrilateral we add one vertex, two edges and one face. Euler’s equation still works.

Любой (конечный) граф можно построить, начиная с одной вершины и добавляя больше вершин одну за другой. Мы показали, что, каким бы способом мы ни добавляли новые вершины, уравнение Эйлера справедливо. Поэтому это верно для всех графиков.

Процесс, который мы использовали, называется математической индукцией . Это очень полезный метод для доказательства результатов в бесконечном количестве случаев, просто начиная с самого простого случая и показывая, что результат сохраняется на каждом этапе при построении более сложных случаев.

Многие плоские графики очень похожи на сети многогранников , трехмерных фигур с многоугольными гранями. Если мы считаем, что многогранники сделаны из эластичных полос, мы можем представить, как растягиваем их, пока они не станут плоскими, плоскими графиками:

Это означает, что мы можем использовать формулу Эйлера не только для плоских графов, но и для всех многогранников - с одним небольшим отличием. При преобразовании многогранников в графы одна из граней исчезает: верхняя грань многогранников становится «наружной»; графиков.

Другими словами, если вы посчитаете количество края , лица и вершины любого многогранника, вы найдете, что F + V = E + .

Икосаэдр 20 лиц 12 вершин 30 ребер

ромбоикосододекаэдр 62 лица 60 вершин 120 ребер

Усеченный икосаэдр 32 лица (12 черных, 20 белых) 60 вершин 90 ребер

Изменить язык

Войдите в Mathigon

Поделиться

Сбросить прогресс

Глоссарий

Графики и СетиПланарные Графики

Planarity

Формула Эйлера