Метод визуализации рисунка непланарного графа

Kurapov, S.V.; Davidovsky, M.V.; Tolok, A.V.

doi:10.26583/sv.11.2.10

Научная визуализация, 2019, том 11, номер 2, страницы 126 - 142, DOI: 10.26583/sv.11.2.10

Метод визуализации рисунка непланарного графа

Авторы: С.В. Курапов^1,A, М.В. Давидовский^2,B, А.В. Толок^3,C

^A Запорожский национальный университет, Украина

^B Запорожский институт последипломного педагогического образования, Украина

^C Московский государственный технологический университет «СТАНКИН», Россия

¹ ORCID: 0000-0003-4563-7227, lilili5050@rambler.ru

² ORCID: 0000-0002-9472-3351, m.davidovsky@gmail.com

³ ORCID: 0000-0002-7257-9029, a.tolok@stankin.ru

Аннотация

В данной работе рассмотрены вопросы описания рисунка непланарного графа. Предложен метод построения топологического рисунка плоской части непланарного графа. Исходной информацией для решения задачи служит множество изометрических циклов графа, что позволяет свести решение к методам дискретной оптимизации. Рассмотрены необходимые понятия и структуры для решения задачи построения непланарного топологического рисунка графа.

Ключевые слова: граф, вращение вершин графа, изометрические циклы, планарность, плоская часть графа.

1. Введение

В данной работе представлен метод описания топологического рисунка непланарного графа. Рассматривается задача выделения максимально плоского суграфа и ее место в процессе построения топологического рисунка.

Граф G = (V,E;P) с множеством вершин V = {v₁,v₂,...,v_n} и множеством ребер E = {e₁,e₂,...,e_m} представляется либо трехместным предикатом Р, либо матрицей смежностей или матрицей инциденций. Здесь: n – количество вершин, а m – количество ребер. Также применяется более краткая запись графа в виде G = (V,E).

Будем рассматривать только несепарабельные графы.

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

Рис. 1. Различные рисунки графа К₅.

Путем элементарных преобразований любой граф можно привести к несепарабельному графу. Теория графов описывает граф с точностью до изоморфизма, игнорируя описание рисунка графа на плоскости. Так граф К₅ можно представить в виде набора следующих рисунков (см. рис. 1), а все множество рисунков описывается только одним трехместным предикатом [9]. Поэтому создание методов построения и описания рисунка графа на плоскости актуально.

Необходимым понятием для описания плоского рисунка графа G является понятие о вращении вершин графа, введенное Г. Рингелем [8].

Определение 2. Вращение вершины x_i графа G – это ориентированный циклический порядок (или циклическая перестановка) всех ребер, инцидентных вершине x_i.

Определение 3. Множество вращений всех вершин будем обозначать символом , и называть вращением графа (G,).

Граф G с множеством вращений вершин часто бывает удобно изображать на плоскости таким образом, чтобы перебирая ребра инцидентные некоторой вершине, мы получили вращение в этой вершине. Вращение графа можно описывать следующим образом. Выпишем циклическую перестановку соседних вершин для каждой вершины v_i. Эта перестановка порождается вращением вершины v_i, т.е. циклической перестановкой ребер инцидентных i-й вершине. Впредь, для краткости записи вершины и ребра будем обозначать цифрами, каждый раз указывая их принадлежность.

Например, графу с вращением , показанному на рис. 2, соответствует следующее множество вращающихся вершин:

Рис. 2. Граф и вращение его вершин.

= {,,,,,} = { = <v₂,v₃,v₄>, = <v₅,v₃,v₁,v₆>, = <v₁,v₂,v₅,v₄>,

= <v₁,v₃,v₅,v₆>, = <v₄,v₃,v₂,v₆>, = <v₂,v₄,v₅>}.

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

Определение 4[12]. Изометрический подграф – подграф графа G, у которого все расстояния внутри те же самые, что и в G.

Определение 5. Изометрическим циклом в графе называется простой цикл, для которого кратчайший путь между любыми двумя его вершинами состоит из рёбер этого цикла.

Изометрический цикл – частный случай изометрического подграфа [3].

2. Изометрические циклы и топологический рисунок графа

Изометрический цикл в графе имеет следующее свойство: в графе G между двумя любыми несмежными вершинами данного цикла не существует маршрутов меньшей длины, чем маршруты, принадлежащие самому циклу.

Подмножество, состоящее из изометрических циклов, будем называть подмножеством изометрических циклов, и обозначать C_t.

Пример 1. Для плоского графа G с вращением, представленным на рис. 1, имеем следующую систему индуцированных изометрических циклов:

c₁ = <v₁,v₃,v₂>, c₂ = <v₁,v₄,v₃>, c₃ = <v₂,v₃,v₅>, c₄ = <v₅,v₃,v₄>, c₅ = <v₂,v₅,v₆>,

