Теория графов: основные понятия и определения

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

Первой работой теории графов как математической дисциплины считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кёнингсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.

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

Графы служат удобным средством описания связей между объектами. Ранее мы уже использовали графы как способ наглядного представления конечных бинарных отношений. Но граф используют отнюдь не только как иллюстрацию. Например, рассматривая граф, изображающий сеть дорог между населенными пунктами, можно определить маршрут проезда от пункта А до пункта Б. Если таких маршрутов окажется несколько, хотелось бы выбрать в определенном смысле оптимальный, например самый короткий или самый безопасный. Для решения задачи выбора требуется проводить определенные вычисления над графами. При решении подобных задач удобно использовать алгебраическую технику, да и само понятие графа необходимо формализовать.

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

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

Графы, как уже отмечалось в примерах, есть способ "визуализации" связей между определенными объектами. Связи эти могут быть "направленными", как, например, в генеалогическом древе, или "ненаправленными" (сеть дорог с двусторонним движением). В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные (или направленные) и неориентированные.

Построение математического определения графа осуществляется путем формализации и "объектов", и "связей" как элементов некоторых (как правило, конечных) множеств.

Неориентированные графы

Неориентированный граф , где считаем, что , то говорят, что ребро .

Вершины , называют смежными, а также концами ребра . Если всех инцидентных ей ребер.

Для вершины называют множеством смежных с .

Цепь в неориентированном графе , такая, что для любого существует. (Под конечной последовательностью понимается кортеж вершин.)

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

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

Ориентированные графы

Ориентированный граф , где , элементы которого называют дугами.

Если дуга , то говорят, что дуга .

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

Для вершины называют множеством преемников вершины — множеством предшественников вершины

Путь в ориентированном графе , такая, что для любого существует.

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

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

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

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

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

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

Пример 5.1. Рассмотрим неориентированный граф, изображенный на рис. 5.2. Он задается множеством вершин

и множеством неупорядоченных пар .

В этом графе последовательность вершин есть простая цепь, а последовательность — цепь, не являющаяся простои, поскольку в ней есть совпадающие ребра. Последовательность вершин не является цепью, поскольку в графе нет ребра . Последовательность есть цикл, а последовательность — цепь с совпадающими концами, но не цикл, поскольку эта цепь не является простой. Эта цепь не будет и замкнутой, так как в ней есть повторяющееся ребро .

Степени вершин графа следующие:

Вершины попарно достижимы и образуют класс эквивалентности по отношению достижимости. Для вершин и имеет место , и они также образуют класс эквивалентности. Заметим, что вершина V7, по определению, образует цепь длины 0 и эквивалентна по отношению достижимости только самой себе.

Пример 5.2. Обратимся к ориентированному графу, изображенному на рис. 5.3. Он задается множеством вершин и множеством дуг

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

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

Полустепени захода, полустепени исхода и степени у вершин следующие:

Свойства отношения достижимости в графах

Отношение достижимости в неориентированных и ориентированных графах обладает следующим важным свойством.

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

Пусть вершины . Если цепь простая, то доказывать нечего. Пусть существует внутренняя (не совпадающая ни с одним из концов) вершина , которая повторяется в этой цепи, т.е. . Это значит, что вершина ) с совпадающими концами (рис. 5.5). Удалим все вершины и ребра цепи , соединяющую вершины . Если цепь простая, то утверждение доказано. В противном случае поступаем с ней так же, как и с цепью . В силу конечности множества вершин и ребер графа после конечного числа шагов получим простую цепь, соединяющую вершины Следствие 5.1. Если вершина неориентированного графа содержится в некоторой замкнутой цепи, то она содержится и в некотором цикле. Если вершина ориентированного графа содержится в некотором замкнутом пути, то она содержится и в некотором контуре.

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

Подграфы неориентированных и ориентированных графов

Перейдем теперь к понятию подграфа. Формулируется это понятие одновременно для неориентированных и ориентированных графов (с учетом различий в терминологии).

Определение 5.1. Неориентированный (ориентированный) граф называют подграфом неориентированного (ориентированного) графа , если и .

Будем использовать обозначение , аналогичное обозначению включения для множеств.

Замечание 5.4. Так как в определении 5.1 пара есть неориентированный (ориентированный) граф, то для любого ребра (дуги ) предполагается, конечно, что , поскольку иначе пару нельзя будет считать неориентированным (ориентированным) графом.

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

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

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

Например, на рис. 5.7 подграфы являются максимальными ациклическими подграфами графа

Связность и компонента связности графов

Следующее важное понятие снова введем параллельно для рассматриваемых двух видов графов.

Неориентированный граф называют связным, если любые две его вершины .

Компонента связности (или просто компонента) неориентированного графа — это его максимальный связный подграф.

Ориентированный граф называют связным, если для любых двух его вершин вершина

Пример 5.3. Граф, изображенный на рис. 5.2, не является связным. Он состоит из трех компонент. Эти компоненты порождены тремя классами эквивалентности по отношению достижимости, указанными в примере 5.1.

Связными являются все графы, изображенные на рис. 5.7.

Ориентированный граф на рис. 5.8 связный, а ориентированные графы на рис. 5.3 и 5.9 не являются связными. В ориентированном графе на рис. 5.3 вершины и не достижимы одна из другой, а в ориентированном графе на рис. 5.9 взаимно не достижимы, например, вершины и . В ориентированном графе, изображенном на рис. 5.9, имеются две компоненты связности: и , которые пересекаются.

Сильная и слабая связности графов

Для ориентированного графа можно определить также понятия сильной и слабой связности.

Определение 5.2. Ориентированный граф называют сильно связным, если для любых двух его вершин Пример 5.4. а. В ориентированном графе, изображенном на рис. 5.3, бикомпонентой является подграф , порожденный множеством вершин . Действительно, эти вершины взаимно достижимы, поэтому ориентированный граф сильно связный. Так как из вершин ни одна из вершин не достижима, то выделенный сильно связный подграф является максимальным.

б. В ориентированном графе, представленном на рис. 5.9, имеются четыре бикомпоненты и . Это подграфы, порожденные соответственно множествами вершин и . Отметим, что подграф, порожденный множеством , не содержит ни одной дуги. Тем не менее этот подграф — бикомпонента, поскольку каждая вершина достижима сама из себя (по пути длины 0).

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

Таким образом, переход от ориентированного графа к ассоциированному с ним неориентированному графу состоит в "стирании" ориентации дуг ориентированного графа с учетом того, что все петли исчезают, а дуги и при переходят в одно и то же ребро .

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

Определение 5.4. Ориентированный граф называют слабо связным, если ассоциированный с ним неориентированный граф связный. Компонентой слабой связности (слабой компонентой) ориентированного графа называют его максимальный слабо связный подграф.

Ориентированные графы, представленные на рис. 5.3, 5.9 и 5.8, являются слабо связными. Ориентированный граф, изображенный на рис. 5.10, не является слабо связным, поскольку не является связным ассоциированный с ним неориентированный граф. Ориентированный граф на рис. 5.10,а имеет две компоненты слабой связности. Соответственно ассоциированный с ним неориентированный граф на рис. 5.10,б имеет две компоненты связности.