Планарные графы

Графы стали изучаться ещё математиками 18 веке, но как предмет математической теории только в 20 веке. В настоящее время теория графов находит всё более и более широкое применение применяются в естественных науках (физика, химия, биология, социология, лингвистика). Во многих случаях не имеет значения, как изобразить граф, поскольку изоморфные графы несут одну и ту же информацию. Однако встречаются ситуации, когда важно выяснить, возможно ли нарисовать граф на плоскости так, чтобы его изображение удовлетворяло определенным требованиям. Например, в радиоэлектронике при изготовлении микросхем печатным способом электрические цепи наносятся на плоскую поверхность изоляционного материала.

---

Не знаете сколько стоит диссертация на заказ ? Проверьте на Work5.

---

. А так как проводники не изолированы, то они нe должны пересекаться. Аналогичная задача возникает при проектировании железнодорожных и других путей, где нежелательны переезды.

Целью этого параграфа является получение еще одного критерия планарности графа, основанного на понятии двойственности. Условимся, что всюду в этом пункте слово «граф» означает «псевдограф». Кроме того, видоизменим здесь использованную выше операцию стягивания ребра е = uv ?EG, под которой теперь будем понимать удаление ребра е и отождествление вершин и и v в новую вершину, инцидентную тем ребрам графа G, которые были инцидентны вершинам и и v, за исключением ребра е Тем самым теперь появляющиеся при стягивании ребра кратные ребра не отождествляются, как ранее. Для плоского графа G построим новый плоский граф G*, который назовем геометрически двойственным к G. Для этого внутри каждой грани Ti графа G выберем по одной точке V*i. Эти точки — вершины будущего графа G*. Далее, каждому ребру е ? EG поставим в соответствие жорданову кривую е*, которая пересекает лишь одно реб­ро е графа G и соединяет вершины v *i, лежащие в гранях, границы которых содержат ребро е (таких граней может быть две или одна). Кривые е* — ребра графа G*. Ребра графа G* можно провести так, чтобы они не пересекались. На рис. 40.2 сплошной линией изображен граф G, а пунктирной — граф G*. Заметим, что петлю в G* порождает всякий мост в G, а кратные ребра появляются в G* тогда и только тогда, когда две грани графа G имеют более одного общего ребра.

. Емеличев Р.И., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. 2. Ф. Харари. Теория графов. М.: «Мир». 1973 3. Зыков А.А. Основы теории графов 4. Березина Л.Ю. Графы и их применение 5. Берж К. теория графов и их применение 6. Мелихов А.Н. применение графов для проектирования дискретных устройств. / А.Н. Мелихов, Л.С. Бернштейн, В.М. Курейчик 7. Кузнецов О.П. Дискретная математика для инженеров.