c₆ = <v₆,v₅,v₄> и обод c₀ = <v₂,v₆,v₄,v₁> в вершинной записи

Реберная запись циклов имеет вид: c₁ = {e₁,e₂,e₄}, c₂ = {e₂,e₃,e₇}, c₃ = {e₇,e₈,e₉},

c₄ = {e₄,e₅,e₈}, c₅ = {e₅,e₆,e₁₁}, c₆ = {e₉,e₁₀,e₁₁}, c₀ = {e₁,e₃,e₆,e₁₀}.

Заметим, что не следует утверждать, что если несепарабельный граф планарен и имеется вращение , описывающее плоский рисунок, то циклы, индуцированные вращением – суть изометрические циклы графа. В качестве примера рассмотрим следующий плоский граф.

Пример 2. Рассмотрим плоский граф G.

Рис. 3. Рисунок плоского графа.

	Множество изометрических циклов графа в виде ребер	Множество изометрических циклов графа в виде вершин
цикл 1	{e₁,e₂,e₈};	{v₁,v₂,v₃};
цикл 2	{e₁,e₄,e₁₀};	{v₁,v₂,v₁₀};
цикл 3	{e₂,e₃,e₁₂};	{v₁,v₃,v₅};
цикл 4	{e₂,e₄,e₁₁,e₁₆};	{v₁,v₃,v₄,v₁₀};
цикл 5	{e₃,e₄,e₁₇};	{v₁,v₅,v₁₀};
цикл 6	{e₃,e₅,e₁₈};	{v₁,v₅,v₁₁};
цикл 7	{e₃,e₇,e₂₀};	{v₁,v₅,v₁₈};
цикл 8	{e₅,e₆,e₂₇};	{v₁,v₁₁,v₁₂};
цикл 9	{e₅,e₇,e₂₈,e₃₃};	{v₁,v₁₁,v₁₃,v₁₈};
цикл 10	{e₆,e₇,e₃₀};	{v₁,v₁₂,v₁₈};
цикл 11	{e₈,e₁₀,e₁₁,e₁₆};	{v₂,v₃,v₄,v₁₀};
цикл 12	{e₈,e₁₀,e₁₂,e₁₇};	{v₂,v₃,v₅,v₁₀};
цикл 13	{e₈,e₉,e₁₁,e₁₅,e₂₅};	{v₂,v₃,v₄,v₈,v₉};
цикл 14	{e₉,e₁₀,e₂₆};	{v₂,v₈,v₁₀};
цикл 15	{e₁₁,e₁₂,e₁₃};	{v₃,v₄,v₅};
цикл 16	{e₁₃,e₁₆,e₁₇};	{v₄,v₅,v₁₀};
цикл 17	{e₁₄,e₁₅,e₂₂};	{v₄,v₆,v₉};
цикл 18	{e₁₅,e₁₆,e₂₅,e₂₆};	{v₄,v₈,v₉,v₁₀};
цикл 19	{e₁₈,e₁₉,e₂₈};	{v₅,v₁₁,v₁₃};
цикл 20	{e₁₈,e₂₀,e₂₇,e₃₀};	{v₅,v₁₁,v₁₂,v₁₈};
цикл 21	{e₁₉,e₂₀,e₃₃};	{v₅,v₁₃,v₁₈};
цикл 22	{e₂₁,e₂₂,e₂₄};	{v₆,v₇,v₉};
цикл 23	{e₂₃,e₂₄,e₂₅};	{v₇,v₈,v₉};
цикл 24	{e₂₇,e₂₈,e₃₀,e₃₃};	{v₁₁,v₁₂,v₁₃,v₁₈};
цикл 25	{e₂₇,e₂₈,e₂₉,e₃₂,e₃₇};	{v₁₁,v₁₂,v₁₃,v₁₅,v₁₇};
цикл 26	{e₂₉,e₃₀,e₃₈};	{v₁₂,v₁₅,v₁₈};
цикл 27	{e₃₁,e₃₂,e₃₅};	{v₁₃,v₁₄,v₁₇};
цикл 28	{e₃₂,e₃₃,e₃₇,e₃₈};	{v₁₃,v₁₅,v₁₇,v₁₈};
цикл 29	{e₃₄,e₃₅,e₃₉};	{v₁₄,v₁₆,v₁₇};
цикл 30	{e₃₆,e₃₇,e₃₉};	{v₁₅,v₁₆,v₁₇};

Пусть L_G – множество всех суграфов этого графа [10]. На множестве всех суграфов можно ввести операцию кольцевого суммирования:

(V,E₁) ⊕ (V,E₂) (V,(E₁E₂)\(E₁E₂))

