Проверка графов на связность

Размещено на http://www.allbest.ru

Проверка графов на связность

Checking graphs for connectivity

И.Д. Винников Научный руководитель - Волков А.А., старший преподаватель Белорусский национальный технический университет, г. Минск, Республика Беларусь

I.Vinnikov Supervisor - A.A. Volkov, Senior Lecturer Belarusian national technical university, Minsk, Belarus

Аннотация

На основе литературных данных рассмотрены понятие графа, его проверка на связность, пример для моей схемы.

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

Abstract

On the basis of literary data the concept of a graph, its connectivity, an example for my scheme.

Keywords: graph, Mengers theorem, edge, vertex.

Введение

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

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

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

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

Основная часть

Для того, чтобы говорить о графах, мы должны ввести само понятие графа:

Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.

Граф G состоит из конечного непустого множества V, содержащего p вершин, и заданного множества X, содержащего q неупорядоченных пар различных вершин из V. Каждую пару x={u,v} вершин в X называют ребром графа G, и говорят, что x соединяет u и v. Мы будем писать x=uv и говорить, что u и v - смежные вершины; вершина u и ребро x инцидентны, так же как v и x. Если два различных ребра x и y инциденты одной и той же вершине, то они называются смежными. Граф с p вершинами и q ребрами называется (p, q)- графом. (1, 0)- граф называется тривиальным.

Обычно граф представляется диаграммой, и ее-то часто называют графом. Таким образом, у графа G на рисунке 1 вершины u и v смежные, а вершины u и w нет. Ребра x и y смежные, а x и z нет.

Рисунок 1 - Схема графа

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

Ориентированный граф, или орграф, D состоит из конечного непустого множества V вершин и заданного набора X упорядоченных пар различных вершин. Элементы из X называются ориентированными ребрами, или дугами. В орграфе нет петель. Направленный граф - это орграф, не имеющий симметричных пар ориентированных ребер.

Число ребер, инцидентных одной вершине называется локальной степенью или просто степенью графа[2].

Приведем определение связности графа.

