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

     Из  теоремы 4.1 вытекают два важных следствия.

     Орграф  называется транзитивным, если истинна импликация .

     Следствие 4.2 (теорема Дилворта , 1950 г.). если орграф транзитивен, то .

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

     Согласно  предыдущей теореме  . Но две вершины транзитивного графа, принадлежащего одной цепи, смежны, поэтому . Итак .

     Следствие 4.3. В каждом турнире существует гамильнотов путь.

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

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

     Для сильных турниров верно следующее  более общее утверждение.

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

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

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

     Рисунок 1.4.1. 

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

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

     Рисунок 1.4.2.     Рисунок 1.4.3.

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

     Очевидно

     Следствие 4.5. Сильный турнир гамильтонов.

     Заметим, что предыдущее следствие вытекает также из теоремы 4.3.

     Теорема 4.6 (Т. Галлаи и Б. Руа, 1967 г.). Если — максимальная длина путей в орграфе , то .

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

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

     Итак, доказано, что  .

 
     1.5. База и ядро

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

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

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

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

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

     Понятие ядра для ориентированных графов вводится так же, как и для неориентированных.

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

Рисунок 1.5.1.                                 Рисунок 1.5.2. 

     Орграф, изображенный на рис. 1.5.1, имеет два ядра: .

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

     Рассмотрим  одно достаточное условие существование ядра.

     Теорема 5.2. Каждый орграф, не имеющий контуров нечетной длины, обладает ядром.

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

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

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

Рисунок 1.5.3.

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

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

Рисунок 1.5.4.

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

     Итак, множество  является независимым и доминирующим одновременно, т.е. — ядро. 
 

ГЛАВА 2

ПРАКТИЧЕСКАЯ  ЧАСТЬ

    Ниже  представлены способы решения некоторых  задач на описанную выше тему:

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

    Решение:

    Будем доказывать по методу математической индукции. Поскольку турнир – ориентированный  граф, основанием которого является полный граф, мы будем рассматривать только полные графы. В случае с двумя и тремя вершинами утверждение очевидно. Допустим, что для какого-то натурального n утверждение истинно. Пусть существует вершина с максимальной степенью исхода (количество очков), и степень ее исхода равна k . Из данной вершин исходит k дуг и входит n – k – 1 дуг, и расстояние до каждой из вершин графа равно или 1 или 2.

              
 
 
 

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

                                                                                                        
 
 

    Очевидно, что в таком случае новая вершина  не может быть соединена исходящими дугами с n – k – 1 вершинами, дуги из которых входят в вершину-победителя, потому что в таком случае расстояние от новой вершины будет равно двум, и задача в таком случае доказана. Также видно то, что с k вершинами, которые соединены с победителем исходящими дугами, новая вершина может быть соединена лишь исходящими из нее в эти же вершины дугами. Поскольку таких дуг может быть максимум k - 1 (так как вершина-победитель единственна), получится так, что новая вершина будет соединена с одной из k вершин входящей дугой, а не исходящей. Следовательно через эту вершину будет существовать маршрут из  вершины-победителя в новую вершину. Значит для графа порядка n+1 данное утверждение также является верным. База индукции верна – а значит – задача доказана.

    Задача2. Покажите, что в орграфе без контуров всегда есть вершина с нулевой полустепенью захода и вершина с нулевой полустепенью исхода.

    Решение:

    Доказательство  проведем от противного. Допустим существует орграф G без контуров , такой что каждая из его n вершин имеет полустепень исхода и полустепень захода отличные от нуля.  Возьмем произвольную вершину этого графа . Будем идти из данной вершины по выходящей из нее произвольной дуге, которая соединяет ее с другой вершиной, назовем ее . Поскольку каждая вершина имеет и входящие и исходящие дуги (по предположению), из вершины мы обязательно попадем в следующую вершину. Будем нумеровать данные вершины по порядку обхода. Из новой вершины мы попадем либо в (поскольку по предположению она имеет входящие в нее дуги), либо попадем в другую, еще не пройденную вершину. В итоге обойдя определенное количество вершин (n – если граф связный, и k – число вершин в произвольной выбранной компоненте, если нет) мы из какой-то вершины должны будем попасть в вершину . Иначе мы противоречим изначальному утверждению. Тогда мы получаем маршрут который будет являться контуром, что противоречит предположению.

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

    Таким образом в орграфе без контуров всегда есть вершина с нулевой  полустепенью захода и вершина с  нулевой полустепенью исхода.

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

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

    

      
 
 
 
 
 

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