(1)

И тогда, количество индуцированных изометрических циклов определяется цикломатическим числом графа n(G) = m – n +1, а обод определяется кольцевым сложением базисных изометрических циклов и может представлять собой как изометрический цикл, так и простой цикл:

с₀ = с₁ ⊕ с₂ ⊕ … ⊕ с_n_(G)

(2)

Теперь можно ввести следующее определение топологического рисунка графа.

Определение 6. Топологическим рисунком плоского графа будем называть теоретико-множественную структуру, состоящую из самого графа G и вращений всех его вершин. Будем записывать его как (G,).

Топологический рисунок плоского графа позволяет осуществлять теоретико-множественные операции с рисунком графа алгебраическими методами, не производя никаких геометрических построений на плоскости.

Пространство суграфов L_G состоит из двух подпространств: подпространства циклов C_G и подпространства разрезов S_G [10]. Таким образом, простые циклы графа с_b, индуцированные вращением вершин графа, принадлежат подпространству циклов C_G.

с_b C_G

(3)

В случае непланарных графов понятия вращения вершин не достаточно, так как вращение вершин не позволяет описывать пересечение ребер. В качестве примера рассмотрим рисунки непланарного графа G (см. рис. 4) заданного одним и тем же вращением вершин.

Рис. 4. Рисунок графа G c пересекающимися ребрами и вращение его вершин.

На рис. 4. вращение вершин в обоих случаях одинаково и производится по часовой стрелке, однако пересечение ребер различно. Например, на рисунке слева ребро (v₇,v₁₀) пересекается с ребрами (v₂,v₆) и (v₈,v₉), а на рисунке справа ребро (v₇,v₁₀) пересекается только с ребром (v₂,v₆).

Для обоих рисунков диаграмма вращений по часовой стрелке имеет один и тот же вид:

₁: v₈ v₇ v₂

₂: v₁ v₉ v₆ v₃

₃: v₂ v₇ v₁₀ v₁₁ v₄

₄: v₃ v₆ v₅

₅: v₄ v₁₁ v₁₀ v₆ v₈

₆: v₂ v₇ v₈ v₅ v₄

₇: v₁ v₆ v₁₀ v₃

₈: v₅ v₆ v₁₀ v₉ v₁

₉: v₂ v₈ v₁₀

₁₀: v₉ v₇ v₈ v₅ v₁₁ v₃

₁₁: v₃ v₁₀ v₅

3. Мнимые вершины

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

Определение 7. Мнимая вершина – это топологическое местоположение пересечения двух ребер.

На рис. 5 представлен рисунок графа с мнимыми вершинами. Для идентификации мнимых вершин применяется обозначение отличное от обозначения заданных вершин графа. Это может быть запись в виде номеров вершин больше n, если количество вершин в исходном графе равно n. Таким образом, запись (G(n_e,n_f),), будет обозначать граф G c естественными и мнимыми вершинами, а также некоторым вращением . Эта запись одновременно будет характеризовать топологический рисунок графа с пересекающимися ребрами.

Рис. 5. Рисунок графа G c мнимыми вершинами.

Общее количество вершин такого графа определяется по формуле:

n = n_e + n_f

(4)

где: n_e – количество естественных вершин графа, n_f – количеством мнимых вершин.

Естественно, что введение мнимых вершин изменяет первоначальную структуру исходного графа. Изменяется как количество вершин и ребер, так и состав, и структура трехместного предиката. Сказанное рассмотрим на примере топологического рисунка графа с мнимыми вершинами.

Пример 3. Опишем топологический рисунок непланарного графа К_6, представленного на рис. 5. Пусть множество основных вершин графа V = {v₁,v₂,v₃,v₄,v₅,v₆}, а множество мнимых вершин V_m = {v₇,v₈,v₉,v₁₀}. Тогда трехместный предикат исходного графа Р_m будет иметь вид:

P_m = {(e₁ → <v₁,v₂> & <v₂,v₁>),(e₂ → <v₁,v₃> & <v₃,v₁>),

(e₃ → <v₁,v₄> & <v₄,v₁>),(e₄ → <v₁,v₅> & <v₅,v₁>);

(e₅ → <v₁,v₆> & <v₆,v₁>),(e₆ → <v₂,v₃> & <v₃,v₂>),

(e₇ → <v₂,v₄> & <v₄,v₂>),(e₈ → <v₂,v₅> & <v₅,v₂>),

(e₉ → <v₂,v₆> & <v₆,v₂>),(e₁₀ → <v₃,v₄> & <v₄,v₃>),

(e₁₁ → <v₃,v₅> & <v₅,v₃>),(e₁₂ → <v₃,v₆> & <v₆,v₃>),

(e₁₃ → <v₄,v₅> & <v₅,v₄>),(e₁₄ → <v₄,v₆> & <v₆,v₄>),

(e₁₅ → <v₅,v₆> & <v₆,v₅>)}.

