На первом занятии, вводя понятие графа, мы рассма­тривали в качестве примера состязания спортивных команд. Мы. соединяли две команды, скажем А и С, ребром АС в том случае, когда эти команды уже играли друг с другом. Однако такой граф не дает ответа на один весьма существен­ный вопрос: кто именно выиграл игру?
Этот недостаток легко может быть устранен. Если команда А выиграла у С, условимся ставить на ребре АС стрелку, направленную от А к С. Предположим, что нам известны результаты всех уже сыгранных игр, и добавим к графу рис. 1 соответствующие стрелки; пусть при этом получится граф, изображенный на рис. 58.

Рис 58.

На этом графе показано, что команда А выиграла у С, команда F проиграла А, а В вы­играла все игры - с С, Е, F и т. д.

Ребро графа называется ориентированным , если одну вершину считают началом ребра , а другую - концом .
Граф, все ребра которого ориентированы, называется ориенти рованным графом .
Одна и та же вершина ориентированного графа может служить началом для одних ребер и концом для других. Соответственно различают две степени вершины: степень выхода и степень входа.
Степенью выхода вершины А ориентированного графа называется число выходящих из А ребер (обозначение: d+(A)).
Степенью входа вершины А ориентированного графа называ­ется число входящих в А ребер (обозначение: d-(A)).
А что, если какая-то игра окончилась вничью? Мы можем отразить ничейные результаты на графе, оставляя соответствующие ребра неориентирован­ными. При этом мы получим так называемый сме шанный граф , на котором имеются как ориенти­рованные, так и неориентированные ребра.
Путем в ориентированном графе G от А1 до Аn называется по­следовательность ориентированных ребер <А1; А2>, <А2; А3>, ..., <Аn-1; Аn>, такая, что конец каждого предыдущего ребра совпадает с началом следующего и ни одно ребро не встречается более одного раза.

Рис. 59
Если в ориентированном графе G нашелся путь от А до В, то обратного пути от В к А может и не быть (рис. 59).
Если существует ориентированный путь от А до В, то говорят, что В достижи­ ма из А,
В графе G на рисунке 38 В достижима
из А, А не достижима из В.
Простым путем в ориентированном гра­фе называется путь, в котором ни одна вершина не содержится более одного раза. Замкнутый путь в ориентированном графе называется ориентированным циклом.
Длиной пути называется число ребер в этом пути.
Расстоянием от А до В в ориентированном графе называется длина наикратчайшего пути от А до В. Если пути от А до В не существует, то расстояние от А до В называют бесконечным и обо­значают?. Расстояние от А до В будем обозначать S (АВ). Для графа на рисунке 38
S (АВ) = 1, S (СВ) - 2, S (ВС) = ?.
Задача 9.1.
В приморском курортном городе после установления одностороннего движения оказалось, что число улиц, по которым можно въехать на каждый перекресток, равно числу улиц, по которым можно из него выехать. Докажите, что можно предложить такой маршрут патрулирования, который начинается и оканчивается в одном месте и проходит через каждый участок улиц ровно один раз.
Решение.
Построим орграф G, задающий движение в городе.
Орграф называется связным, если от любой его вершины до любой другой можно перейти по дугам без учета их ориентации. Связный орг­раф называется эйлеровым, если в нем есть эйлеров цикл.
Теорема 12. Связный орграф является эйлеровым тогда и только тогда, когда для каждой его вершины v выполняется равенство d - (v ) = d + (v ) .
Теорема доказывается точно так же, как и теорема в задаче 4.2.
Из условия задачи следует, что для вершин построенного графа G выполняется равенство d-(v) = d+(v). Следовательно, граф G эйлеров, и эйлеров цикл определит нужный маршрут патрулирования.
Задача 9.2.
На плоскости отмечено конечное число точек. Некоторые пары то­чек являются началами и концами векторов, причем число векторов, входящих в любую точку равно числу векторов, выходящих из нее. Найдите сумму векторов.
Решение.
Точки плоскости вместе с векторами образуют орграф G.Цикл орграфа, все вершины которого различные, называется контуром.
Теорема 13. Связный орграф G эйлеров тогда и только тогда, когда G является объединением контуров, попарно не имеющих общих ребер.
Доказательство. Необходимость.Пусть G - эйлеров орграф. Рассмотрим его любую вершину u1. Выйдем из вершины u1по некоторой дуге (u1, u2).Это возможно сделать, так как орграф Gсвязный. Поскольку d-(u2) = d+(u2), то из вершины u2можно выйти по дуге (u2, u3). Орграф Gимеет конечное число вершин, поэтому, в конце концов, мы попадем в не­которую вершину w, в которой были раньше. Часть цепи, которая начинается и оканчивается в вершине w, является контуром С1. Удалим дуги кон­тура С1 из орграфа G. В получившемся орграфе G1(возможно несвязном) степени входа и выхода вершин, принадлежавших С, уменьшились на единицу, степени входа и выхода остальных вершин не изменились. Следовательно, для любой вер­шины v орграфа С1 будет выполняться равенство d-(v) = d+(v). Поэтому в орграфе G1 можно выделить контур C2 и т.д.
Достаточность доказывается путем объединения контуров в эй­леров цикл (см. доказательство теоремы в задаче 4.2).
Теорема доказана. Возможно, орграф G, задающий векторы в нашей задаче, не явля­ется связным. Применив доказанную теорему к каждой связной части орграфа, получим разбиение векторов на контуры. Сумма векторов, при­надлежащих одному контуру, равна нулю. Следовательно, сумма всех векторов равна нулю.

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

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

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

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

