Федоров В.Н. - Введение в теорию графов, страница 10

f = m – n + 2,

где n – число вершин, m – число ребер.

11.3. Алгоритм построения плоского изображения графа

Ответ на второй вопрос: – Как получить плоское изображение графа? – дает алгоритм, рассмотренный ниже.

Пусть задана часть G₁ = (V₁, E₁) графа G = (V, E).

Будем называть куском графа G относительно G₁:

1. ребро вместе с его концами, которые принадлежат V₁,

2. а также компоненту связности G’_i = (V’_i, E’_i) подграфа, порожденного подмножеством вершин V\V_l, дополненную всеми ребрами, инцидентными вершинам из V'_i, и всеми вершинами этих ребер, принадлежащими V₁ , которые называются «контактными точками»;

Алгоритм использует последовательный процесс присоединения к некоторому плоскому подграфу цепи , оба конца которой (и только они) – вершины . Эта цепь разобьет одну из граней на две.

В качестве начального плоского графа выбирают некоторый цикл графа G.

Чтобы перейти от подграфа к , предварительно рассматривают все куски P_j графа G относительно .

Грань f_k графа и кусок Р_j совместимы, если все его контактные точки принадлежат множеству вершин этой грани.

Для каждого куска определяем грани, которые с ним совместимы. Возможны три случая:

1. Некоторый кусок не совместим ни с какой гранью графа . Тогда граф не плоский.

2. Какой–либо кусок совместим с единственной гранью f_k графа . Тогда выберем в этом куске цепь такую, что оба ее конца (и только они) принадлежат . Дополняя ребрами и вершинами этой цепи, получаем , проводя внутри грани f_k.

3. Если каждый из кусков Р_j совместим, по крайней мере, с двумя гранями графа , то можно выбрать цепь в любом из кусков и действовать как в случае 2.

П
ример. Проиллюстрируем этот алгоритм на примере графа G(V,E) рис. 11.2.

Рисунок 11.2

Шаг 1. Берем произвольный цикл, например u₀ = (1, 2, 6, 5, 1), представляющий плоский граф (рис. 11.3, а).

Грани :

A₀ — внешняя грань (1, 2, 6, 5, 1),

В₀ — внутренняя грань (1,2,6,5,1).

Куски графа G относительно :

Куски	Вершины куска	Контактные точки	Совместимые грани
P1	{1, 3, 5, 6}	{1, 5, 6}	A0 и B0
Р2	{1, 2, 4, 6}	{1, 2, 6}	A0 и B0

Шаг 2. Определяем . Все куски совместимы с двумя гранями (случай 3). Выбираем, например, цепь (1, 3, 5) из куска Р₁ и проводим ее в грани В₀. Эта грань в заменяется двумя гранями: В₁ – внутренней к (1, 3, 5, 1) и В₂ – внутренней к (1, 2, 6, 5, 3, 1) (рис. 11.3, б).

Куски G относительно :

Куски	Вершины кусков	Контактные точки	Совместимые грани
	{3, 6}	{3, 6}	В2
	{1, 2, 4, 6}	{1, 2, 6}	A0 и В2

Шаг 3. Определяем . Кусок Р₁ совместим лишь с одной гранью В₂ (случай 2). Цепь (3, 6) должна быть помещена в грань В₂, которую она разобьет на две грани: В₃ — внутреннюю к (3, 5, 6, 3) и В₄ – внутреннюю к (1, 2, 6, 3, 1) (рис. 11.3, в).

Р
исунок 13.3

Куски G относительно :

Кусок	Вершины куска	Контактные точки	Совместимые грани
	{1, 2, 4, 6}	{1, 2, 6}	A0 и В4

Шаг 4. Определяем . Кусок совместим с двумя гранями A₀ и B₄ (случай 3). Возьмем, например, цепь (1, 4, 2) и поместим ее в грань A₀. Получаем две новые грани: A₁ – внешнюю к (1, 4, 2, 6, 5, 1) и А₂ – внутреннюю к (1, 4, 2, 1) (рис. 11.3, г).

Куски G относительно :

Кусок	Вершины куска	Контактные точки	Совместимые грани
	{4, 6}	{4, 6}	A1

Шаг 5. Определяем . Кусок совместим с одной гранью A₁ (случай 2). Помещаем единственную цепь (4, 6) в A₁ и получаем новые грани: A₃ – внешнюю к (1, 4, 6, 5, 1) и A₄ – внутреннюю к (2, 4, 6, 2) (рис. 11.3, д).

Таким образом, получаем плоское изображение графа G.

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

1. Что такое планарный граф?

2. Каковы условия планарности для произвольного графа?

3. Грань плоского графа – Что это такое ? Сколько граней у плоского графа?

4. Граф K₆ плоский? А K₇?

5. Что такое число планарности и толщина графа? Как их определить?

6. Какова идея алгоритма построения плоского изображения графа?

12. Двудольные графы

Двудольным графом называют такой граф G(X Y,E), что

1. X Y = ,

Пример двудольного графа и его матрица смежности показаны на рис. 12.1.

Рисунок 12.1

С
войства двудольного графа:

1. Множество вершин графа состоит из двух непересекающихся подмножеств таких, что внутри каждого подмножества нет смежных вершин.

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

3. Двудольный граф не имеет простых циклов нечетной длины.

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

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

12.1. Минимальное покрытие двудольного графа

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

Н
апример, для графа рис. 12.2 покрытием будет множество дуг

W = {(x₁,y₁), (x₂,y₄), (x₃, y₂), (x₄, y₃), (x₅, y₄), (x₅, y₅), (x₆,y₃)}.

Рисунок 12.2

В матрице смежности, показанной на рис. 12.2, дуги множества W выделены полужирным шрифтом.

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

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

12.1.1. Алгоритм с использованием матрицы инцидентности

Для простоты будем рассматривать неориентированный двудольный граф, вершины которого обозначены натуральными числами 1, 2, 3,..., а ребра строчными буквами латинского алфавита.

Алгоритм:

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

2. Для определения минимального покрытия вершин графа ребрами необходимо найти такую минимальную совокупность столбцов матрицы инцидентности (ребер), которая содержала хотя бы по одной 1 во всех строках, т.е. могла бы покрыть каждую вершину графа.

Для этого для каждой вершины (для каждой строки) записываем логическую сумму имен ребер, инцидентных вершине (имеющих 1 в строке вершины). Каждая сумма символизирует тот факт, что для покрытия вершины, чьим именем обозначена строка, нужно или ребро a, инцидентное вершине, или ребро b, инцидентное вершине, и т.д.

1. Для покрытия графа надо покрыть и вершину 1, и вершину 2, и т.д. Поэтому из сумм предыдущего пункта, заменив союз И символом логического умножения, составляем логическое произведение.

2. полученное логическое произведение сумм преобразуется в дизъюнктивную форму и минимизируется. Терм с минимальным числом букв и будет представлять минимальное покрытие графа.

Пример. Дан граф рис. 12.3.

Найти минимальное подмножество ребер, инцидентных всем вершинам.

Составляем матрицу инцидентности графа (табл. 12.1).

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

Составляем логическое произведение полученных сумм, раскрываем скобки и минимизируем

(a b)(c d)(a c)(b d) =

= (ac ad bc bd)(ab ad bc cd) =

= abc acd abc acd abd ad abcd acd

abc abcd bc bcd abd abd bcd bcd =

= ad bc.

Подмножество ребер ad или bс покрывает все вершины графа.

Таблица 12.1
	a	b	c	d
1	1	1	0	0
2	0	0	1	1
3	1	0	1	0
4	0	1	0	1

Рисунок 12.3