Рис. 6. Топологический рисунок непланарного графа К₆ с мнимыми вершинами.

Пусть вращение вершин графа с мнимыми вершинами задано диаграммой:

₁: v₂ v₁₀ v₄ v₉ v₇

₂: v₃ v₁₀ v₁ v₇ v₆

₃: v₅ v₄ v₁₀ v₂ v₆

₄: v₃ v₅ v₉ v₁ v₁₀

₅: v₆ v₈ v₉ v₄ v₃

₆: v₃ v₂ v₇ v₈ v₅

₇: v₂ v₁ v₈ v₆

₈: v₆ v₇ v₉ v₅

₉: v₁ v₄ v₅ v₈

₁₀: v₂ v₃ v₄ v₁

Так как мнимая вершина характеризуется пересечением двух ребер ( – знак пересечения), можно записать:

v₇ → (<v₂,v₈> & <v₈,v₂>) (<v₁,v₆> & <v₆,v₁>),

v₈ → (<v₆,v₉> & <v₉,v₆>) (<v₇,v₅> & <v₅,v₇>),

v₉ → (<v₁,v₅> & <v₅,v₁>) (<v₄,v₈> & <v₈,v₄>),

v₁₀ → (<v₂,v₄> & <v₄,v₂>) (<v₁,v₃> & <v₃,v₁>).

Введение мнимых вершин позволяет свести описание рисунка непланарного графа к топологическому плоскому рисунку.

Таким образом, для описания топологического рисунка непланарного графа достаточно иметь трехместный предикат и вращение основных и мнимых вершин графа. Такое представление топологического рисунка непланарного графа с пересекающимися ребрами разбивает процесс построения топологического рисунка на два этапа. Первый этап – построение плоской части графа. Второй этап – проведения ребер, не включенных в топологический рисунок плоской части. Ребра, не включенные в плоский топологический рисунок, будем называть ребрами, удаленными в процессе планаризации графа. Естественно, что удаленные в процессе планаризации ребра можно построить как пересекающиеся с ребрами плоской части графа и на этом этапе вводить мнимые вершины. Очевидно, что для первой задачи критерием достижения цели должен служит максимально плоский подграф.

4. Максимально плоский подграф и максимально плоский суграф

В англоязычной литературе встречаются два определения максимальных плоских частей непланарного графа. Первое определение: наибольший планарный подграф не планарного графа (maximum planar subgraph) – это планарный граф с наибольшим количеством ребер среди всех подграфов графа G. Второе определение: максимальный планарный подграф не планарного графа G = (V,E) (maximal planar subgraph) – это такой планарный подграф P = (V,E\F) графа G, что добавление любого ребра из F к P нарушает его планарность, то есть P не планарен для каждого eF [9].

Как известно, задача выделения максимально плоского подграфа относится к классу NP-полных задач [2]. Для решения задачи выделения максимально плоского суграфа применяют экспоненциальные переборные алгоритмы. Очевидно, что результат выделения максимально плоского подграфа для несепарабельных графов переборным алгоритмом принадлежит пространству суграфов графа L_G.

Точное решение задачи построения максимально плоского суграфа возможно путем перечисления вариантов удаления ребер с заданным их количеством, начиная с единицы, и до получения результата. При каждом выборе варианта нужно осуществлять проверку выделенной части графа на планарность. В этом случае применение метода Хопкрофта-Тарьяна [11] вполне обосновано, но тогда мы приходим к полному перебору вариантов [2].

С другой стороны, применить алгоритм Хопкрофта-Тарьяна напрямую для решения задачи построения топологического рисунка плоского подграфа для непланарного графа не представляется возможным, так как основная идея этого алгоритма – построение дерева графа с последующей укладкой сегментов относительно этого дерева. Но в непланарном графе в ветви выделенного дерева могут попасть удаляемые при планаризации ребра, что может качественно изменить решение задачи. Кроме того, алгоритм Хопкрофта-Тарьяна предназначен только для проверки графа на планарность и не предназначен для описания процесса построения топологического рисунка графа алгебраическими методами. Поэтому нужна другая математическая модель для решения поставленной задачи.

Для получения топологического рисунка нам нужен результат выделения плоской части графа в виде базиса простых циклов, находящегося в подпространстве циклов графа. Введем понятие максимально плоского суграфа.

Определение 8. Максимально плоским суграфом графа G, будем называть суграф несепарабельного графа, принадлежащий подпространству циклов, при минимальном удалении ребер.

На рис. 7-9 представлены соответствующие рисунки графа.


Рис. 7. Граф G.	Рис. 8. Максимально плоский подграф.	Рис. 9. Максимально плоский суграф.