Это по сути граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними – ребрами. Заменив компьютеры вершинами, мы получим математический объект – граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке. Стоит отметить, что в данном примере не используется ни одной петли, то есть такого ребра, которое выходит из вершины и сразу же входит в нее, но петли могут встречаться в задачах.

Вот некоторые важные обозначения, используемые в теории графов:

• G=(V, E), здесь G – граф, V – его вершины, а E – ребра;
• |V| – порядок (число вершин);
• |E| – размер графа (число рёбер).

В нашем случае (рис. 1) |V|=5, |E|=10;

Когда из любой вершины доступна любая другая вершина, то такой граф называется неориентированным связным графом (рис. 1). Если же граф связный, но это условие не выполняется, тогда такой граф называется ориентированным или орграфом (рис. 2).

В ориентированных и неориентированных графах имеется понятие степени вершины. Степень вершины – это количество ребер, соединяющих ее с другими вершинами. Сумма всех степеней графа равна удвоенному количеству всех его ребер. Для рисунка 2 сумма всех степеней равна 20.

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

Ориентированные графы имеют следующую форму записи:

G=(V, A), где V – вершины, A – направленные ребра.

Третий тип графов – смешанные графы (рис. 3). Они имеют как направленные ребра, так и ненаправленные. Формально смешанный граф записывается так: G=(V, E, A), где каждая из букв в скобках обозначает тоже, что ей приписывалось ранее.

В графе на рисунке 3 одни дуги направленные [(e, a), (e, c), (a, b), (c, a), (d, b)], другие – ненаправленные [(e, d), (e, b), (d, c)…].

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

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

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

В любом из рассмотренных нами графов имеется возможность выделить путь и, причем не один. Путь – это последовательность вершин, каждая из которых соединена с последующей посредством ребра. Если первая и последняя вершины совпадают, то такой путь называется циклом. Длина пути определяется количеством составляющих его ребер. Например, на рисунке 4.а путем служит последовательность [(e), (a), (b), (c)]. Этот путь является подграфом, так как к нему применимо определение последнего, а именно: граф G’=(V’, E’) является подграфом графа G=(V, E), только тогда когда V’ и E’ принадлежат V, E.

Виды графов могут определяться общими принципами их построения (таковы, например, двудольный граф и эйлеров граф), а могут зависеть от тех или иных свойств вершин или рёбер (например, ориентированный и неориентированный граф, обыкновенный граф).

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

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

Графы, в которых все рёбра являются дугами (порядок двух концов ребра графа существенен), называются ориентированными графами или орграфами .

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

Графы с петлями, смешанные графы, пустые графы, мультиграфы, обыкновенные графы, полные графы

Если граф содержит петли , то это обстоятельство специально оговаривают, добавляя к основной харатеристике графа слова "с петлями", например, "орграф с петлями". Если граф не содержит петель, то добавляют слова "без петель".

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

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

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

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

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

Двудольный граф

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

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

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

Эйлеров граф

Мы уже касались задачи о кёнигсбергских мостах . Отрицательное решение Эйлером этой задачи привело к первой опубликованной работе по теории графов. Задачу об обходе мостов можно обобщить и получить следующую задачу теории графов: можно ли найти в данной графе цикл, содержащий все вершины и все рёбра? Граф, в котором это возможно, называется эйлеровым графом.

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

Пример 2. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом? Объяснить ответ. Привести примеры.

Ответ. Если n - нечётное число, то каждая вершина инцидентна n -1 рёбрам. В таком случае данный граф является эйлеровым графом. Примеры таких графов на рисунке ниже.

