Урок "Планарность графов" (9 класс)

Урок «Планарность графов»

факультативного курса «Элементы теории графов и их приложения»

(9 класс)

Одной из наиболее интересных и практико-ориентированных задач является проблема проверки графов на планарность и раскладка графа на плоскости. Школьникам можно привести наглядный пример, показав сотовый  телефон и спросив, представляют ли они, насколько сложные электрические схемы в нем? Сколько электрических соединений приходится делать, чтобы связать электронные компоненты этого устройства? А ведь прокладка токоведущих дорожек – трассировка, это типичная задача о планарности графа.

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

Рассмотрим рисунок 1,а и определим, является ли изображенный на нем граф планарным.

Рисунок 1 – Граф (а) и его плоское изображение (б)

На первый взгляд граф, изображенный на рисунке 1,а не является планарным. Но, если мысленно передвинуть, например, вершину v₂ в центр графа, сохраняя при этом связи между вершинами, то можно получить его плоское изображение (рисунок 1,б). То есть, этот граф планарен.

Примерами планарных графов являются простые циклы (рисунок 2, а), деревья (рисунок 2,б), графы, содержащие цикл, из вершин которого «выходят» деревья (рисунок 2,в) и др.

Рисунок 2 – Планарные графы

Рассмотрим одну из классических задач теории графов – задачу о трех домах и трех колодцах. Имеются три дома и три колодца. Жители каждого дома могут пользоваться любым из трех колодцев (рисунок 3).

Рисунок 3 – Задача о трех домах и трех колодцах

Но однажды обитатели домов поссорились, и чтобы не встречаться друг с другом, решили проложить дорожки до колодцев так, чтобы они не пересекались. Возможно ли это?

Для начала отметим, что граф, изображенный на рисунке 3 имеет особое обозначение в теории графов: K_3,3. Это связано с тем, что он имеет как бы две доли: одна доля графа – это дома, другая – колодцы. Поэтому такие графы называют двудольными, и индекс 3,3 означает, что в каждой доле по три вершины.

Попытаемся определить, является ли граф K_3,3 планарным. Для этого попытаемся нарисовать его на плоскости так, чтобы его ребра не пересекались. На любом плоском изображении этого графа обязательно должен присутствовать цикл v₁, v₄, v₂, v₅, v₃, v₆, v₁, который делит плоскость на две части: внутреннюю (внутри цикла) и внешнюю (вне его) – см. рисунок 4.

Рисунок 4 - Задача о трех домах и трех колодцах (этап 1)

Остается дорисовать ребра (v₃, v₄), (v₁, v₅) и (v₆, v₂) так, чтобы они не пересекались. Начнем с ребра (v₃, v₄). Его можно нарисовать внутри цикла (рисунок 5, а) или вне его (рисунок 5,б).

Рисунок 5 - Задача о трех домах и трех колодцах (этап 2)

Тогда следующее ребро (v₁, v₅) можно нарисовать либо вне цикла (рисунок 5,а), либо внутри его (рисунок 5,б)

Рисунок 5 - Задача о трех домах и трех колодцах (этап 3)

Последнее же ребро (v₆, v₂) невозможно нарисовать без пересечения других ребер ни внутри цикла (рисунок 6,а), ни вне его (рисунок 6,б).

Рисунок 6 - Задача о трех домах и трех колодцах (этап 4)

Таким образом, мы доказали, что граф K_3,3 не планарен и невозможно провести дорожки так, чтобы они не пересекались.

Другим часто встречающимся непланарным графом, является полный граф K₅, с которым мы уже сталкивались (рисунок 7)

Рисунок 7 – Непланарный граф K₅

Характеристикой плоского изображения графа является понятие грани. Гранью плоского представления графа называют часть плоскости, ограниченную простым циклом и не содержащую внутри других циклов. Грань, которая имеет бесконечную площадь, называют внешней или бесконечной, остальные грани называют внутренними. Рассмотрим рисунок 8,а: этот граф имеет грани (v₁, v₇, v₄, v₁), (v₁, v₃, v₂, v₄, v₁), (v₁, v₂, v₃, v₁), (v₂, v₆, v₅, v₄, v₂), а часть плоскости (v₁, v₂, v₄, v₁) не является гранью, так как содержит внутри себя цикл (v₁, v₂, v₃, v₁).

Рисунок 8 – Грани в изображении графа

На рисунке 8,б часть плоскости (v₁, v₂, v₃, v₄, v₁) является гранью, так как ребро (v₄,v₅), которое находится внутри грани, не образует цикла. На рисунке 8,в заштрихованная часть не является гранью, так как содержит внутри себя цикл. Ребро (v₁, v₂), которое соединяет два цикла, называют мостом или перегородкой.

Простой цикл, ограничивающий грань называют границей грани. Если две границы имеют хотя бы одно общее ребро, то сами грани называют соседними. Так, на рисунке 8,а грани (v₁, v₃, v₂, v₄, v₁) и (v₁, v₂, v₃, v₁) – соседние, а грани (v₁, v₂, v₃, v₁) и (v₂, v₆, v₅, v₄, v₂) соседними не являются.

Гранью является и часть плоскости, расположенной вне плоского представления графа – это внешняя или бесконечная грань.

Рисунок 9 – Бесконечная грань (а) и область, не являющаяся гранью (б)

