Дискретная математика. Кулаков Ю.В - 46 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Графы на рис. 25, а, б преобразуются в графы, изоморфные графам F
5
и K
3, 3
соответственно, в результате замены цепей ({4, 5}, {5, 7}) ребрами {4, 7}. Граф на рис. 25, в преобразу-
ется в граф, изоморфный графу F
5
, в результате стягивания сначала ребра {1, 7}, а затем ребра {1(7), 2}.
Граф на рис. 25, г преобразуется в граф, изоморфный графу K
3, 3
, в результате стягивания ребра {1, 2}.
Толщина рассматриваемого графа не меньше двух:
t(G) ≥ 1 +
−
−
)27(6
232
= 2, t(G) ≥ 2.
Чтобы определить, какие ребра следует удалить для преобразования графа в
планарный граф, необходимо выделить все запрещенные фигуры и построить двумерную таблицу,
строки которой взаимно однозначно соответствуют каждой запрещенной фигуре Q
i
, столбец – ребру ρ
j
.
Тогда покрытие строк столбцами этой таблицы определит, какие ребра следует удалить для приведения
графа к планарному виду. Минимальное покрытие будет соответствовать минимальному решению.
Для рассматриваемого графа (рис. 24, а) такая таблица имеет следующий
вид.
Таблица 14
ρ
j
Q
i
{1,
2}
{2,
6}
{2,
3}
{1,
6}
{6,
7}
{1,
7}
{2,
4}
{2,
7}
{3,
5}
{3,
6}
{3,
7}
{3,
4}
{4,
6}
{4,
5}
{5,
6}
{5,
7}
Q
1
1 1 1 1 1 1 1 1 1 1 1
Q
2
1 1 1 1 1 1 1 1 1 1
Q
3
1 1 1 1 1 1 1 1 1 1 1 1
Q
4
1 1 1 1 1 1 1 1 1 1
Элемент (i, j) таблицы равен 1, если в фигуре Q
i
имеется ребро ρ
j
; в против-
ном случае – 0. Покрытие строк столбцами этой таблицы определит искомое решение. Минимальное
покрытие будет соответствовать минимальному решению.
В качестве минимального покрытия может выступать любое из ребер: {2, 4},
{3, 6}, {4, 5} или {5, 7}. После удаления, для определенности, ребра {3, 6} получаем планарный граф,
плоское представление которого изображено на рис. 24, б. Соединение, которое соответствует удален-
ному ребру, показано штриховой линией и должно быть реализовано на второй плоскости.
Задачи и упражнения
2
3
7
6
5
4
а)
1
2
3
7
6
5
4
б)
Рис. 25
1
2
3
7
6
5
4
в)
1
2
3
7
6
5
4
г)

Страницы