Таким образом, возникает иной подход, основанный на цикломатических свойствах графа для решения задачи выделения максимально плоского подграфа и состоящий из двух последовательных этапов:

• построение максимально плоского несепарабельного суграфа;

• добавление единичных ребер до сепарабельного максимально плоского подграфа (пусть даже с нулевым количеством дополнительных ребер).

5. Выделение максимально плоского суграфа

Существование в графе G(V,E) определенного характерного подмножества простых циклов, называемое множеством изометрических циклов , порождает некоторое количество инвариантов графа, так как количество изометрических циклов и матрица расстояний в изоморфных графах постоянны [3,4].

Одним из таких инвариантов, по аналогии с вектором локальных степеней, является вектор количества изометрических циклов, проходящих по ребрам графа. Будем называть его вектором циклов по ребрам, и обозначать P_e:

P_e= (p_e1,p_e2,p_e3,…,p_em)

(5)

здесь p_ei – количество изометрических циклов графа проходящих по ребру e_i.

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

P_v= (p_v1,p_v2,p_v3,…,p_vn)

(6)

здесь p_vj – количество циклов проходящих по вершине v_j.

Для выделения максимально плоского суграфа воспользуемся критерием планарности Маклейна. Критерий планарности Маклейна основан на следующей теореме [6].

Теорема Маклейна [6]. Граф G планарен тогда и только тогда, когда существует такой базис, состоящий из простых циклов, где каждое ребро принадлежит не более чем двум циклам. Тогда любому подмножеству изометрических циклов мощностью можно поставить в соответствие значение функционала Маклейна, определяемое следующей формулой [5]:

(7)

где: p_i – количество циклов, проходящих по ребру i в векторе циклов по ребрам, m – количество ребер графа.

Если имеется базис линейного подпространства циклов c_b, состоящий из изометрических циклов, и обод, согласно выражению (4), и значение функционала Маклейна для базиса равно нулю, то вращение вершин графа характеризует плоский граф.

Следует заметить, что функционал Маклейна может характеризовать любое подмножество изометрических циклов с мощностью k большей цикломатического числа графа card(c_k)

Между цикломатическим числом плоского суграфа, количеством ребер m и количеством вершин n существует связь устанавливаемая формулой Эйлера:

= m - n + 1

(8)

Функционал F(с_k) принимает целое неотрицательное значение на множестве простых циклов с мощностью k, и проблема отыскания базиса Маклейна, таким образом, является частным случаем следующей задачи дискретной оптимизации: найти минимум F(с_b) на множестве матриц С размера × m, покрывающем все множество вершин графа.

Очевидно, что не для любого графа G минимум функционала F(c_b) будет равен нулю согласно критерию Маклейна. Отметим, что нулевое значение данный функционал принимает только в случае наличия базиса планарного графа. В общем случае решение указанной задачи минимизации позволяет построить приближенный полиномиальный алгоритм выделения максимально плоского суграфа [5,6].

Рассмотрим процесс выделения максимально плоского суграфа в случае выделения базиса изометрических циклов со значением функционала Маклейна не равного нулю.

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

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

- m +n -1 = (-1) – (m-1) +n -1 = (-1) – (m-q) +(n-(q-1)) -1= 0

(9)

Как видно, если при удалении цикла удаляется одно и только одно ребро, то нарушения формулы Эйлера не происходит. Если при удалении цикла удаляется не одно ребро, а q ребер, то полученный суграф состоит из q-1 компонент связности согласно выражению (9).

В случае удаления циклов и ребер функционал Маклейна уже не будет отвечать процессу построения рисунка графа, так как он строился в предположении отсутствия нулевых значений для вектора P_e. Для более точного описания процесса удаления ребер из базиса применим функционал Понтрягина-Куратовского:

(10)

где p_i – количество изометрических циклов, проходящих по ребру. Функционал Понтрягина-Куратовского характеризует подмножество изометрических циклов с мощностью, не превышающей цикломатическое число графа.

Данный функционал подобен функционалу Маклейна, но позволяет учитывать нулевые значения в векторе P_e в процессе удаления ребер из базиса.

6. Структурные числа и удаление циклов. Примеры построения топологического рисунка плоской части

Рассмотрим вопрос применения методов алгебры структурных чисел для описания процесса удаления циклов.

Алгебраической производной структурного числа W [1] называется число дW/да, определенное как:

столбцы, не содержащие элемент а, исключены

(11)

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

(12)

где q – количество удаленных ребер. Выражение (12) описывает последовательность удаления циклов.

Пример 4. Рассмотрим процесс построения топологического рисунка плоской части следующего непланарного графа G (см. рис. 10).

Множество изометрических циклов С_t состоит из следующих циклов:

