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

      БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

      Механико-Математический ФАКУЛЬТЕТ 

      КАФЕДРА уравнений математической физики 
 
 
 
 
 
 
 
 

Теория  графов. ориентированные  графы  

      КУРСОВАЯ  РАБОТА 
 
 
 
 
 
 
 
 

              студентки 3 курса отделения математической электроники  
               

      Научный руководитель –

      профессор В.А. Емеличев 
 
 
 
 
 
 
 
 
 
 
 
 

      Минск, 2011 

Оглавление 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ

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

     Начало  теории графов датируют 1736 г., когда  Л. Эйлер решил популярную в то время «задачу о кенигсбергских мостах». Термин «граф» впервые был введен спустя 200 лет (в 1936 г.) Д. Кенигом.

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

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

Таблица №1. Примеры ориентированных  графов 

Орграф Вершины Дуги
Чайнворд Слова Совпадение  последней и первой букв (возможность связать два слова в цепочку)
Стройка Работы Необходимое предшествование (например, стены нужно построить  раньше, чем крышу, т. п.)
Обучение Курсы Необходимое предшествование
Одевание  ребенка Предметы гардероба Необходимое предшествование (например, носки должны быть надеты раньше, чем ботинки, и т.п.)
Европейский город Перекрестки Узкие улицы  с односторонним движением
Организация Сотрудники Иерархия (начальник - подчиненный)

ГЛАВА 1

ОРИЕНТИРОВАННЫЕ ГРАФЫ

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

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

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

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

Рисунок 1.1.1.

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

     Пусть — некоторый орграф. Ориентированным  маршрутом (или просто маршрутом) в графе называется такая последовательность (1) его чередующихся вершин дуг, что . Такой маршрут назовем -маршрутом. Вершины и назовем крайними, а остальные вершины маршрута (1) — промежуточными (внутренними). Длиной маршрута называется число входящих в него дуг. Маршрут называется цепью, если все входящие в него дуги различны, и путем, если все входящие в него вершины, кроме, возможно, крайних, различны.

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

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

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

     Если  в орграфе существует -маршрут, то говорят, что вершина достижима из вершины . Любая вершина считается достижимой из себя самой.

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

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

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

Рисунок 1.1.2.

     На рис. 1.1.2, а изображен сильный орграф, на рис. 1.1.2, б — односторонний, а на рис. 1.1.2, в — слабый.

     Маршрут, содержащий все вершины орграфа , называется остовным.

     Утверждение 1.1. Орграф является сильным тогда и только тогда, когда в нем есть остовный циклический маршрут.

     Доказательство:

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

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

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

     Аналогично  доказывается

     Утверждение 1.2. Орграф является односторонним тогда и только тогда, когда в нем есть остовный маршрут. Орграф является слабым тогда и только тогда, когда в нем есть остовный полумаршрут.

     Подграфы  и порожденные подграфы ориентированного графа определяются так же, как и для неориентированного. Так же определяются и операции над орграфами.

     Введем  важное понятие сильной компоненты орграфа. Сильной (или сильносвязной) компонентой ориентированного графа называется любой его максимальный относительно включения сильный подграф.

     Очевидно, что отношение взаимной достижимости вершин ориентированного графа рефлексивно, симметрично и транзитивно.

Рисунок 1.1.3.

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

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

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

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

     На рис. 1.1.3 представлены орграф и его конденсация .

     Утверждение 1.3. Конденсация любого орграфа не имеет контуров.

     Доказательство.

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

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

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

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

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

     1.2. Полустепени исхода и полустспени захода

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

     Полустепенью  исхода вершины называется число дуг, исходящих из , т.е. . Аналогично определяется полустепень захода вершины : .

     Степень вершины орграфа — это число инцидентных ей дуг: .

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

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

     Поэтому верно следующее утверждение, являющееся аналогом леммы о рукопожатиях.

     Утверждение 2.1. Сумма полустепеней исхода всех вершин орграфа равна сумме полустепеней захода и равна числу его дуг: .

     Нетрудно  убедиться в том, что равенство (1) не является достаточным условием для существования бинарной -матрицы с векторами строчных сумм и столбцевых сумм . Например, нет матрицы , для которой , .

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

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

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

     Теорема 2.2. Пара векторов , (2)

     является графической тогда и только тогда, когда выполняются следующие два условия:

     1) последовательность (3) графическая;

     2) .

     Доказательство:

     Очевидно, что пара векторов (2) реализуется двудольным графом тогда и только тогда, когда последовательность (3) реализуется расщепляемым графом, для которого и — списки степеней вершин верхней и нижней долей соответственно. Поэтому доказываемое непосредственно вытекает из критерия расщепляемости графической последовательности.

     Коснемся  вопроса о реконструируемости орграфов. Гипотезу Келли — Улама для ориентированных графов можно попытаться сформулировать так же, как и для неориентированных. Но для орграфов эта гипотеза не верна. 

