Дискретная математика. Громов Ю.Ю - 64 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

64
лицу, каждой строке которой соответствует запрещённая фигура Q
i
, а ка-
ждому столбцу – ребро ρ
j
графа G. Эту таблицу следует заполнить так,
чтобы элемент (i, j) был равен 1, если в запрещённой фигуре Q
i
имеется
ребро ρ
j
, и был равен 0 − в противном случае. Тогда каждое покрытие
строк столбцами таблицы определит множество рёбер графа G, удаление
которых преобразует его в планарный граф. При этом покрытие мини-
мальной мощности определит минимальное решение задачи.
Для рассматриваемого графа G (рис. 28, а) в качестве запрещённых
фигур Q
1
, Q
2
, Q
3
и Q
4
выступают графы, представленные на рис. 29, а, б, в
и г соответственно, а таблица выглядит следующим образом.
Таблица 14
Q
i
ρ
j
{1,2}
{1,6}
{1,7}
{2,3}
{2,4}
{2,6}
{2,7}
{3,4}
{3,5}
{3,6}
{3,7}
{4,5}
{4,6}
{5,6}
{5,7}
{6,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
2
3
7
6
5
4
а)
1
2
3
7
6
5
4
б)
Рис. 29
1
2
3
7
6
5
4
в)
1
2
3
7
6
5
4
г)

Страницы