Регулярный граф

Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k . Таким образом, на рисунке к примеру 2 изображены примеры регулярных графов, называемых по степени его вершин 4-регулярными и 2-регулярными графами или регулярными графами 4-й степени и 2-й степени.

Число вершин регулярного графа k -й степени не может быть меньше k +1. У регулярного графа нечётной степени может быть лишь чётное число вершин.

Пример 3. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.

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

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

Гамильтонов граф

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

Пример 4. Задан двудольный граф, в котором n - число вершин из множества A , а m - число вершин из множества B . В каком случае граф будет эйлеровым графом, а в каком случае - гамильтоновым графом?

В предыдущих главах мы представили некоторые основные результаты теории неориентированных графов. Однако для описания некоторых ситуаций неориентированных графов недостаточно. Например, при представлении схемы уличного движения графом, ребра которого соответствуют улицам, для указания допустимого направления движения ребрам необходимо присваивать ориентацию. Другим примером является программа для ЭВМ, моделируемая графом, ребра которого представляют поток управления от одних множеств инструкций к другим. В таком представлении программы для указания направления потока управления ребрам также необходимо присвоить ориентацию. Еще одним примером физической системы, для представления которой требуется ориентированный граф, является электрическая цепь. Применения ориентированных графов и соответствующие алгоритмы рассматриваются в гл. 11-15.

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

5.1. Основные определения и понятия

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

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

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

В графическом представлении ориентированного графа вершины изображаются точками или кружками, а ребра (дуги) - отрезками

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

Например, если такие, что Их), ориентированный граф можно представить рис. 5.1. В этом графе - параллельные дуги, а - петля.

Рис. 5.1. Ориентированный граф.

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

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

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

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

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

Теорема 5.1. В ориентированном графе с дугами

Сумма полустепеней захода=Сумма полустепеней исхода=m.

Подграфы и порожденные подграфы ориентированного графа определяются так же, как и в случае неориентированных графов (разд. 1.2).

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

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

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

Ориентированный маршрут называется открытым, если его концевые вершины различны, в противном случае - замкнутым.

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

Открытая ориентированная цепь называется ориентированным путем, если различны все ее вершины.

Замкнутая ориентированная цепь называется ориентированным циклом или контуром, если ее вершины, за исключением концевых, различны.

Говорят, что ориентированный граф ациклический или бесконтурный, если он не имеет контуров. Например, ациклическим является ориентированный граф на рис. 5.2.

Рис. 5.2. Ациклический ориентированный граф.

Рис. 5.3. Сильно связный ориентированный граф.

Последовательность вершин ориентированного графа G называется маршрутом в G, если она является маршрутом лежащего в основе неориентированного графа Например, последовательность в графе на рис. 5.2 является маршрутом, но не ориентированным.

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

Ориентированный граф называется связным, если связным является лежащий в его основе неориентированный граф.

Подграф ориентированного графа G называется компонентой графа G, если он является компонентой графа

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

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

Ориентированный граф называется сильно связным, если сильно связны все его вершины. Например, сильно связным является граф на рис. 5.3.

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

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

Рис. 5.4. Граф и его конденсация.

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

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

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

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

Граф, получающийся в результате стягивания всех дуг сильно связных компонент ориентированного графа G, называется конденсированным графом графа G. Конденсация графа, приведенного на рис. 5.4, а, представлена на рис. 5.4, б.

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

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

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

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

Рис. 5.5. Минимально связный ориентированный граф.

Минимально связным является, например, граф, представленный на рис. 5.5.

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

Мы знаем, что неориентированный граф минимально связен тогда и только тогда, когда он является деревом (упр. 2.13). По теореме 2.5 дерево имеет не менее двух вершин степени 1. Следовательно, минимально связные неориентированные графы имеют по крайней мере две вершины степени 1.

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

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

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

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

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

Например, при сложной оценке образцов (в геологии, например) направление ребра указывает предпочтение. В нормальной системе предпочтений не должно быть циклов

Таня Наташа

чтобы всегда можно было сделать выбор, иначе необходимо пересмотреть систему предпочтений.

Одностороннее движение.

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

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

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

Ясно, что каждый такой граф должен быть связным, однако этого недостаточно.

Ребро Е = (А,В) будем называть связывающим ребром , или перешейком , если оно является единственным путем от А к В (или обратно).

Свюзывающее ребро делит все вершины графа на два множества: те, в которые можно прийти из А, не проходя по ребру Е, и те, в которые можно прийти из В, не проходя по Е. Граф в этом случае состоит из двух частей G 1 и G 2 соединенных только ребром Е (рис. a и a+1).

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

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