Связностью x=x(G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Отсюда следует, что связность несвязного графа равна 0, а связность связного графа, имеющего точку сочленения, равна 1. Полный Граф (Kp) нельзя сделать несвязным, сколько бы вершин из него ни удалять, а тривиальный граф получается из Kp после удаления p-1 вершин. Поэтому x(Kp) = p-1. Иногда x называют вершинной связностью.

По такому принципу определяется реберная связность л=л(G) графа G определяется как наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу. Очевидно, что реберная связность несвязного графа равна 0, а реберная связность связного графа, имеющего мост (ребро, при удалении которого граф G становится несвязным), равна 1. Связность, реберная связность и наименьшая степень графа связаны неравенством, найденным Уитни[3].

Теорема 1. Для любого графа G:

x(G)? л(G)? д(G) (1)

Задача определения наибольшей связности, возможной для графа с данным числом вершин и данным числом ребер, была поставлена Бержем и решена Харари.

Теорема 2. Среди всех графов с p вершинами, д(G)?p/2 и q ребрами наибольшая связность равна нулю если q<P-1, и равна (2q/p), если q?p-1[3].

Следствие 2. Наибольшая реберная связность (p, q)- графа равна его наибольшей связности.

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

Пусть u и v - две различные вершины связного графа G. Две простые цепи, соединяющие u и v, называются непересекающимися, если у них нет общих вершин, отличных от u и v и реберно-пересекающимися, если у них нет общих ребер. Множество S вершин, ребер или вершин и ребер разделяет u и v, если u и v принадлежат различным компонентам графа G-S. Теорема Менгера первоначально была сформулирована в “вершинной форме”.

Теорема 3. Наименьшее число вершин, разделяющих две несмежные вершины s и t, равно наибольшему числу непересекающихся простых (s-t)-цепей [3].

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

Теорема 4. Граф n-связен тогда и только тогда, когда любая пара его вершин соединена по крайней мере n вершинно-непересекающимися цепями[3].

Связь между теоремами 3 и 4 легко заметить, если ввести понятие локальной связности. Локальной связностью x(u, v) двух несмежных вершин u и v графа G называется наименьшее число вершин, удаление которых разделяет u и v. Используя введенное понятие, теорему Менгера можно сформулировать так: для любых двух выделенных несмежных вершин u и v справедливо равенство

x(u, v) = µo(u, v), (2)

где µo(u, v) - наибольшее число вершинно-непересекающихся цепей, соединяющих u и v. Для неполных графов выражение (2) будет записано в другой форме:

?(u, v)= min ?(u, v), (3)

min ?(u, v) - минимум, который берется по всем парам несмежных вершин u и v.

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

Различие между теоремами 3 и 4 заключается в том, что в теореме 3 рассматриваются две выделенные вершины, а в теореме 4 всевозможные пары несмежных вершин. Это различие, так же как и очевидное различие между теоремами 3 и 5, представлено в таблице 1.

Таблица 1 - Различия между теоремами 3, 4, 5

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

Рисунок 2 - Схема для проверки связности

Сначала проверим наш граф по теореме 1. Для этого найдем связность графа(?), реберную связность(л) и наименьшую степень графа(д). Для моей схемы: ? = 2 (для создания несвязного графа достаточно удалить 2 вершины, процесс нахождения показан на рисунке 3а), л = 2 (для создания несвязного графа достаточно удалить 2 ребра, процесс нахождения показан на рисунке 3б), д = 2 (минимальное число ребер инцидентных одной вершине равно 2, процесс нахождения показан на рисунке 3в). Подставляем эти значения в выражение (1): 2?2?2 .Получаем, что теорема 1 выполняется для схемы.

Рисунок 3 - Нахождение ?, л, д

Проверку теоремы 2 для нашего графа осуществить нельзя, т.к. не выполняется условие д(G)?p/2.

Далее сделаем проверку графа по теореме 3. Для примера возьмем две несмежные вершины: А и Д. Наибольшее число непересекающихся цепей (А, Д) (А>Б>Д, А>В>Д, А>БУ>Д) равно 3 (рисунок 4), следовательно, наименьшее число вершин, разделяющих две несмежные вершины А и Д тоже равно 3.

Рисунок 4 - Нахождение наибольшего числа непересекающихся цепей

Для 4 теоремы нужно найти min ?(u, v). Возьмем произвольные несмежные вершины u=Е, v=А. Определим min ?(u, v): u=Е>БУ>А, Е>Д>В>А (рисунок 5). Существует всего два непересекающихся путей, поэтому степень d(u)=2. Следуя теореме 4, сделаем вывод, что граф, указанный на рисунке 2, является 2-связным, т.е. ?(u, v)= min ?(u, v)=2.

Рисунок 5 Определение min ?(u, v)

Теорема 5: из рисунка 2 видно, что вершины А и Д можно разделить, удалив 3 ребра, и что наибольшее число непересекающихся по ребрам (А, Д) путей будет 3. Из вершины А выходит 3 ребра Е1 (Б, В, БУ). В вершину Д заходят тоже 3 ребра Е2 (Б, В, БУ). Между вершинами А и Д существуют следующие реберно-независимые пути, включающие ребра множества Е1, в качестве начальных и ребра множества Е2 в качестве конечных. 1 путь: А-Б>Б-Д; 2 путь: А-В>ВД; 3 путь: А-БУ>БУ-Д (рисунок 6). В 3 пути ребро БУ-Д можно заменить ребрами БУ-Е>Е-Д. т.е. между множествами Е1 и Е2 существует более 3 реберно-независимых путей, значит наименьшее число рёбер, которые определяют число реберно-непересекающихся путей в этом случае определяется минимальной степенью вершин А и Д. В нашем случае они равны 3, поэтому вершины А и Д можно разделить, удалив 3 ребра и наибольшее количество непересекающихся по ребрам (А - Д ) путей тоже равно 3, что доказывает правильность теоремы 5.

Рисунок 6 - Нахождение наибольшего числа непересекающихся по ребрам (А, Д) путей

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

Рисунок 7 - Пример несвязного графа

граф связность цепь

По теореме 1 найдем ?, л, д. Связность графа равна 0, реберная связность тоже равна 0, а наименьшую степень графа равна 1. Подставляем в выражение (1): 0?0?1. По нулевым значениям вершинной и реберной связности можно сделать вывод, что граф несвязен.

Проверка теоремы 2 для графа не осуществима, потому что условие д(G)?p/2 не выполняется.

Для теоремы 3 возьмем две несмежные вершины: А и Д. Наибольшее число непересекающихся цепей(А, Д) равно 0, наименьшее число вершин, разделяющих вершины А и Д тоже равно 0, значит граф несвязен.

Для теоремы 4 и 5 выполняются аналогичные действия, как и в теореме 3.

Заключение

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

При этом можно использовать любую из приведенных теорем.

Литература

1. Гурский, С.К. Алгоритмизация задач управления режимами сложных систем в электроэнергетике ; под ред. Г.Е. Поспелова. - Минск: наука и техника, 1977. - 367 с. :ил.

2. Основные понятия теории графов [Электронный ресурс]/ Основные понятия теории графов.-Режим доступа: http://www.math.mrsu.ru/text/courses/method/osn_pon_teor_graph.htm. Дата доступа: 17.12.2021.

3. Харари, Ф. Теория графов / Пер. с англ. И предисл. В.П. Козырева. Под редакцией Г.П. Гаврилова. / Ф. Харари. - Изд. 2-е. - М.: Едиториал УРСС, 2003. -296 с.

Размещено на Allbest.ru