с₁ = {e₁,e₂,e₅}; с₂ = {e₁,e₃,e₈,e₁₈}; с₃ = {e₁,e₄,e₈,e₁₉};

с₄ = {e₃,e₄,e₁₅,e₁₆}; с₅ = {e₃,e₄,e₁₈,e₁₉}; с₆ = {e₅,e₆,e₉};

с₇ = {e₆,e₇,e₁₀}; с₈ = {e₆,e₈,e₁₁,e₁₇}; с₉ = {e₁,e₃,e₇,e₁₂,e₁₅};

с₁₀ = {e₁,e₄,e₇,e₁₂,e₁₆}; с₁₁ = {e₇,e₈,e₁₃,e₁₇}; с₁₂ = {e₁₀,e₁₁,e₁₃};

с₁₃ = {e₇,e₈,e₁₂,e₁₅,e₁₈}; с₁₄ = {e₇,e₈,e₁₂,e₁₆,e₁₉}; с₁₅ = {e₁₂,e₁₃,e₁₄};

с₁₆ = {e₁₄,e₁₅,e₁₇,e₁₈}; с₁₇ = {e₁₄,e₁₆,e₁₇,e₁₉}; с₁₈ = {e₁₅,e₁₆,e₁₈,e₁₉}.

Рис. 10. Граф G.

Вектор циклов по ребрам имеет вид:

P_e = (5,1,4,4,2,3,6,6,1,2,2,5,3,3,5,5,4,5,5).

Выделенный базис с минимальным значением функционала Маклейна = 4 составляют следующие изометрические циклы:

с₁ = {e₁,e₂,e₅}; с₂ = {e₁,e₃,e₈,e₁₈}; с₄ = {e₃,e₄,e₁₅,e₁₆};

с₅ = {e₃,e₄,e₁₈,e₁₉}; с₆ = {e₅,e₆,e₉}; с₇ = {e₆,e₇,e₁₀};

с₈ = {e₆,e₈,e₁₁,e₁₇}; с₁₂ = {e₁₀,e₁₁,e₁₃}; с₁₅ = {e₁₂,e₁₃,e₁₄};

с₁₇ = {e₁₄,e₁₆,e₁₇,e₁₉}.

Вектор циклов по ребрам имеет вид:

P_e = (2,1,3,2,2,3,1,2,1,2,2,1,2,2,1,2,2,2,2).

Здесь местоположение числа в записи характеризует номер ребра. Например, выделенное число 3 характеризует ребро e₆, по которому проходят три цикла

Определяем для выбранного базиса значение функционала Понтрягина-Куратовского как равное 12.

Из базиса последовательно удаляем циклы с соблюдением условия: удаление цикла должно приводить к удалению одного и только одного ребра. С этой целью воспользуемся операцией дифференцирования структурного числа W_b, характеризующего выбранный базис:

FP() = 12; FP() = 6; FP() = 6; FP() = 6; FP() = 6;

FP() = 6; FP() = 6; FP() = 12; FP() = 12; FP() = 12.

Согласно правилу, для удаления выбираем цикл с₄. При удалении цикла с₄ удаляется ребро e₁₅.

Теперь вектор циклов по ребрам имеет вид:

P_e = (2,1,2,1,2,3,1,2,1,2,2,1,2,2,0,1,2,2,2).

Значение функционала Понтрягина-Куратовского не равно нулю, поэтому продолжаем процесс удаления циклов:

FP() = 6; FP() = 6; FP() = 6; FP() = 0; FP() = 0;

FP() = 0; FP() = 6; FP() = 6; FP() = 6.

Рис. 11. Топологический рисунок плоского суграфа.

Согласно правилу, для удаления выбираем цикл с₇. Удаляется ребро e₇.

Вектор циклов по ребрам имеет вид:

P_e = (2,1,2,1,2,2,0,2,1,1,2,1,2,2,0,1,2,2,2).

Остановим процесс удаления циклов тогда, когда значение функционала Понтрягина-Куратовского будет равно нулю: FP() = 0

Выбранное подмножество изометрических циклов характеризует топологический рисунок плоской части графа с удаленными ребрами e₇ и e₁₅ (см. рис. 11):

с₁ = {e₁,e₂,e₅}; с₂ = {e₁,e₃,e₈,e₁₈}; с₅ = {e₃,e₄,e₁₈,e₁₉};

с₆ = {e₅,e₆,e₉}; с₈ = {e₆,e₈,e₁₁,e₁₇}; с₁₂ = {e₁₀,e₁₁,e₁₃};

с₁₅ = {e₁₂,e₁₃,e₁₄}; с₁₇ = {e₁₄,e₁₆,e₁₇,e₁₉};