рис.2 Связывающее рис. 2+1 Конечное (связывающее) рис.2+2 Циклическое

Ребро ребро

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

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

Мы можем доказать эту теорему, указав спосмоб соответствующего ориентирования графа. Выберем в G произвольное ребро Е = (А,В) . Если Е - связывающее ребро, оно останется двухсторонним, и тогда можно будет перейти от А к В и обратно (рис.2+3).

рис.2+3 рис. 2+4

Если Е - циклическое ребро, то оно входит в некоторый цикл С, на котором можно установить циклическую ориентацию (рис.2+4).

Предположим, что мы уже ориентировали некоторую часть Н графа G , так, что из любой вершины графа Н можно пройти в любую другую его вершину с соблюдением правил одностороннего движения. Так как граф G является связным, то либо Н совпадает со всем графом G, либо найдется ребро Е= (А,В), которое не принадлежит Н , но одна из его вершин, скажем А , принадлежит Н .

Если Е - связывающее ребро АВ , то оно останется двухсторонним. Тогда для любой вершины X графа Н можно найти ориентированную цепь R , соединяющую Х с А , а значит (через ребро Е ) , и с В . Обратно от вершины В через ребро Е можно перейти к А , а затем - по ориентировочной цепи Z - от А к Х (рис a+5). Присоединяя Е к H , мы получим уже большую часть графа G , обладающую требуемым свойствам. Если же ребро Е= (А,В) является циклическим, оно принадлежит некоторому циклу С . Мы установили направление на С от А до В и далее вдоль С до первой вершины D из С , принадлежащей Н (рис. a+6).

рис. a+5 рис. a+6

Все эти ребра присоединим к Н . Пусть Х - произвольная вершина из Н , а У - любая вершина из С ; можно найти ориентированную цепь R , принадлежащую Н и соединяющую Х с А , а затем вдоль С пройти к вершине У из С . Обратно, от У можно пройти вдоль С к вершине D , а от нее - принадлежащей Н ориентированной цепью Z - от D к Х . Поэтому ориентированный граф, полученный добавлением к Н указанных ребер цикла С , также удовлетворяет требуемым условиям. Продолжая этот процесс, мы в конце концов ориентируем требуемым образом исходный граф G .

Степени вершин.

Для ориентированных графов мы имеем в каждой вершине число р(А) выходящих и число р * (А) входящих ребер. Общее число ребер равно:

N = р(А 1) + р(А 2) +... + р(А n) = p * (A 1)+p * (A 2)+...+p * (A n)

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

р(А) = р * (А) = r

Упражнение

Постройте однородные ориентированные графы степени r = 2 с числом вершин n = 2,6,7,8.

ОТНОШЕНИЯ.

Отношения и графы.

Всякая математическая система имеет дело с множеством каких-то объектов, или элементов. (Приметы: алгебра, геометрия)

Для того чтобы построить математическую теорию, нам нужны не только сами эти элементы, но также и отношения между ними. (Примеры: для чисел а > в; в геометрии -равенство треугольников, // прямых; в теории множеств - равенство и включения множеств.)

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

Введем общее определение бинарного отношения R: аRв - в находится в отношении R к а.

Например, отношение а > в означает, что в принадлежит множеству всех чисел, меньших а

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

Специальные условия.

Пусть дано некоторое отношение R. Если элемент а находится в отношении R сам с собой, то ему соответствует петля в графе

Отношение R, для которого условие аRв выполняется при любом а , называется рефлексивным .

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

Для каждого отношения R можно определить обратное отношение R * , считая, что аR * в тогда и только тогда, когда аRв.

Из определения обратного отношения видно, что если на графе G, соответствующем R, имеется ребро (а,в), то на графе G * , соответствующем R * , должно быть ребро (в,а). Иными словами, граф G * обратным для G, т.е. графом с теми же ребрами, что и G, но противоположно ориентированными.

Отношение называется симметрическим , если из аRв следует вRа.

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

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

Отношение R транзитивно , если из двух условий аRв и вRс следует, что аRc.

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

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

Отношения эквивалентности.

Отношение эквивалентности, обычно обозначаемое символом ~ , характеризуется следующими тремя свойствами:

1). Рефлексивностью: а ~ а;

2). Симметричностью: из а ~ в Þ в ~ а;

3). Транзитивностью: из а ~ в и в ~ с Þ а ~ с.

Фактически отношение эквивалентности - обобщение свойства равенства.

Отношение эквивалентности вводит в множестве вершин разбиение на непересекающиеся классы эквивалентности .

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

