ПОИСК ШАРНИРОВ В НЕОРИЕНТИРОВАННОМ ГРАФЕ

SEARCHING OF JOINTS IN A NON–ORIENTED GRAPH

Anastasia Vernikovskaya

Student, Department of Intelligent Information Technologies, Belarusian State University of Informatics and Radioelectronics,

Belarus, Minsk

Alisa Tochkar

Student, Department of Intelligent Information Technologies, Belarusian State University of Informatics and Radioelectronics,

Belarus, Minsk

АННОТАЦИЯ

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

ABSTRACT

The article describes the problem of finding a set of vertices, the removal of which leads to an increase in the number of connected components of an undirected graph.

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

Keywords: graph, undirected graph, hinge, connected component.

Задача поиска шарниров в неориентированном графе построена на использовании поиска в глубину [1]. Поиск в глубину – это один из способов обхода графа, которая заключается в том, чтобы постоянно продвигаться вглубь графа, работая рекурсивно (рис. 1) [2].

Рисунок 1. Макет работы поиска в глубину

Некоторые базовые понятия из предметной области теории графов: [4]

Граф (абсолютное понятие) – совокупность непустого множества вершин и множества пар вершин (связей между вершинами), где каждая связь установлена ровно между двумя вершинами (рис. 2) [1].

Рисунок 2. На рисунке изображена формализация понятия граф на языке SCg

Неориентированный граф (абсолютное понятие) – это такой граф, в котором все связки являются ребрами (рис. 3) [1].

Рисунок 3. На рисунке изображена формализация понятия неориентированный граф на языке SCg

Шарнир – вершина, удаление которой вместе с инцидентными ей ребрами приведет к увеличению количества компонент связности графа [1].

Компонента связности – часть графа, для каждой пары вершин которой найдется цепочка ребер от первой вершины ко второй [1].

Алгоритм: Создаем множество вершин всех вершин графа, множество посещенных вершин, множество шарниров, множество удаленных дуг и вершину, называемую удаленной. Формируем множество всех узлов графа, занося все вершины из памяти. Приравниваем удаленной вершине текущую вершину, удаляем текущую вершину, заносим инцидентные ей дуги во множество удаленных дуг и берем следующую вершину. Если текущая вершина не посещена, заносим ее во множество посещенных вершин. Если у текущей вершины есть потомки (имеется в виду смежные вершины), берем такого потомка, который не посещен.Если множество всех вершин графа не совпадает с множеством посещенных вершин, то удаленная вершина является шарниром и мы добавляем ее во множество шарниров. Добавляем удаленную вершину и множество удаленных дуг в исходный граф, берем следующую непроверенную вершину, которая и является искомой [5].

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

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

1. Метасистема IMS [Электронный ресурс]. URL: http://ims.ostis.net/
2. Ф., Харари. Теория графов / Харари Ф. – КомКнига, 2006. – 296 с.
3. В.В. Голенков, О.Е. Елисеева, В.П. Ивашенко и др. Представление и обработка знаний в графодинамических ассоциативных машинах / В.П. Ивашенко и др. В.В. Голенков, О.Е. Елисеева; БГУИР. – 2001. – 12 с.
4. Ф.А., Новиков. Дискретная математика для программистов / Нови–ков Ф.А. – Питер, 2003. – 364 с.
5. О., Оре. Теория графов / Оре О. – Наука, 1980. – 336 с.