В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 52
Текст из файла (страница 52)
Очевидно, что отношение взаимной достиягимости вершин ориентированного графа С рефлексивно, симметрично и транзитивно. Следовательно, мы получим разбиение в =в»>'е> и>> о Рве. 63.3 мяо>кества УС на классы, обьеднннв в один класс все вершины, достпясимые друг нз друга. Подграфы, порожденные классами этого разбиення, и только они, слуя1ат сильпымп компонентами орграфа С.
В орграфе могут быть дуги, не входящие ни в одну из его сильных компонент. Орграф С, изобраясенный ва рпс. 63.3, имеет четыре сильные компоненты с множествами вершин Ь>, оп ог, о4), М, ог, Ы, )Рт) н Ьг) Пусть >Я>, Яг, ..., Я ) — множество всех сильных компонент ориентированного графа С. Лонденсоцией орграфа С называется орграф С*, вершины г>, вн ..., г которого соотвотству>от сильным компонентам орграфа С, и пара (г>, в;) является дугой в С* тогда и только тогда, когда в С есть дуга, начало которой принадлежит компоненте Я>, а конец — Я;. На рис. 63.3 представлены орграф С и его конденсация С*.
Утверждение 63.3. Конденсация Се любого орграФа С не имеет контуров. !> Проведем доказательство от противного. Пусть Т = =(зо, хи зн ..., зо) — контур в С". Тогда каждая вершина, входящая в компоненту Яь достижима пз любой вершины, входящей з коьпгопенту 8ь Но зто противоречит максимальности сильных компонент..З !!оорионтированпый мультпграф, получающийся в результате снятия ориентации с дуг орграфа С, называется основанием орграфа С и обозначается через Сг. Очевидно, что орграф является слабым тогда и только тогда, когда его основание — связный мультиграф.
Орграф называется несвязным, если его основание— несвязный мультиграф. Ориентированный граф называется турниром, если его основание является полным графом. Этот класс графов получил свое название в связи со спортивными турнирами без ничьих, проводимыми по круговой системе. Результаты встреч можно описать ориентированным графом, вершины которого соответствуют участникам соревнований, а дуга (и, и) есть в орграфе, если участник и победил участника и. 5 64. Полустепени исхода и полустепени захода Пусть С вЂ” ориентированный граф и и~ г'С. Множество концов всех дуг, исходящих из вершины и, обозначается через Г(и), а множество начал всех дуг, заходящих в и — через Г '(и). Иолуетепеныо исхода Ы+(и) верглины и называется число дуг, исходящих из и, т. е.
д+(и)= ~Г(и) ~. Аналогично определнется полустепень захода а (и) вершины щ д (и) = )Г '(и) !. Степень йеяи вершины и орграфа — зто число инцидентных ей дуг: Йеяо =д+(о)+ д (и). Длн произвольной бинарной т Хи-матрицы А вектор се =(еь см ..., с ), 1-я координата е~ которого равна числу единиц в 1-й строке втой матрицы, называется вектором строчных сумм. Аналогично определяется вектор етолбуевых сумм Ил =(дн дг, ..., Н„): координата д; равна числу единиц в 1-м столбце. Очевидно, что гп л ~е;=,~' д;, (1) иг ';=-1 поскольку каждая из этих сумм равна числу всех единиц матрицы Л.
Если Л =- Л (6) — матрица смежности орграфа 6, то Ай — ЛФ (/) ~', Ли й (У) т. е, число единиц в 1-и строке матрицы Л(6) равно полустепени исхода 1-й вершины, а число единиц в у-м столбце равно полустепени захода у-и вершины. Таким образом, для А = А (6) имеем с =(й«(1), И+(2), ..., И" (и)), йл=(й (1), Ы (2), ..., И (и)). Поэтому верно следующее утверждение, являющееся аналогом леммы о рукопожатиях. Ут в е р ж д е н и е 64.1. Сумма полустепеней исхода всех вершш«орграфа равна сумме полуетепеней захода и равнв, числу его дуг: ~~э ~й+(н) = — ~ й (о) = (А6(. «и го юе го Нетрудно убедиться в том, что равенство (1) не является достаточным условием для существования бинарной п Х т-матрицы А с векторамп строчных сумм с,, и столбцевых сумм йл.
Например, нет матрицы А, для которой с =(3, О), й =(2, 1). Пара векторов с=(си см ..., с„), Ы=(йн дг, ..., а ) с целыми неотрицательными координатамп называется графической, если существует бинарная т Х и-матрица Л, для которой ел = с, ал = И. Коли истолковывать эту матрицу как приведенную матрицу смежности двудольиого графа, то вектор сл окажется списком степопей вершин этого графа, принадлежащих одной доле, а вектор йл— списком степеней вершин другой доли, так что условия графичности пары векторов являются условиями существования соответствующего двудольного графа — реализации этой пары.
Этим и объясняется термин «графическая пара векторов». При та = и ту же матрицу А можно истолковывать как матрицу смежности орграфа, и тогда условия графичности пары векторов станут условиями существования ориентированного графа с заданными списками полустепеней исхода и полустепоней захода ве1ппин. Критерий графичности пары векторов устанавливается следующей теоремой.
Теорема 64.2. Пара векторов с=(сп сг, ..., с ), й=(йь йг, ..., Н„) (2) является графической тогда и только тогда, когда выполняются следующие два условия: 1) последовательность (с~ + т — 1, сг + т — 1, ..., с + т — 1, йп йг, ..., й„) (3) графическая; 2) ~ сг = ~~Р~ йо г=г г-1 С Очевидно, что пара векторов (2) реализуется двудольным графом тогда и только тогда, когда последовательность (3) реализуется расщепляемым графом, для которого (с~+ т — 1, сг+ т — 1, ..., с„+ т — 1) и (Ып йг, ..., т)„) — списки степеней вершин верхней и нижней долей соответственно.
Поэтому доказываемое непосредственно вытекает из критерия расщепляемости графической последовательности (утверждение 49.3) . Э Коснемся вопроса о реконструируемости орграфов, Гипотезу Келли — Улана для ориентированных графов мол<- но попытаться сформулировать так же, как и для неориентироваппых. 11о для орграфов эта гипотеза не верна.
Рас. 64.1 П. Стокмейер (1977, 1981 гг.) нашел несколько семейств нереконструируемых орграфов. Одно из них состоит иэ спльных турниров специального вида. Два нерекопструируемых турнира изображены на рис. 641. Ф. Харари и Е. Палмер доказали (1967 г.), что любой турнир, не являющийся сильным, реконструируем. 285 А. Рамачандран предложил новый вариант гипотезы реконструируемости для орграфов. Пусть С вЂ” ориентированный граф. Вместе с каждым подграфом 6.=6 — и, о ы УС, будем рассматривать упорядоченную пару (Ы'(о), И (и)) полустепеней исхода и захода вершины о. Орграф С назовем М-реконструирувмым, если он определяется с точностью до изоморфизма набором ((С„, йт(о), й (о)): и ы (тС), Гипотеза Р а м а ч а н д р а н а (1981 г ).
Любой орграф И-реконструируем, Эта гипотеза пока не доказана и не опровергнута. 5 65. Обходы Определения эйлеровых и гамильтоповых ориентированных графов сходны с аналогичными определениями для неориентированных. Цепь, содержащая каждую дугу орграфа, называется зйлеровой. Связный орграф называется гйлеровым, если в пем есть замкнутая эйлерова цепь.
Следующие две теоремы, характеризующие эйлеровы орграфы, доказываются так же, как и в неориентированном случае. Тео рема 65.1. Для связного ориентированного графа С следующие утверждения равносильны: 1) граф С зйлеров; 2) для любой вершины о ~ т'С верно равенство й'( ) = й-( ); 3) граф 6 является объединением контуров, попарно не имеющих общих ребер. Т е о р е м а 65.2. Связный орграф С содержит открытую вйлерову г(епь тогда и только тогда, когда в нем есть две такие вершины о~ и ог, что й+(о,)=И (о~)+1, й+(ог)=И (ог) — 1 и й+(и) = и' (о) для любой вершины о, отличной от о1 и ог.
Контур (путь) орграфа 6 называется гамильтоповым, если он содержит все вершины С. Гамильтонов орграф— это орграф, имеющий гамильтонов контур. Вопросы, связанные с распознаванием гамильтоновости орграфа и построением гамильтоновых контуров или путей, являются столь жо сложными, как и аналогичные шгпросы для неориентированных графов. Докажем одно достаточное условие гамильтоновости орграфа. 286 Теорема 65.3 (М.
Мейниел, 1973 г.). Пусть С— сильный орграф порядка п)1 бев петель и параллельных дуг. Если для любой пары и и о его несовпадающих несмелспых вершин справедливо неравенство Йея и+ + йод о > 2п — 1, то в С есть гамильтонов контур. Для доказательства атой теоремы проделаем некоторую предварительную работу. Если о ~и УС, Я вЂ” УС, то через Е(о - Я) обозначим множество дуг орграфа С с началом о и концом в Я, Рнс. 65.1 а через Е(ц Я) — множество дуг между и и Я, т. е.
дуг вида (о, г) или (г, о), где г ~н Я. Как и выше, множество вершин произвольного пути Р будем обозначать через )тР. Лемма 65.4. Пусть Р=(ои ог,, о,) — путь в орграфе С, оя 'т'С~'т'Р, и пусть в С нет (оь и„)-пути, множество вершин которого совпадает с УР 0 о. Тогда !Е(о, тР)! ( й+ 1. > Для любого г, 1 ~ г ~ й — 1, положим ~; =!Е(о; (о))! + )Е(о (о<, )) ). Очевидно, что ~,(1, 1=1, й — 1, (1) иначе в С существовал бы путь, запрещенный условием леммы (рис.
65.1). Суммируя неравенства (1) по всем ~= 1, й — 1 и учитывая при этом воэмояспость существования каждой из дуг (о, о~) и (о„о), получим ь — 1 ) Е(о, УР))(2+ ~ ~г(й+ 1. а г 1 Пусть У вЂ” УС. Путь Р в орграфе С назовем П-путем, если он удовлетворяет следующим трем условиям: 1) длина пути Р не меньше чем 2; 2) начальная и конечная вершины пути Р принадлежат мноягеству У; 3) никакая из других вершин, входящпх в Р, не принадлежит множеству У. > Теперь перейдем к доказательству теоремы 65.3, которое проведем от противного. Пусть орграф 6 удовлетворяет условиям теоремы и не является гамильтоновым и пусть Я=(иь ок ..., ин и~) — такой контур в 6, множество вершин которого не является собственным подмножеством множества вершин другого контура.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