и ободом c₀ = {e₂,e₄,e₉,e₁₀,e₁₂,e₁₆}.

Применяя алгоритм перехода от циклов к вращению вершин, получаем топологический рисунок плоской части графа (G,):

= {₁ = <v₁₀,v₉,v₂,v₃>, ₂ = <v₁,v₈,v₄,v₃>, ₃ = <v₁,v₂,v₄>, ₄ = <v₂,v₇,v₅,v₃>,

₅ = <v₇,v₆,v₄>, ₆ = <v₇,v₁₀,v₅>, ₇ = <v₄,v₈,v₆,v₅>, ₈ = <v₁₀,v₇,v₂,v₉>, ₉ = <v₈,v₁>,

₁₀ = <v₆,v₈,v₁>}.

Рис. 12. Топологический рисунок непланарного графа.

Построим топологический рисунок графа с минимальным числом пересечений для выделенной части непланарного графа.

Вводим мнимые вершины v₁₁ и v₁₂ соответственно в места пересечение ребер e₇e₁₁ и e₁₅e₁₉. Система изометрических циклов и обод определяют вращение вершин графа:

с₁ = {e₃,e₄,e_15b,e_19b}<v₁,v₉,v₁₁,v₁₀>; с₂ = {e₁,e₂,e₅}<v₁,v₃,v₂>;

с₃ = {e₁,e₃,e₈,e₁₈}<v₁,v₂,v₈,v₉>; с₄ = {e_15b,e₁₈,e_19a}<v₉,v₈,v₁₁>;

с₅ = {e₁₄,e_15a,e₁₆,e_19a}<v₈,v₇,v₆,v₁₁>; с₆ = {e_15a,e₁₆,e_19b}<v₁₁,v₆,v₁₀>;

с₇ = {e₅,e₆,e₉}<v₃,v₄,v₂>; с₈ = {e₆,e_7a,e_11a}<v₂,v₄,v₁₂>;

с₉ = {e_7a,e₈,e_11b,e₁₇}<v₂,v₁₂,v₇,v₈>; с₁₀ = {e_7b,e₁₀,e_11a}<v₄,v₅,v₁₂>;

с₁₁ = {e_7b,e_11b,e₁₃}<v₁₂,v₅,v₇>; с₁₂ = {e₁₂,e₁₃,e₁₄}<v₅,v₆,v₇>;

и обод с₀ = {e₂,e₄,e₉,e₁₀,e₁₂,e₁₆}<v₁,v₁₀,v₆,v₅,v₄,v₃>.

7. Алгоритм выделения плоского планарного суграфа

Теперь можно описать алгоритм выделения плоского планарного суграфа состоящего из изометрических циклов.

шаг 0. [Инициализация]. Производим выделение базиса состоящего из изометрических циклов. Строим вектор количества циклов по ребрам P_e и вектор количества циклов по вершинам P_v.

шаг 1. [Удаление цикла с удалением одного и только одного ребра]. Последовательно удаляем циклы из базиса с соблюдением правила: удаление цикла – удаление одного ребра. Выбираем цикл, максимально изменяющий значение функционала Понтрягина-Куратовского и удаляем его. Если такого цикла нет, то идем на шаг 3.

шаг 2. [Построение векторов]. После удаления цикла строим вектор циклов по ребрам P_e и вектор циклов по вершинам P_v. Определяем значение функционала Понтрягина-Куратовского. Если функционал Понтрягина-Куратовского равен нулю, то конец работы алгоритма. Если значение функционала Понтрягина-Куратовского не равно нулю – идем на шаг 1.

шаг 3. [Определение компонент связности]. Находим ребра, удаление которых максимально изменяет значение функционала Понтрягина-Куратовского. Производим удаление циклов для тех ребер, которые качественно влияют на процесс разбиения по компонентам связности, идем на шаг 1.

Следующим этапом построения плоского суграфа является подключение удаленных в процессе планаризации ребер e₃₇,e₅₀,e₆₄ с целью образования простых циклов (см. рис. 16).

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

Заключение

В данной работе рассмотрен начальный этап визуализации рисунка графа на плоскости. Представлен приближенный алгоритм выделения плоского суграфа непланарного графа с применением методов дискретной оптимизации. Показано место данного алгоритма в процессе построения топологического рисунка непланарного графа. По результатам работы можно сделать следующие выводы:

1. Топологический рисунок графа с помощью вращения вершин позволяет описывать только плоские графы.

2. Для построения топологического рисунка непланарного графа вначале необходимо выделить плоскую часть графа с минимальным количеством удаленных ребер. Затем ввести в выделенную плоскую часть удаленные в процессе планаризации ребра с минимальным количеством пересечений. В места пересечений ввести мнимые вершины. Определить вращение истинных и мнимых вершин.

