Разбиение графа на плоские суграфы

Пусть задан произвольный граф G=(X,U), имеющий гамильтонов цикл. Пусть ребра, инцидентные одной вершине, не пересекаются между собой, два любых ребра гамильтонова цикла не образуют пересечений. Каждому ребру графа U_i,j є U поставим в соответствие двоичный символ a_ij,

1, если ребро U_ij лежит во внутренней области

a_ij=

0, если ребро U_ij лежит во внешней области

Будем обозначать инверсию a_ij как .

Граф G будет плоским, если его разбиение на G₀ и так, что (общее число пересечения ребер), то есть

Для определения планарности графа надо решить данное уравнение.

Так как a_s,t ≥ 0, т.е. неотрицательно, то .

Левая часть уравнения является двоичной логической функцией эквивалентности, которая равна нулю, когда переменные a_k,j и равны друг другу. Такая запись означает, что ребра U_k,j и U_m,_i не образуют пересечений, если их провести в разных областях.

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

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

Если в данном выражении найдется хотя бы один такой элемент a_s,_t для которого в этом выражении существует a_s,t , что (G) ≠ 0. Число пар вида является верхней оценкой числа планарности графа.

ПРИМЕР №1: Задан граф G=(X,U)

Найдем оценку числа планарности графа (G), а так же те ребра, которые следует удалить, чтобы граф G стал плоским. По методу, описанному выше, составим уравнение и определим P₀(G) и (G): n=6; k=4,5,6; i=3,4,5; m=1,2,3

P₀(G) = a_2,5(a_1,3 + а_1,4) + а_3,6(а_1,4 + а_1,5 + а_2.5) + а_3,5·а_1,4 + а_4,6(а_1,5 + а_2,5 + а_3,5);

;

Приравнивая элементы, заключенные в скобки, получаем истину:

Сведем полученную систему к выражению вида:

Так как в полученной подсистеме две пары вида

то '(G)=2.

Проводим с наружи

Удаляем

Удаляем

Результат:

Удаляем Удаляем

= = = a_3,6 = = = = a_4,6 =

Проводим внутри Проводим снаружи

ПРИМЕР №2

n = 7

k = 2, 3, 4, 5

j = 4, 5, 6, 7

i = 3, 4, 5, 6

m = 1, 2, 3, 4

Q = l => граф непланарен.

В результате получим: ребро (2,6) - удаляем => граф станет планарным.

УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ:

Основная литература.

1.1 Корячко В.П., Курейчик В.М.. Норенкоз И.П. «Теоретические основы САПР» М,. «Энергоиздат»., 1987

1.2 Норенокв И.П., Маничев В.Б. «Основы теории и проектирования САПР» М., «Высшая школа», 1990

1.3 Сучков А.И. «Проектирование печатных плат с САПР PCAD» (учебно-методическое пособие). Обнинск, «Микрос», 1992

1.4 Саврушев Э.Ц. «P-CAD для Windows. Система проектирования печатных плат» М., «Эком», 2002

Дополнительная литература.

2.1 Разевиг В.Д. «Система PCAD 2000 (справочник команд)» М., «Телеком», 2001

2.2 Климов В.Е. «Разработка САПР» (в 10 книгах) М., «Высшая школа», 1990