Задача выделения максимально плоского
подграфа
непланарного
графа занимает важное место при
визуальном построении рисунка графа. В работе [1] показано, что задача
выделения максимально плоского подграфа
непланарного
графа является
NP-полной. То есть ее можно решить путем полного перебора
вариантов и не существует полиномиального алгоритма для ее разрешимости.
Будем рассматривать приближенное решение задачи в общем виде, не вдаваясь
в подробное описание методов и алгоритмов, а только выделяя основные этапы. Для
решения данной задачи применим методы
диакоптики
[2],
то есть разобьем решение на части, связанные между собой.
Будем рассматривать граф
G
= (
V
,
E
) с пронумерованным множеством ребер
E
= {
e
1
,
e
2
,...,
e
m
} и пронумерованным множеством вершин
V
= {
v
1
,
v
2
,...,
v
n
}, причем
card
(
V
)
=
n
и
card
(
E
)
=
m
.
Выделим
несепарабельную
часть графа.
Определение 1.
Несепарабельным
графом
G
будем называть связный
неориентированный граф без петель и кратных ребер, без мостов и точек
сочленения, без вершин с локальной степенью меньшей или равной двум.
Таким образом,
диакоптика
позволяет применить математическую модель, основанную на цикломатических
свойствах графа, и тем самым подключить для решения задачи теорему
Маклейна
. Тогда процесс решения можно представить в виде,
состоящем из двух последовательных этапов:
·
построение максимально плоского суграфа для
несепарабельного
суграфа;
·
добавление к полученному решению единичных ребер до
сепарабельного максимально плоского подграфа (пусть даже с нулевым количеством
дополнительных ребер).
В такой
модели основную роль играют простые
циклы графа. Следовательно
,
задача о построении максимально плоского суграфа может быть
сведена к задаче комбинаторной оптимизации.
Задача комбинаторной оптимизации:
Найти на множестве простых циклов
подмножество независимых циклов, описывающее плоский суграф и удовлетворяющее
нулевому значению функционала
Маклейна
и уравнению
Эйлера с максимальным числом ребер.
Такая постановка позволяет свести
перечислительную задачу к классу задач комбинаторной оптимизации и позволяет
применить для её решения хорошо разработанный математический аппарат дискретной
оптимизации. Параллельно с этим цикломатический подход позволяет строго и
однозначно описывать топологический рисунок плоской части графа, так как
полученная в результате решения независимая система циклов индуцирует
(порождает) вращение вершин графа. Согласно теории вращений, вращение вершин
создает топологический рисунок графа [3].
Определение 2.
Изометрическим циклом
в графе называется простой цикл, для
которого кратчайший путь между любыми двумя его вершинами состоит из рёбер
этого цикла.
Изометрический цикл – частный случай
изометрического подграфа [4].
Или, другими словами, изометрическим
циклом
в графе называется подграф
в виде простого цикла, если между двумя любыми
несмежными вершинами данного подграфа в графе
G
не существует маршрутов меньшей
длины, чем маршруты, принадлежащие данному циклу.
Будем искать решение на множестве изометрических циклов графа. Множество
изометрических циклов графа представляет собой
матроид
[5].
Определение 3.
Матроид
М – это конечное множество
S
и набор
F
таких подмножеств множества
S
, что выполняются следующие условия,
называемые условиями независимости:
|
Æ
Î
F
|
(1)
|
|
Если
Z
Î
F
и
Y
Í
Z
, то
Y
Î
F
|
(2)
|
|
Если
Z
и
Y
– члены
F
и
½
Z
½
=
½
Y
½
+1, то существует такое
z
Î
Z
–
Y
,
что
Y
È
z
Î
F
|
(3)
|
В
выражении (3) вычитание
Z
–
Y
понимается как
Z
/(
Z
Ç
Y
). Элементы множества
S
называются элементами
матроида
М. Члены набора
F
называются
множествами
матроида
М. Максимальное по включению
независимое множество
матроида
М называется
базой
матроида
М. Множество баз
матроида
М обозначается
B
(
M
) или просто
B
.
Подмножество
S
, не принадлежащее набору
F
называется зависимым. Минимальное по включению зависимое подмножество
S
называется циклом
матроида
М. Набор циклов
матроида
М обозначается
(
M
) или просто
.
Множество изометрических циклов графа будем обозначать как
. Множество баз
матроида
изометрических циклов будем обозначать
. Базис линейного подпространства
циклов, состоящего из изометрических циклов мощностью равной цикломатическому
числу графа
, будем
обозначать
как
и называть
конфигурацией
. В
свою очередь,
, где
– множество конфигураций. Естественно предположить, что
конфигурации
.
Множество конфигураций можно представлять как структурное число
W
, где каждый столбец (элемент) характеризует конфигурацию. С
другой стороны, структурное число можно представлять как произведение
однострочных структурных чисел, характеризующих изометрические циклы,
проходящие по выбранной хорде. Причем согласно правилам алгебры структурных
чисел [6] выбор дерева графа не влияет на конечный результат.
В свою очередь, подмножеству циклов можно поставить в соответствие два
вектора. Вектор циклов по ребрам
P
e
, определяющий количество изометрических циклов, проходящих
по ребрам данного подмножества, и вектор циклов по вершинам
P
v
, определяющий количество изометрических циклов, проходящих
по вершинам данного подмножества.
Плоская часть
непланарного
графа должна
удовлетворять нулевому значению функционала
Маклейна
[7]
:
|
|
(4)
|
где
a
i
– коэффициенты вектора
P
e
.
Требования
к
конфигурациям:
1.
Конфигурация должна быть линейно независимой.
2. Значение функционала Маклейна для конфигурации должно
стремиться к минимальному значению.
3. В векторе циклов по ребрам для конфигурации не должно быть нулевых элементов.
4. В векторе циклов по ребрам для конфигурации обязательно должны содержаться
единичные элементы.
5.
В векторе циклов по вершинам для конфигурации не должно быть нулевых элементов.
Естественно, что значение функционала
Маклейна
для конфигурации
непланарного
графа больше нуля. Следовательно, для достижения нулевого значения функционала
Маклейна
нужно удалить часть циклов. Для описания процесса
удаления циклов методом наискорейшего спуска можно воспользоваться операцией
дифференцирования структурного числа
W
изометрических циклов [8,9].
Описание
процесса построения плоской части
непланарного
несепарабельного
графа лучше всего проводить на конкретных
примерах, так как в процессе описания приходится вводить новые нестандартные
термины и определения. Такое введение нестандартных определений, в итоге,
вызывает некоторое затруднение для прочтения и понимания. Сказанное рассмотрим
на примере следующего неориентированного графа.
Рис. 1. Граф
G.
Количество изометрических циклов графа равно 20, по длинам они
распределены следующим образом: длины 4 – 13 циклов, длины 6 – 7 циклов.
Циклы соответствующего
матроида
(
)
состоят
из шести наборов по три изометрических цикла в каждом, а также из двух наборов
по 4 цикла, и т.д.
В качестве примера рассмотрим один из
циклов
матроида
, представленный на рис. 2:
Рис.2. Топологический
рисунок 18-го цикла
матроида.
c
18
c
17
c
14
c
1
c
7
c
9
c
15
= {
e
14
,
e
15
,
e
20
,
e
22
}
{
e
12
,
e
15
,
e
18
,
e
19
}
{
e
1
,
e
2
,
e
9
,
e
10
,
e
12
,
e
14
}
{e
1
,e
2
,e
4
,e
5
}
{
e
4
,
e
7
,
e
9
,
e
11
}
{
e
5
,
e
7
,
e
18
,
e
19
,
e
21
,
e
22
}
{e
10
,e
11
,e
20
,e
21
}
=
Если удалить из множества изометрических циклов следующие циклы:
{с
6
, с
9
, с
14
, с
12
, с
16
, с
13
},
то получим элемент базы
матроида
изометрических
циклов состоящий из 14-ти циклов.
Множество
независимых циклов, принадлежащих выбранному элементу базы
матроида
,
будем называть
усеченным
множеством изометрических циклов
. В свою
очередь, усеченные множества изометрических циклов образуют базу
матроида
.
Сформируем
однострочные структурные числа для усеченного множества изометрических циклов.
Для выделенного дерева графа
T
= {
e
1
,
e
4
,
e
5
,
e
8
,
e
10
,
e
12
,
e
13
,
e
17
,
e
19
,
e
20
,
e
21
,
e
22
}
множество хорд
H
= {
e
2
,
e
3
,
e
6
,
e
7
,
e
9
,
e
11
,
e
14
,
e
15
,
e
16
,
e
18
}.
И тогда для множества изометрических циклов однострочные структурные числа
имеют вид:
по хорде
e
2
проходят циклы:
[
c
1
,
c
4
,
c
5
,
c
14
];
по хорде
e
3
проходят циклы:
[
c
2
,
c
3
,
c
4
,
c
5
];
по хорде
e
6
проходят циклы:
[
c
6
,
c
8
,
c
10
,
c
20
];
по хорде
e
7
проходят циклы:
[
c
7
,
c
9
,
c
10
,
c
11
,
c
12
,
c
20
];
по хорде
e
9
проходят циклы:
[
c
2
,
c
3
,
c
6
,
c
7
,
c
14
];
по хорде
e
11
проходят циклы:
[
c
7
,
c
10
,
c
15
];
по хорде
e
14
проходят циклы:
[
c
3
,
c
12
,
c
13
,
c
14
,
c
18
];
по хорде
e
15
проходят циклы:
[
c
11
,
c
17
,
c
18
,
c
19
,
c
20
];
по хорде
e
16
проходят циклы:
[
c
2
,
c
3
,
c
4
,
c
16
,
c
19
];
по хорде
e
18
проходят циклы:
[
c
5
,
c
9
,
c
16
,
c
17
].
Построим однострочные структурные числа
для усеченного множества изометрических циклов. Длина элемента структурного
числа всегда равна количеству хорд графа, в данном случае – десяти.
Алгоритмом
«бегущая строка» выделим все множество элементов усеченного структурного числа
W
и
определим их количество. Количество элементов структурного числа для нашего
примера равно 594.
Усеченные
однострочные структурные числа:
циклы, проходящие по хорде e
14
:
[c
3
,c
18
];
циклы, проходящие по хорде e
18
:
[c
5
,c
17
];
циклы, проходящие по хорде e
2
:
[c
1
,c
4
,c
5
];
циклы, проходящие по хорде e
6
:
[c
8
,c
10
,c
20
];
циклы, проходящие по хорде e
9
:
[c
2
,c
3
,c
7
];
циклы, проходящие по хорде e
11
:
[c
7
,c
10
,c
15
];
циклы, проходящие по хорде e
3
:
[c
2
,c
3
,c
4
,c
5
];
циклы, проходящие по хорде e
7
:
[c
7
,c
10
,c
11
,c
20
];
циклы, проходящие по хорде e
16
:
[c
2
,c
3
,c
4
,c
19
];
циклы,
проходящие по хорде e
15
: [c
11
,c
17
,c
18
,c
19
,c
20
];
Элементы
усеченного структурного числа (конфигурации) имеют вид (рассмотрим на примере 172-го
и 173-го элементов):
……………………………………………………………………………
172-й – {c
3
,c
5
,c
1
,c
20
,c
7
,c
10
,c
2
,c
11
,c
4
,c
18
};
173-й – {c
3
,c
5
,c
1
,c
20
,c
7
,c
10
,c
2
,c
11
,c
4
,c
19
};
……………………………………………………………….……………
Приближенно количество элементов
структурного числа можно рассчитать по формуле
:
|
|
(5)
|
здесь
k
u
– мощность усеченного множества
изометрических циклов.
Очевидно, что при создании
практических систем приближенного решения для выделения плоской части
непланарного
графа следует воспользоваться методом
Монте-Карло. То есть произвести методом наискорейшего спуска случайным образом
выборку большого числа конфигураций и выбрать соответствующее решение, используя
при этом в качестве целевой функции функционал
Маклейна
и описывая процесс как взятие обратной производной структурного числа.
При выборе плоской части
конфигурации следует соблюдать следующие условия:
1.
При исключении цикла из конфигурации
(или применении операции дифференцирования структурного числа) в качестве
целевой функции следует применять функционал Понтрягина-
Куратовского
.
2.
При исключении циклов из конфигурации
должно выполняться правило: при исключении одного цикла должно удаляться одно и
только одно ребро.
3.
В результате исключения циклов должна
образоваться подсистема циклов, имеющая нулевое значение функционала
Понтрягина-
Куратовского.
Такую подсистему будем
называть
плоской конфигурацией.
В свою очередь, плоская конфигурация
должна удовлетворять ряду требований:
1.
Для плоской конфигурации должен
выполняться закон Эйлера.
2.
Линейная комбинация циклов плоской
конфигурации обязательно должна образовывать обод, который характеризует не
пустой связный простой цикл.
3.
Выделенный суграф должен быть связным
и не содержать точек сочленения.
4.
Циклы плоской конфигурации должны
индуцировать вращение вершин, которое описывает топологический рисунок плоской
части графа.
Генерируя
случайным образом конфигурации методом наискорейшего спуска, получаем следующие
плоские конфигурации:
Таблица 3.1. Плоская конфигурация 1.
|
|
Множество
циклов графа в виде ребер:
|
Множество
циклов графа в виде
вершин:
|
Кортеж вершин
изометрических циклов:
|
|
с
16
|
{e
12
,e
16
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
4
}
|
<
v
9
,v
5
,v
11
,v
4
>
|
|
c
1
|
{e
1
,e
2
,e
4
,e
5
}
|
{v
7
,v
2
,v
9
,v
1
}
|
<
v
1
,v
9
,v
2
,v
7
>
|
|
с
6
|
{e
4
,e
6
,e
8
,e
9
}
|
{v
7
,v
3
,v
8
,v
2
}
|
<
v
2
,v
8
,v
3
,v
7
>
|
|
с
8
|
{e
5
,e
6
,e
12
,e
13
}
|
{v
9
,v
4
,v
8
,v
2
}
|
<
v
9
,v
4
,v
8
,v
2
>
|
|
с
18
|
{e
14
,e
15
,e
20
,e
22
}
|
{v
13
,v
6
,v
12
,v
4
}
|
<
v
4
,v
12
,v
6
,v
13
>
|
|
с
15
|
{e
10
,e
11
,e
20
,e
21
}
|
{v
13
,v
6
,v
10
,v
3
}
|
<
v
13
,v
6
,v
10
,v
3
>
|
|
с
5
|
{e
2
,e
3
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
1
}
|
<
v
1
,v
11
,v
5
,v
9
>
|
|
с
13
|
{e
8
,e
10
,e
13
,e
14
}
|
{v
8
,v
4
,v
13
,v
3
}
|
<
v
8
,v
4
,v
13
,v
3
>
|
|
обод
|
{e
16
,e
1
,e
9
,e
15
,e
22
,e
11
,e
21
,e
3
}
|
{v
11
,v
1
,v
7
,v
3
,v
10
,v
6
,v
12
,v
4
}
|
<
v
11
,v
1
,v
7
,v
3
,v
10
,v
6
,v
12
,v
4
>
|
Рис. 3.
Топологический рисунок плоской конфигурации 1.
В
процессе
планаризации
удалены ребра е
7
и е
19
.
Вращение вершин плоского графа:
вращение вершины
v
1
:
v
11
v
7
v
9
v
11
вращение вершины
v
2
:
v
8
v
9
v
7
v
8
вращение вершины
v
3
:
v
7
v
10
v
11
вращение вершины
v
4
:
v
11
v
9
v
8
v
13
вращение вершины
v
5
:
v
9
v
11
v
9
вращение вершины
v
6
:
v
13
v
10
v
13
вращение вершины
v
7
:
v
1
v
3
v
2
v
1
вращение вершины
v
8
:
v
4
v
2
v
3
v
4
вращение вершины
v
9
:
v
4
v
5
v
1
v
2
v
4
вращение вершины
v
10
:
v
3
v
6
v
3
вращение вершины
v
11
:
v
5
v
4
v
1
v
5
вращение вершины
v
12
:
v
4
v
6
v
4
вращение вершины
v
13
:
v
4
v
3
v
6
v
4
Таблица 3.2. Плоская конфигурация 2.
|
|
Множество
циклов графа в виде ребер:
|
Множество
циклов графа в виде
вершин:
|
Кортеж вершин
изометрических циклов:
|
|
с
15
|
{e
10
,e
11
,e
20
,e
21
}
|
{v
13
,v
6
,v
10
,v
3
}
|
<
v
13
,v
6
,v
10
,v
3
>
|
|
с
8
|
{e
5
,e
6
,e
12
,e
13
}
|
{v
9
,v
4
,v
8
,v
2
}
|
<
v
9
,v
4
,v
8
,v
2
>
|
|
с
16
|
{e
12
,e
16
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
4
}
|
<
v
9
,v
5
,v
11
,v
4
>
|
|
с
13
|
{e
8
,e
10
,e
13
,e
14
}
|
{v
8
,v
4
,v
13
,v
3
}
|
<
v
8
,v
4
,v
13
,v
3
>
|
|
с
5
|
{e
2
,e
3
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
1
}
|
<
v
1
,v
11
,v
5
,v
9
>
|
|
с
6
|
{e
4
,e
6
,e
8
,e
9
}
|
{v
7
,v
3
,v
8
,v
2
}
|
<
v
2
,v
8
,v
3
,v
7
>
|
|
с
18
|
{e
14
,e
15
,e
20
,e
22
}
|
{v
13
,v
6
,v
12
,v
4
}
|
<
v
4
,v
12
,v
6
,v
13
>
|
|
с
7
|
{e
4
,e
7
,e
9
,e
11
}
|
{v
7
,v
3
,v
10
,v
2
}
|
<
v
7
,v
3
,v
10
,v
2
>
|
|
обод
|
{e
21
,e
5
,e
16
,e
2
,e
3
,e
15
,e
22
,e
7
}
|
{v
10
,v
2
,v
9
,v
1
,v
11
,v
4
,v
12
,v
6
}
|
<
v
6
,v
12
,v
4
,v
11
,v
1
,v
9
,v
2
,v
10
>
|
Рис. 4. Плоская
конфигурация 2.
В
процессе
планаризации
удалены ребра е
1
и е
19
.
Вращение вершин плоского графа:
вращение вершины
v
1
:
v
11
v
9
v
11
вращение вершины
v
2
:
v
10
v
7
v
8
v
9
v
10
вращение вершины
v
3
:
v
10
v
13
v
8
v
7
v
10
вращение вершины
v
4
:
v
8
v
13
v
12
v
11
v
9
v
8
вращение вершины
v
5
:
v
9
v
11
v
9
вращение вершины
v
6
:
v
13
v
10
v
12
v
13
вращение вершины
v
7
:
v
2
v
3
v
2
вращение вершины
v
8
:
v
3
v
4
v
2
v
3
вращение вершины
v
9
:
v
1
v
2
v
4
v
5
v
1
вращение вершины
v
10
:
v
6
v
3
v
2
v
6
вращение вершины
v
11
:
v
4
v
1
v
5
v
4
вращение вершины
v
12
:
v
4
v
6
v
4
вращение вершины
v
13
:
v
3
v
6
v
4
v
3
Таблица 3.3. Плоская конфигурация 3.
|
|
Множество
циклов графа в виде ребер:
|
Множество
циклов графа в виде
вершин:
|
Кортеж вершин
изометрических циклов:
|
|
с
8
|
{e
5
,e
6
,e
12
,e
13
}
|
{v
9
,v
4
,v
8
,v
2
}
|
<
v
9
,v
4
,v
8
,v
2
>
|
|
с
13
|
{e
8
,e
10
,e
13
,e
14
}
|
{v
8
,v
4
,v
13
,v
3
}
|
<
v
8
,v
4
,v
13
,v
3
>
|
|
с
17
|
{e
12
,e
15
,e
18
,e
19
}
|
{v
9
,v
5
,v
12
,v
4
}
|
<
v
9
,v
5
,v
12
,v
4
>
|
|
с
18
|
{e
14
,e
15
,e
20
,e
22
}
|
{v
13
,v
6
,v
12
,v
4
}
|
<
v
4
,v
12
,v
6
,v
13
>
|
|
с
6
|
{e
4
,e
6
,e
8
,e
9
}
|
{v
7
,v
3
,v
8
,v
2
}
|
<
v
2
,v
8
,v
3
,v
7
>
|
|
с
15
|
{e
10
,e
11
,e
20
,e
21
}
|
{v
13
,v
6
,v
10
,v
3
}
|
<
v
13
,v
6
,v
10
,v
3
>
|
|
с
5
|
{e
2
,e
3
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
1
}
|
<
v
1
,v
11
,v
5
,v
9
>
|
|
c
1
|
{e
1
,e
2
,e
4
,e
5
}
|
{v
7
,v
2
,v
9
,v
1
}
|
<
v
1
,v
9
,v
2
,v
7
>
|
|
обод
|
{e
19
,e
22
,e
9
,e
11
,e
21
,e
3
,e
17
,e
1
}
|
{v
12
,v
6
,v
10
,v
3
,v
7
,v
1
,v
11
,v
5
}
|
<
v
5
,v
11
,v
1
,v
7
,v
3
,v
10
,v
6
,v
12
>
|
Рис. 5. Плоская
конфигурация 3.
В
процессе
планаризации
удалены ребра е
7
и е
16
.
Вращение вершин плоского
cуграфа
:
вращение вершины
v
1
:
v
7
v
9
v
11
v
7
вращение вершины
v
2
:
v
8
v
7
v
9
v
8
вращение вершины
v
3
:
v
8
v
13
v
10
v
7
v
8
вращение вершины
v
4
:
v
9
v
12
v
13
v
8
v
9
вращение вершины
v
5
:
v
9
v
11
v
12
v
9
вращение вершины
v
6
:
v
10
v
13
v
12
v
10
вращение вершины
v
7
:
v
2
v
3
v
1
v
2
вращение вершины
v
8
:
v
4
v
3
v
2
v
4
вращение вершины
v
9
:
v
2
v
1
v
5
v
4
v
2
вращение вершины
v
10
:
v
3
v
6
v
3
вращение вершины
v
11
:
v
5
v
1
v
5
вращение вершины
v
12
:
v
5
v
6
v
4
v
5
вращение вершины
v
13
:
v
4
v
6
v
3
v
4
Следует
заметить, что кортеж циклов в вершинной записи позволяет записывать циклы в
векторной форме:
< v
9
,v
4
,v
8
,v
2
>
= (v
9
,v
4
) + (v
4
,v
8
) + (v
8
,v
2
)
+ (
v
2
,
v
9
);
< v
8
,v
4
,v
13
,v
3
>
= (v
8
,v
4
) + (v
4
,v
13
) + (v
13
,v
3
)
+ (
v
3
,
v
8
);
< v
9
,v
5
,v
12
,v
4
>
= (v
9
,v
5
) + (v
5
,v
12
) + (v
12
,v
4
)
+ (
v
4
,
v
9
);
< v
4
,v
12
,v
6
,v
13
>
= (v
4
,v
12
) + (v
12
,v
6
) + (v
6
,v
13
)
+ (
v
13
,
v
4
);
< v
2
,v
8
,v
3
,v
7
>
= (v
2
,v
8
) + (v
8
,v
3
) + (v
3
,v
7
)
+ (
v
7
,
v
2
);
< v
13
,v
6
,v
10
,v
3
>
= (v
13
,v
6
) + (v
6
,v
10
) + (v
10
,v
3
)
+ (
v
3
,
v
13
);
< v
1
,v
11
,v
5
,v
9
>
= (v
1
,v
11
) + (v
11
,v
5
) + (v
5
,v
9
)
+ (
v
9
,
v
1
);
< v
1
,v
9
,v
2
,v
7
>
=
(v
1
,v
9
) + (v
9
,v
2
) + (v
2
,v
7
)
+ (
v
7
,
v
1
);
< v
5
,v
11
,v
1
,v
7
,v
3
,v
10
,v
6
,v
12
>=
(v
5
,v
11
) + (v
11
,v
1
) + (v
1
,v
7
)
+ (
v
7
,
v
3
) + (v
3
,v
10
)
+ (v
10
,v
6
) + (v
6
,v
12
) + (
v
12
,
v
5
).
Сумма всех векторных записей для плоской
конфигурации есть пустое множество, так как
.
Следует
заметить, что подмножество циклов, характеризующееся нулевым значением
функционала Понтрягина-
Куратовского
(или функционала
Маклейна
) не может быть планарной конфигурацией, так как
описывает суграф с точкой сочленения (см. рис. 6).
|
с
13
|
{e
8
,e
10
,e
13
,e
14
}
|
{v
8
,v
4
,v
13
,v
3
}
|
|
с
17
|
{e
12
,e
15
,e
18
,e
19
}
|
{v
9
,v
5
,v
12
,v
4
}
|
|
с
18
|
{e
14
,e
15
,e
20
,e
22
}
|
{v
13
,v
6
,v
12
,v
4
}
|
|
с
15
|
{e
10
,e
11
,e
20
,e
21
}
|
{v
13
,v
6
,v
10
,v
3
}
|
|
с
16
|
{e
12
,e
16
,e
17
,e
18
}
|
{v
9
,v
5
,v
11
,v
4
}
|
|
с
1
|
{e
1
,e
2
,e
4
,e
5
}
|
{v
7
,v
2
,v
9
,v
1
}
|
Рис. 6. Суграф с точкой сочленения.
Будем
рассматривать следующий этап создания топологического рисунка плоского суграфа.
Теоретическое обоснование данного метода изложено в работах [10-11].
Данный
этап рассмотрим на примере следующего графа, заданного
инцидентором
.
Выделим
в данном графе одну из плоских конфигураций, например, следующую (рис. 7).
Рис.7. Топологический рисунок плоской конфигурации.
Рассмотрим обод данной плоской
конфигурации как замкнутую последовательность ориентированных ребер. Назовём
такое построение координатно-базисной системой КБС [10,11]. Проведем
ребра, удаленные в процессе
планаризации
, которые
имеют две концевые вершины, совместимые с вершинами обода
(см. рис. 7).
Запишем КБС в виде замкнутого кортежа,
состоящего из ориентированных ребер <
e
44
,
e
70
,
e
71
,
e
39
,
e
38
,
e
32
,
e
33
,
e
40
,
e
41
,
e
58
,
e
56
,
e
53
,
e
55
,
e
72
,
e
51
,
e
52
,
e
67
,
e
14
,
e
13
,
e
6
,
e
7
,
e
18
,
e
17
,
e
25
,
e
24
,
e
46
,
e
49
,
e
47
,
e
68
,
e
60
,
e
20
,
e
23
,
e
35
,
e
36
,
e
28
,
e
30
,
e
43
>.
Неориентированное ребро можно представить в виде двух разнонаправленных
ориентированных дуг.
Тогда для каждого ориентированного
ребра существует проекция (в теоретико-множественном смысле) на
координатно-базисную систему.
Например
(рис. 8):
Рис. 8. Координатно-базисная система и проведенные
ребра.
Запишем КБС в виде
замкнутого кортежа, состоящего из ориентированных ребер <
e
44
,
e
70
,
e
71
,
e
39
,
e
38
,
e
32
,
e
33
,
e
40
,
e
41
,
e
58
,
e
56
,
e
53
,
e
55
,
e
72
,
e
51
,
e
52
,
e
67
,
e
14
,
e
13
,
e
6
,
e
7
,
e
18
,
e
17
,
e
25
,
e
24
,
e
46
,
e
49
,
e
47
,
e
68
,
e
60
,
e
20
,
e
23
,
e
35
,
e
36
,
e
28
,
e
30
,
e
43
>.
Неориентированное ребро можно представить в виде двух разнонаправленных
ориентированных дуг.
Тогда для каждого ориентированного
ребра существует проекция (
в
множественном смысле) на
координатно-базисную систему. Например, из двух проекций ребра выделим одну
проекцию, но минимальную по длине.
В
соответствии с законами векторной алгебры пересечений будем считать, что ребра
пересекаются, если пересекаются их проекции (в терминах пересечения теории
множеств). Ребра не пересекаются, если результат пересечения проекций есть
пустое множество или одна проекция полностью включается в другую.
Рассмотрим
пересечения ребра
e
9
.
Из рассмотрения следует, что ребро
e
9
пересекается со всеми
ребрами кроме ребра
e
50
.
Для
определения удаления ребер необходимо рассмотреть все случаи парного
пересечения ребер. После этого будем последовательно удалять ребра, максимально
пересекающиеся с другими. В конце процесса выделится множество непересекающихся
ребер. В нашем случае непересекающиеся соединения представлены на рис. 9.
В
результате выделяются новые простые циклы, которые можно добавить к
существующим
.
с
15
= {
e
37
,
e
43
,
e
41
,
e
70
,
e
71
,
e
39
};
с
16
= {
e
37
,
e
38
,
e
32
,
e
33
,
e
40
,
e
34
,
e
36
,
e
28
,
e
30
};
с
17
= {
e
34
,
e
41
,
e
61
,
e
20
,
e
23
,
e
35
};
с
18
= {
e
54
,
e
55
,
e
72
,
e
51
,
e
52
,
e
67
,
e
11
,
e
25
,
e
24
,
e
46
};
с
19
= {
e
11
,
e
17
,
e
18
,
e
6
,
e
7
,
e
15
};
c
0
= {
e
61
,
e
58
,
e
56
,
e
53
,
e
54
,
e
49
,
e
47
,
e
68
,
e
60
}.
Рис. 9. Непересекающиеся соединения.
Совокупность
простых и изометрических циклов образует топологический рисунок плоского
суграфа (см. рис. 10).
Рис. 10. Топологический рисунок плоского суграфа.
В
данной работе рассмотрены вопросы
диакоптического
подхода к построению топологического рисунка плоской части
непланарного
графа.
Показано,
что решение вопроса выделения плоской части
непланарного
графа для
несепарабельной
части
непланарного
графа состоит из двух этапов.
Первый
этап построения топологического рисунка основан на
матроидных
свойствах множества изометрических циклов графа. Предложен метод выделения
топологического рисунка плоской части
непланарного
графа методами алгебры структурных чисел. Исходной информацией для решения
задачи первого этапа служит множество изометрических циклов графа и позволяет
свести решение к методам дискретной оптимизации.
Второй
этап присоединения циклов строится на базе методов векторной алгебры
пересечений. Основой данного метода служит построение
координаино
-базисной
системы на основе обода выделенной плоской части графа первого этапа.
1.
М. Гэри, Д.
Джонсон.
Вычислительные машины и труднорешаемые задачи: Пер. с англ. – М.: Мир, 1982. – 416 с.
2.
Г. Крон
. Исследование сложных систем по
частям (диакоптика). Перев. с англ. – М.: Наука, 1972. – 544 стр.
3.
Г.
Рингель
.
Теорема о раскраске карт. / Г. Рингель – М.: Мир. – 1977. – 126 с.
4.
T.
Kavitha
, C.
Liebchen
, K.
Mehlhorn
, D.
Michail
, et al.
Cycle bases in graphs – characterization, algorithms, complexity, and
applications //
Comput
.
Sci
.
Rev
.
2009. No.3. P.199–243.
5.
М. Свами.
Графы, сети и алгоритмы. М.: Мир. –
1984. – 455 с.
6.
С. Беллерт.
Анализ и синтез электрических цепей методом структурных
чисел/С. Беллерт, Г. Возняцки. – М.: Мир, 1972. – 332 с.
7.
С. Мак-
Лейн
.
Комбинаторное условие для плоских графов / С. Мак-
Лейн
// В кн.: Кибернетический сборник. Новая серия. – 1970.
Вып
.
7. – С.133–144.
8.
Курапов С.В.,
Толок А.В.
Методы
построения топологического рисунка графа // Автоматика и телемеханика. – 2013,
№ 9. – C. 78–97.
9.
Курапов С.В.,
Давидовский
М.В.
Построение общего рисунка соединений
в плоских конструктивах // Компоненты и технологии. 2016. № 3.
С. 72–77.
10.
Раппопорт
Л.И.,
Мороговский
Б.Н.,
Поливцев
С.А.
Векторная
алгебра и проектирование топологии соединений//В кн.: Вопросы автоматизации
проектирования интегральных схем. – Киев: ИК УССР. – 1976. – С.107–124.
11.
Раппопорт
Л.И.,
Мороговский
Б.Н.,
Поливцев
С.А.
Векторная
алгебра пересечений//В кн.: Многопроцессорные вычислительные структуры.-
Таганрог
.-1982.-
вып
.2(11).-
С
.53-56.
Generating a topological drawing of the flat part of a nonplanar graph
Authors: S.V. Kurapov1,A, M.V. Davidovsky2,B, A.V. Tolok3,C
A Zaporozhye National University, Ukraine
B Zaporozhye Institute of Postgraduate Pedagogical Education, Ukraine
C Moscow State Technological University «STANKIN», Russia
1 ORCID: 0000-0003-4563-7227, lilili5050@rambler.ru
2 ORCID: 0000-0002-9472-3351, m.davidovsky@gmail.com
3 ORCID: 0000-0002-7257-9029, a.tolok@stankin.ru
Abstract
In this article, we consider the issues of applying the diakoptic approach to constructing a topological drawing of the planar part of a non-planar graph. It is demonstrated that the first stage of constructing a topological drawing is based on the matroid properties of the set of graph isometric cycles. In the article, we propose a method for constructing a topological drawing of the planar part of a non-planar graph using the methods of structure numbers algebra. The initial solution is based on the set of graph isometric cycles that allows application of discrete optimization methods. The second stage of joining the cycles is based on the methods of vector algebra of intersections. In the article we describe the essential mathematical concepts and structures for solving the problem of constructing a planar topological drawing of a non-planar graph. The presentation is supported by detailed illustrative examples.
Keywords: graph, rotation of graph vertices, isometric cycles, planarity, planar part of a graph.
1.
M.
Gary
, D. Johnson.
Computing machines and
hard-to-solve problems.
–
M.: Mir, 1982. – 416 p.
2.
G.
Cron
.
Investigation of complex
systems in parts (diakoptics). Trans. with English. – Moscow: Nauka, 1972. –
544 p.
3.
G.
Ringel
.
Map Color Theorem. Repr.
of the orig. 1st ed. (1974), Springer, 2011. – 212 p.
4.
T.
Kavitha
, C. Liebchen, K. Mehlhorn,
D. Michail, et al.
Cycle bases in graphs – characterization, algorithms,
complexity, and applications // Comput. Sci. Rev. 2009. No.3. P.199–243.
5.
M.
N. S.
Swamy
, K. Thulasiraman.
Graphs, networks, and
algorithms. – J. Wiley & Sons, 1981.
6.
S.
Bellert
.
Analysis and synthesis of
electrical circuits by the method of structural numbers / S. Bellert, G.
Wozniacki. – Moscow: Mir, 1972. – 332 p.
7.
S.
MacLane
.
A combinatorial condition
for planar graphs // Fund. Math., 28. – 1937. – P. 22–32.
8.
S.
V.
Kurapov
, A. V. Tolok.
The topological drawing of
a graph: Construction methods // Autom. Remote Control. 2013. Vol. 74, Issue 9.
– P. 1494–1509.
9.
Kurapov
S. V, Davidovsky M. V.
Construction of a general
drawing of connections in planar structures // Components and technologies. –
2016. No. 3. – P. 72–77.
10.
Rappoport
L. I., Morogovskiy B. N.,
Polivtsev S. A.
Vector algebra and projection of connection topology. In: Problems of
Automation of Design of Integrated Circuits. – Kiev: IR of the USSR . – 1976. – P. 107–124.
11.
Rappoport
L. I., Morogovskiy B. N.,
Polivtsev S. A.
Vector algebra of intersections // In: Multiprocessor computing
structures. – Taganrog. – 1982. – Vyp. 2 (11). – P. 53–56.
