Контрольные вопросы

1. Какой граф называется двудольным.

2. Перечислить перечень некоторых задач на двудольные графы.

3. Условие существования двудольного графа.

4. Что называется паросочетанием и максимальным паросочетанием?

5. Что называется реберным покрытием и минимальным реберным покрытием?

6. Связь между задачами о выделении паросочетания и реберного покрытия.

7. Пояснить понятия – открытая вершина, чередующаяся цепь и увеличивающая цепь.

8. Рассказать алгоритм выделения максимального паросочетания и минимального реберного покрытия.

Лекция 21

ТЕМА: ПЛОСКИЕ ГРАФЫ

ПЛАН:

1. Задача о плоской укладке графа

2. Основные определения

3. Алгоритм плоской укладки графа

Главная

1. Задача о плоской укладке графа

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

Если представить приборы: вершины графа, а гальванические связи между ними – ребра графа, то задача размещения приборов сводится к такому изображению графа на плоскости, при котором никакие два ребра не пересекаются.

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

2. Основные определения

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

Если граф укладывается на плоскости, то он называется планарным.

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

Плоский граф на плоскости определяет ее области. При этом неограниченная область называется внешней гранью графа, а остальные области – внутренние грани. Внешнюю грань обозначим S₀, а внутренние S₁, S₂, …, S_k . На рисунке представлен планарный граф и соответствующий ему плоский граф с гранями:

Для плоских графов справедлива формула Эйлера: n + k = m + 2, где n – число вершин графа, k – число граней, m – число ребер.

Для представленного графа: число вершин равно 5, число ребер – 8, число граней – 5. проверим формулу Эйлера:

5 + 5 = 8 – 2 – равенство верно.

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

Для формулировки этого важного результата введем два понятия.

Элементарное стягивание ребра. Элементарным стягиванием ребра {v, w} называется отождествление вершин v и w:

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

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

Сформулируем необходимое и достаточное условие планарности графа.

Для того чтобы граф G(V, X) был планарным, необходимо и достаточно, чтобы он не содержал подграфа , гомеоморфного либо полному графу К₅, либо графу К_3,3 .

Граф К₅