Рисунок 1.2.1. 

     П. Стокмейер (1977, 1981 гг.) нашел несколько  семейств нереконструируемых орграфов. Одно из них состоит из сильных турниров специального вида. Два нереконструируемых турнира изображены на рис. 1.2.1. Ф. Харари и К. Палмер доказали (1967 г.), что любой турнир, не являющийся сильным, реконструируем.

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

     Гипотеза  Рамачандрана (1981 г.). Любой орграф -реконструируем.

     Эта гипотеза пока не доказана и не опровергнута.

     1.3. Обходы

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

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

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

     Теорема 3.1. Для связного ориентированного графа следующие утверждения равносильны:

     1) граф эйлеров;

     2) для любой вершины верно равенство ;

     3) граф является объединением контуров, попарно не имеющих общих ребер.

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

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

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

     Теорема 3.3 (M. Мейниел, 1973 г.). Пусть — сильный орграф порядка без петель и параллельных дуг. Если для любой пары и его несовпадающих несмежных вершин справедливо неравенство , то в есть гамильтонов контур.

     Для доказательства этой теоремы проделаем некоторую предварительную работу.

     Если  , ,то через обозначим множество дуг орграфа с началом и концом в , а через —множество дуг между и , то есть дуг вида или , где . 

Рисунок 1.3.1. 

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

     Лемма 3.4. Пусть — путь в орграфе , , и пусть в нет -пути, множество вершин которого совпадает с . Тогда .

     Доказательство:

     Для любого , , положим .

     Очевидно, что , (1), иначе и существовал бы путь, запрещенный условием леммы (рис. 1.3.1). Суммируя неравенства (1) по всем и учитывая при этом возможность существования каждой из дуг и , получим .

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

     1) длина пути не меньше чем 2;

     2) начальная и конечная вершины пути принадлежат множеству ;

     3).никакая из других вершин, входящих в , не принадлежит множеству .

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

     1) В  нет -путей. Возьмем какие-либо две вершины — одну в , а другую — вне . В сильном орграфе есть контур , содержащий эти две вершины и потому отличающийся от . Эти два контура имеют ровно одну общую вершину, скажем, , иначе в был бы -путь. Пусть теперь и — вершины, непосредственно следующие за в контурах и соответственно (рис. 1.3.2). 

          Рисунок 1.3.2.                                                          Рисунок 1.3.3.

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

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

     2) В графе  есть -пути. Выберем среди них путь с минимальным (см. рис. 1.3.3). Из максимальности контура следует, что . Определим как максимальное среди таких чисел , что и в есть -путь , для которого (возможно и тогда ). Таким образом, . Так как также является контуром, из максимальности контура вытекает, что . Из выбора числа следует, что в нет -пути с множеством вершин , так что в силу леммы 3.4 вершина соединена с не более чем дугами.

     Пусть . Так как контур максимален, то в нет -пути с множеством вершин . Из леммы 3.4 теперь следует, что вершина соединена с не более чем дугами.

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

     Учитывая  вышесказанное, получаем для несмежных  вершин и

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

     Очевидно

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

 
     1.4. Пути

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

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

     Теорема 4.1 (Т. Галлаи и А. Мигрэм, 1960 г.). Для любого орграфа верно неравенство .

     Фиксируем некоторое разбиение (1) орграфа  на пути. Пусть , , — множество начальных вершин этих путей. Докажем более сильное утверждение:

     существует  такое разбиение  орграфа на пути, что , .

     Доказательство:

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

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

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

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