Частичная упорядоченность.

Отношение частичной упорядоченности - это (на примере множеств):

1). Рефлексивность: А Ê А

2). Транзитивность: если А Ê В и В Ê С Þ А Ê С

3). Тождественность: если А Ê В и В Ê АÞ А = В

Отношения строгого включения -

1). Антирефлексивность: А ÉА никогда не имеет места;

2). Транзитивность: если А É В и В É С, то А É С

Отношение упорядоченности (в строгом смысле) называется строгая упорядоченность, а>в, для которой в дополнение к предыдущим условиям выполнено также следующее:

Условие полноты. Для любых двух несовпадающих элементов в и а всегда выполнено одно из двух соотношений а>в или в>а.

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

ПЛОСКИЕ ГРАФЫ.

Условия для плоских графов.

Граф Куратовского К 3,3

Граф задача о трех домах и трех колодцах

Граф Куратовского К 5

Эти два графа - НЕ ПЛОСКИЕ!

Расширение графа - на некоторые ребра поставили новые вершины, так что эти ребра

стали элементарными цепями, состоящими из нескольких ребер.

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

Теорема Куратовсого

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

ФОРМУЛА ЭЙЛЕРА

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

Из определения многоугольных графов следует, что они связны. Потребуем также, чтобы ни один многоугольник не лежал внутри другого. Граничные ребра каждого такого многоугольника образуют цикл, иногда называемый минимальным циклом . Часть плоскости, заключенная внутри многоугольника, называется гранью графа . На графе имеется и максимальный цикл С 1 , окружающий весь граф со всеми его гранями. Будем рассматривать часть плоскости, лежащую вне С 1 , тоже как грань графа с границей С 1 - бесконечная грань F ¥ .

Обозначим через

число вершин, ребер и граней пространственного многоугольника. .

Теорема Эйлера

в - р + г = 2

Доказательство: Формула очевидна для многоугольника, имеющего n ребер. Действительно, n вершин и n ребер, а также две грани F 1 F ¥

Добавим новую грань к графу с г гранями, проводя по грани F ¥ некоторую элементарную цепь, соединяющую две вершины максимальног графа G. Если эта дуга имеет г ребер, то нам придется бобавить г - 1 новую вершину и одну новую грань. Но тогда

в’ - р’ + г’ = (в + г - 1) - (р + г) + (г + 1) = в - р + г (=2!)

по предположению индукции.

Матричные представления.

1. Матрица инциденций А.

а). Для неориентированного графа матрица инциденций представляет собой матрицу, строки которой соответствуют вершинам, а столбцы - ребрам. Элемент матрицы равен 1, если вершина инцидентна ребру. В противном случае элемент матрицы принимает значение 0.

б). Для ориентированного графа элемент матрицы инциденций равен +1, когда вершина, инцидентная дуге, является начальной вершиной дуги (т.е. дуга исходит из этой вершины). Элемент равен -1, когда дуга входит в вершину. Если вершина не инцидентна дуге, то элемент матрицы равен 0.

2. Матрица циклов С.

а). Для неориентированного графа строки матрицы циклов соответствуют простым циклам графа, а столбцы - его ребрам. Элемент матрицы a ij =1, если цикл С i содержит ребро e j . В противном случае a ij =0.

б). Для ориентированного графа a ij =1, -1 или 0 в зависимости от того, одинакова или противоположна ориентация цикла С i и дуги e j или же данный цикл вообще не содержит дуги e j .

3. Матрица смежности вершин (или просто матрица смежности) V представляет собой матрицу, строки и столбцы которой соответствуют вершинам, а элемент матрицы a ij в случае неориентированного графа равен числу ребер, соединяющих вершины i и j. Для ориентированного графа элемент a ij равен числу ребер, направленных от вершины i к вершине j.

Оновные теоремы, связанные с матричными представлениями графов.

1).Ранг (максимальное число линейно-независимых столбцов) матрицы инциденций А связного графа (ориентированного и неориентированного) с n вершинами равен (n-1).

2). Ранг матрицы циклов С связного графа с m ребрами и n вершинами равен (m-n+1).

Пример использования матрицы смежности.

Следующее отображение показывает, что графы G 1 и G 2 изоморфны

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

A 2 =PA 1 P", где

Р = , или p ij =d p(i),j (символ Кронекера)

и Р" - транспонированная матрица.

Нахождение матрицы Р может быть нелегким делом.

Изоморфность G 1 и G 2 означает, что А 1 и А 2 имеют одинаковые собственные значения. Однако это условие не является достаточным (пример внизу).