3. Для выделения плоской части графа применен функционал Понтрягина-Куратовского, нулевое значение которого достигается путем поэтапного удаления циклов из базиса изометрических циклов графа.

4. Показано, что удаление циклов должно производиться по правилам, вытекающим из уравнения Эйлера.

5. Поиск оптимального решения достигается на ограниченном множестве изометрических циклов графа, мощность которого не превосходит card(C_t) n(n-1)(n-2)/6 = m(n-2)/3. Вычислительная сложность алгоритма построения топологического рисунка графа может быть определена как o(m²n²).

Представленный полиномиальный алгоритм позволяет определить систему изометрических циклов, близкую к максимально плоскому суграфу, и автоматически задает вращение вершин графа, характеризующее его топологический рисунок [3].

Список литературы

1. Z.V. Apanovich. Ot risovaniya grafov k vizualizatsii informatsii (From Graph Drawing to Information Visualization), Novosibirsk: Nauka, 2007. – 24 s.

2. G. Di Battista. Algorithms for Drawing Graphs: an Annotated Bibliography / G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis // Comp. Geom., Theory and Appl. – 1994. – N 4. – P. 235–282.

3. R. Tamassia. Handbook of Graph Drawing and Visualization. C&H/CRC – 2013. – 844 p.

4. V. N. Kas'yanov, V. A. Evstigneev. Grafy v programmirovanii: obrabotka, vizualizaciya i primenenie. SPb.: BHV-Peterburg, 2003. – 1104 s.

5. 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.

6. S. V. Kurapov, M. V. Davidovskii. Dva podhoda k provedeniyu soedinenij v ploskih konstruktivah. Komponenty i tekhnologii. 2015. № 7. S. 142–147;

7. S. V. Kurapov, M. V. Davidovskii. Topologicheskij podhod k provedeniyu soedinenij v ploskih konstruktivah. Komponenty i tekhnologii. 2015. № 11. S. 127–130;

8. S. V. Kurapov, M. V. Davidovskii. Proverka planarnosti i postroenie topologicheskogo risunka ploskogo grafa (poiskom v glubinu) // PDM. 2016. №2(32). S.100–115.

9. 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.

10. M. Deza, V. Grishukhin, M. Shtogrin. Scale-Isometric Polytopal Graphs in Hypercubes and Cubic Lattices. Imperial College Press, 2004. – 175 p.

11. G. Ringel. Map Color Theorem. Repr. of the orig. 1st ed. (1974), Springer, 2011. – 212 p.

12. M. Patrignani. Planarity testing and embedding. Chapter 1. Handbook of Graph Drawing and Visualization. Roberto Tamassia, Editor. CRC Press. June 24, 2013. – P.1–42.

13. J. E. Hopcroft, R. E. Tarjan. Isomorphism of Planar Graphs // Complexity of Computer Computations / The IBM Research Symposia Series. – 1972. – P.131–152.

14. S. MacLane. A combinatorial condition for planar graphs // Fund. Math., 28. – 1937. – P. 22–32.

15. A.A Zykov. Teoriya konechnykh grafov (Theory of Finite Graphs). Novosibirsk: Nauka, 1963.

16. M. N. S. Swamy, K. Thulasiraman. Graphs, networks, and algorithms. – J. Wiley & Sons, 1981.

17. Harary, F. Graph Theory, Reading: Addison-Wesley. – 1969.

18. E. Korach, Z. Ostfeld. DFS tree construction: Algorithms and characterizations // In: van Leeuwen J. (eds) Graph-Theoretic Concepts in Computer Science. WG 1988. Lecture Notes in Computer Science. – Vol 344. – Springer, Berlin, Heidelberg. – 1989.

A method for visualizing the drawing of a nonplanar graph

Authors: S.V. Kurapov^1,A, M.V. Davidovsky^2,B, A.V. Tolok^3,C

^A Zaporozhye National University, Ukraine

^B Zaporozhye Institute of Postgraduate Pedagogical Education, Ukraine

^C Moscow State Technological University «STANKIN», Russia

¹ ORCID: 0000-0003-4563-7227, lilili5050@rambler.ru

² ORCID: 0000-0002-9472-3351, m.davidovsky@gmail.com

³ ORCID: 0000-0002-7257-9029, a.tolok@stankin.ru

Abstract

In this paper, we consider the issues related to the representation of a nonplanar graph drawing. We propose a new method for constructing a topological drawing of the flat part of a nonplanar graph. The initial information used for the solution is basically the set of graph isometric cycles, which makes it possible to reduce the solution to discrete optimization methods. The necessary concepts and structures for solving the problem of constructing a non-planar topological graph drawing are considered.

Keywords: graph, rotation of graph vertices, isometric cycles, planarity, flat part of a graph.

References