Заштрихованная часть на рисунке 9,а является бесконечной гранью, в то время как заштрихованная часть на рисунке 9,б гранью не является – она не ограничена изнутри простым циклом. Ребро (v₁, v₃) является перегородкой.

Как исключение считают бесконечную грань в плоском представлении дерева – гранью считается вся плоскость рисунка.

Одним из критериев планарности является формула Эйлера: для всякого плоского представления связного планарного графа без перегородок верно равенство (1):

n–m+f=2

(1)

где n – число вершин, m – число ребер, f – число граней графа с учетом бесконечной.

Покажем справедливость этого утверждения. Рассмотрим дерево T: оно имеет n вершин, число его ребер равно m=(n–1), и, как уже отмечалось, оно имеет одну бесконечную грань (например, такое дерево как на рисунке 2,б). Для дерева T формула (1) верна:

n–(n–1)+1=2. Теперь будем поочередно добавлять к дереву T ребра, образовывая циклы (например, как на рисунке 10).

Рисунок 10 – К формуле Эйлера

При каждом добавлении число вершин не меняется, а число ребер и граней увеличивается на единицу и соотношение (1) останется неизменным.

Для определения заведомо непланарных графов может быть полезно следующее соотношение. Для связного планарного графа, содержащего n вершин (n≥3) и m ребер выполняется соотношение (2):

m≤3n–6

(2)

Докажем это утверждение. Пусть f₁, f₂, …,f_k – грани графа G, а m₁, m₂, …, m_f – число ребер, ограничивающих каждую грань (не путайте с общим числом ребер графа m). Обозначим сумму этих ребер S= m₁+m₂+…+ m_f.

Так как любая грань графа G ограничена как минимум тремя ребрами, то 3f≤S. С другой стороны, каждое ребро принадлежит или одной грани, или двум граням – является общим для них. То есть в сумме S каждое такое ребро учитывается или один раз, или два. Отсюда S≤2m, где m – число всех ребер графа G. Сопоставляя два этих неравенства, получим соотношение (3):

3f≤2m

(3)

Далее представим формулу Эйлера (1) в виде (4), выразив число граней f:

f=m–n+2

(4)

и умножим обе части формулы (4) на три (5): 

3f=3m–3n+6

(5)

На основании неравенства (3) перепишем равенство (5) в виде неравенства (6):

2т≥3m–3n+6

(6)

Выразив m, получим (7):

т≤3n–6

(7)

Неравенство доказано.

Здесь, однако, не следует забывать, что если неравенство (7) не выполняется, то граф однозначно непланарен. Если же оно выполняется, то сказать определенно планарен он или нет, нельзя. В этом можно убедиться, проверив с помощью неравенства (7) на планарность графы K_3,3 (см. рисунок 3) и K₅ (см. рисунок 7). Для графа K₅ это соотношение не выполняется и можно определенно сказать, что он непланарен. Для графа же K_3,3 оно выполняется, хотя как мы показали выше, он также непланарен.

Другим критерием планарности графов служит теорема Понтрягина-Куратовского: граф является планарным тогда и только тогда, когда не содержит подграфов типа K_3,3 и K₅. Доказательство теоремы можно найти в книге Р.Басакера и Т.Саати «Конечные графы и сети».

Задачи для самостоятельного решения

1.    Проверьте справедливость формулы Эйлера для графа, изображенного на рисунке 8,а

2.    Корпорация решила построить в городе торговую сеть. В каждом квартале города, ограниченном улицами, было решено построить по универсаму. Город имеет 155 перекрестков и 260 отрезков улиц между перекрестками. Сколько же придется построить универсамов?

3.    Печатная плата представляет собой пластину из непроводящего электричества материала, на которую нанесены проводящие дорожки. В отверстия на дорожках платы устанавливают электронные приборы. При таком строении, дорожки на печатной плате не должны пересекаться. Если пересечения дорожек не избежать, то одну из таких дорожек переносят на другую сторону платы (в современных устройствах, например материнских платах компьютеров, могут использовать несколько слоев для таких пересекающихся дорожек). Конструктор разработал схему печатной платы, которая состоит из 14 электронных приборов и 32 токоведущих дорожек их соединяющих. Можно ли изготовить плату так, что все дорожки будут расположены на одной стороне?

Рекомендуемая литература

[1]     Березина Л. Ю. Графы и их применение: Пособие для учителей с ил. – М.: Просвещение, 1979. – 143 с.

[2]     Мельников О.И. Занимательные задачи по теории графов. – Минск: ТетраСистемс, 2001. – 144 с.

[3]     Мельников О.И. Теория графов в занимательных задачах. Изд.3, испр. и доп. – М.: Книжный дом «ЛИБРОКОМ», 2009. – 232 с.

[4]     Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974

Краткое описание документа:

Предлагаемый материал представляет собой конспект урока "Планарность графов" факультативного курса "Элементы теории графов и их приложения" (9 класс). Академик И.М.Яглом, в предисловии к книге О.Оре «Графы и их применение» отмечает, что несмотря на значительную важность для прикладной науки, «учение о графах очень подходит для изложения начинающим, поскольку соединяет большую геометрическую наглядность с математической содержательностью и с возможностью обходиться без громоздкого аппарата». Именно поэтому изучение теории графов можно рекомендовать в старших классах общеобразовательной школы.