![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Пусть G — ориентированный граф и v VG. Множество концов всех дуг, исходящих из вершины v, обозначается через Г (у), а множество начал всех дуг, заходящих в v — через Г-1 (v).
Полустепенъю исхода d+(v) вершины v называется число дуг, исходящих из v, т. е. d+(v)= / Г(v) /I. Аналогично определяется полустепень захода d-(v) вершины v: d-(v)= / Г-1(v) /.
Степень deg v вершины v орграфа — это число инцидентных ей дуг:
Для произвольной бинарной m X n -матрицы А вектор сА = { с1, с2,..., сm), i-я координата сi которого равна числу единиц в i-й строке этой матрицы, называется вектором строчных сумм. Аналогично определяется вектор столбцевых сумм dA = (d1, d2,..., dn): координата dt равна числу единиц в i-м столбце. Очевидно, что
(1)
поскольку каждая из этих сумм равна числу всех единиц матрицы А.
Если А = A (G) — матрица смежности орграфа G, то
г. е. число единиц в i-й строке матрицы A(G) равно полустепени исхода i-й вершины, а число единиц в j-м cтолбце равно полустепени захода j-й вершины. Таким oбразом, для A — A (G) имеем
Поэтому верно следующее утверждение, являющееся аналогом леммы о рукопожатиях.
Утверждение 64.1. Сумма полустепеней исхода icex вершин орграфа равна сумме полустепеней захода и швна числу его дуг:
Нетрудно убедиться в том, что равенство (1) не является достаточным условием для существования бинарной n X m -матрицы А с векторами строчных сумм сА и столбовых сумм dA. Например, нет матрицы А, для которой сА = (3,0), dA =(2,1).
Пара векторов с = (с1, с2,..., сm), d = (d1, d2,..., dn) целыми неотрицательными координатами называется графической, если существует бинарная m X w-матрица А, для которой сА = с, dA = d. Если истолковывать эту матрицу как приведенную матрицу смежности двудольного графа, то вектор сА окажется списком степеней вершин того графа, принадлежащих одной доле, а вектор dA — списком степеней вершин другой доли, так что условия графичности пары векторов являются условиями существования соответствующего двудольного графа — реализации этой пары. Этим и объясняется термин «графическая пара векторов».
При m = п ту же матрицу А можно истолковывать как матрицу смежности орграфа, и тогда условия графичности пары векторов станут условиями существования ориентированного графа с заданными списками полустепеней схода и полустепеней захода вершин.
Критерий графичности пары векторов устанавливается следующей теоремой.
Теорема 64.2. Пара векторов с = (с1, с2,..., сm), d = (d1, d2,..., dn) (2)
является графической тогда и только тогда, когда выполняются следующие два условия:
1) последовательность
(с1 + m - 1, с2 + m - 1,..., сm + m - 1, d1 , d2,..., dn) (3)
графическая;
2)
> Очевидно, что пара векторов (2) реализуется двудольным графом тогда и только тогда, когда последовательность (3) реализуется расщепляемым графом, для которого (с1 + m - 1, с2 + m - 1,..., сm + m - 1) и (d1 , d2,..., dn) — списки степеней вершин верхней и нижней долей соответственно. Поэтому доказываемое непосредственно вытекает из критерия расщепляемости графической последовательности (утверждение 49.3). <
Коснемся вопроса о реконструируемости орграфов. Гипотезу Келли — Улама для ориентированных графов можно попытаться сформулировать так же, как и для неориентированных. Но для орграфов эта гипотеза не верна.
П. Стокмейер (1977, 1981 гг.) нашел несколько семейств нереконструируемых орграфов. Одно из них состоит из сильных турниров специального вида. Два нереконструируемых турнира изображены на рис. 64.1. Ф. Харари и Е. Палмер доказали (1967 г.), что любой турнир, не являющийся сильным, реконструируем.
А. Рамачандран предложил новый вариант гипотезы реконструируемости для орграфов. Пусть G — ориентированный граф. Вместе с каждым подграфом GV = G — v, будем рассматривать упорядоченную пару (d+(v), d-(v)) полустепеней исхода и захода вершины v. Орграф G назовем N-реконструируемым, если он определяется с точностью до изоморфизма набором {(Gv, d+(v), d-(v)}.
Гипотеза Рамачандрана (1981 г.). Любой орграф N-реконструируем.
Эта гипотеза пока не доказана и не опровергнута.
Обходы
Определения эйлеровых и гамильтоновых ориентиро-анных графов сходны с аналогичными определениями ля неориентированных.
Цепь, содержащая каждую дугу орграфа, называется эйлеровой. Связный орграф называется эйлеровым, если нем есть замкнутая эйлерова цепь.
Следующие две теоремы, характеризующие эйлеровы графы, доказываются так же, как и в неориентированым случае.
Теорема 65.1. Для связного ориентированного графа G следующие утверждения равносильны:
1) граф G эйлеров;
2) для любой вершины v <= VG верно равенство D(v) = d-(v);
3) граф G является объединением контуров, попарно имеющих общих ребер.
Теорема 65.2. Связный орграф G содержит открытую эйлерову цепь тогда и только тогда, когда в нем есть такие вершины v1 и v2, что
d+(vi) = d-(v1)+1, d+(v2)=d-(v2)-1
d+(v) = d-(v) для любой вершины v, отличной от v1 и v2.
Контур (путь) орграфа G называется гамильтоновым, если он содержит все вершины G. Гамилътонов орграф — это орграф, имеющий гамильтонов контур. Вопросы, связанные с распознаванием гамильтонового орграфа и построением гамильтоновых контуров или сетей, являются столь же сложными, как и аналогичные вопросы для неориентированных графов. Докажем одно достаточное условие гамильтоновости орграфа.
Теорема 65.3 (М. Мейниел, 1973 г.). Пусть G — сильный орграф порядка n>1 без петель и параллельных дуг. Если для любой пары и и v его несовпадающих несмежных вершин справедливо неравенство deg и + deg v > 2п — 1, то в G есть гамильтонов контур.
Для доказательства этой теоремы проделаем некоторую предварительную работу.
Если v<=VG, S VG, то через E(v->S) обозначим множество дуг орграфа G с началом v и концом в S, а через Е(и, S) — множество дуг между и и S, т. е. дуг вида (v, s) или (s, v), где s
S.
Как и выше, множество вершин произвольного пути Р будем обозначать через VP.
Лемма 65.4. Пусть P = { v1, v2,..., vk) — путь в орграфе G, v<=VG\VP, и пусть в G нет (v1, ик)-пути, множество вершин которого совпадает с VP U v. Тогда |Е(и, VP)|<k+L
> Для любого i, 1<i<k-1, положим
Очевидно, что
иначе в G существовал бы путь, запрещенный условием леммы (рис. 65.1). Суммируя неравенства (1) по всем i = ( 1, к — 1) и учитывая при этом возможность существования каждой из дуг (v, v1) и (v к, v), получим
Пусть U s VG. Путь Р в орграфе G назовем U-путем, если он удовлетворяет следующим трем условиям:
1) длина пути Р не меньше чем 2;
2) начальная и конечная вершины пути Р принадлежат множеству U;
3) никакая из других вершин, входящих в Р, не принадлежит множеству U.
> Теперь перейдем к доказательству теоремы 65.3, которое проведем от противного. Пусть орграф G удовлетворяет условиям теоремы и не является гамильтоновым и пусть S = (v1, v2,..., vk, v1) —такой контур в G, множество вершин которого не является собственным подмножеством множества вершин другого контура. Рассмотрим отдельно два случая.
1) В G нет VS-путт. Возьмем какие-либо две вершины — одну в S, а другую — вне S. В сильном орграфе G есть контур S', содержащий эти две вершины и потому отличающийся от S.
Эти два контура имеют ровно одну общую вершину, скажем, va, иначе в G был бы VS-путь. Пусть теперь va+1 и v — вершины, непосредственно следующие за va в контурах S и S' соответственно (рис. 65.2). Так как в орграфе G нет VS -путей, то вершина v не смежна ни с одной из вершин, входящих в S и отличных от va. По той же причине для любой вершины и VG\(VSU v) верно неравенство | Е(и, {va+1,v})|<2. Следовательно, для несмежных вершин v и va+1 имеем
что противоречит условию теоремы (здесь первая сумма учитывает дуги, соединяющие вершины va+1 и v с вершинами из VS, а вторая —дуги, соединяющие иа+1 и v с остальными вершинами графа).
2) В орграфе G есть VS-nymи Выберем среди них путь
P = (va, и1, и2,..., иа, Va+ γ ) с минимальным γ (см. рис. 65.3). Из максимальности контура S следует, что γ > 1. Определим β как максимальное среди таких чисел i, что 1 < i < γ и в G есть (Va+ γ, Va) -путь Р', для которого
VP' = VS\{va+i,..., va+ γ -1 }
(возможно, β = 1 и тогда Р' = (va+ γ, va+ γ +1, …., va). Таким образом, | VP'| = к — β + γ. Так как PUP' также является контуром, из максимальности контура S вытекает, что (} < у. Из выбора числа β следует, чтов G нет (Va+ γ, Va) -пути с множеством вершин VP' U (va+t), так что в силу леммы 65.4 вершина va+ β соединена с Р' не более чем к — β + γ + 1 дугами.
Пусть Р" = (va+ γ, va+ γ +1, …., va).. Так как контур S максимален, то в G нет (va+i, v а)-пути с множеством вершин VP" U и1. Из леммы 65.4 теперь следует, что вершина и1 соединена с Р" не более чем к — γ + 2 дугами.
Из минимальности числа γ вытекает, что и1 не смежна ни с какой вершиной va+1, 1< i <γ, и что для любой вершины и VG\(VSU и1) выполняется неравенство
Учитывая вышесказанное, получаем для несмежных вершин и1 и va+ β
Учитывая полученные выше соотношения, а также то, что
и в графе могут существовать дуги вида (va+β, va+i), (va+i,va+β), 1< i <γ получаем
что противоречит условию теоремы. <
Очевидно
Следствие 65.5. Сильный орграф порядка п без петель и параллельных дуг, степень каждой вершины которого не менее п, имеет гамилътонов контур.
Пути
Пусть
(1)
— какое-либо множество путей орграфа G, попарно не имеющих общих вершин. Если множества VPi вершин этих путей составляют разбиение для VG, т. е.
то множество путей М называется разбиением орграфа G на пути. Минимальное число l путей, составляющих разбиение орграфа G, обозначим через l(G).
Ниже фигурируют понятия числа независимости a0{G) и хроматического числа χ(G) орграфа G, которые для ориентированных графов определяются так же, как и для неориентированных, т. е. a0 (G)= a0 (G6), χ(G)= χ(Gb).
Теорема 66.1 (Т. Галлаи и А. Милгрэм, 1960 г.). Для любого орграфа G верно неравенство l(G) ≤ a0 (G).
Фиксируем некоторое разбиение (1) орграфа G на пути. Пусть N(M) = { a1, a2,..., al), ai Pi,— множество начальных вершин этих путей. Докажем более сильное утверждение:
существует такое разбиение М' орграфа G на пути, что
> Доказательство последнего утверждения проведем индукцией по n = |G|. Утверждение очевидно при п = 1, 2. Пусть п > 2 и утверждение верно для орграфов, порядки которых меньше п.
Вначале покажем, что, не ограничивая общности, можно считать | М| < a0(G)+ 1. В самом деле, пусть | М| ≥ a0(G)+ 2. Рассмотрим орграф G1 = G — VP1. Очевидно, что a0(G1) ≤ a0(G). Пo индуктивному предположению существует разбиение М1 орграфа G1 на пути с
Пусть теперь | М| — a0(G)+ 1. Тогда множество N(M) = (a1, a2,..., al) не является независимым, т. е. в нем есть хотя бы одна пара смежных вершин. Предположим, что (a1, a2) AG. Если путь P 1 состоит из единственной вершины a 1, то объединив P 1 и Р 2 в путь (a1, a2 ...), получим нужное разбиение.
Если же путь P 1 =(a1, b1,...) имеет более чем одну вершину, то рассмотрим орграф G1 = G — a1. По индуктивному предположению существует такое разбиение М1 орграфа G1 на пути, что | М| < a0(G1) < a0(G) и N(M1)<={b1, a2, a3,..., al). Если b1 N(M1), то М' получим из M1, добавив вершину а1 к пути, начинающемуся в b1. Аналогично можно поступить и тогда, когда а2
N(M1).
Из теоремы 66.1 вытекают два важных следствия.
Орграф G называется транзитивным, если истинна импликация
Следствие 66.2 (теорема Дилворта, 1950 г.). Если орграф G транзитивен, то l(G) = a0(G).
> Согласно предыдущей теореме l(G) <= a0(G). Но две вершины транзитивного орграфа, принадлежащие одной цепи, смежны, поэтому a0(G)<= l(G). Итак, l(G) = a0(G).
Следствие 66.3. В каждом турнире существует гамилътонов путь.
> Поскольку любые две вершины произвольного турнира Т смежны, то a0(T)= 1. Поэтому существует цепь Р, содержащая все вершины турнира Т. <
Для сильных турниров верно следующее более общее утверждение.
Теорема 66.4. Пусть Т — сильный турнир порядка п. Тогда для любой его вершины и и для любого числа k, 3 <k< п, в Т есть контур длины к, содержащий вершину и.
> Пусть S(и) и Р(и)— множество всех тех вершин v и, соответственно, w турнира Г, для которых (и, v) AT и (w, u)^AT. Оба эти множества не являются пустыми, поскольку орграф Т сильный. По той же причине существует хотя бы одна дуга (v, w), идущая из S(и) в Р(и) (рис. 66.1). Следовательно, вершина и лежит на контуре длины 3.
Далее воспользуемся индукцией по к. Пусть вершина и входит в контуры всех длин от 3 до к, где к < п. Покажем, что она входит в контур длины к + 1.
Пусть C = (v0, vi,..., vh), vQ = vk = и,— контур длины к. Предположим, что для некоторой вершины w, не
входящей в этот контур, существуют такие дуги (w, х) и (у, w), что х VC и у
VC. Тогда в С есть такие две смежные вершины vi и vi+1, что (vi, w) и (w, vi+1)— дугитурнира Т (рис. 66.2). Следовательно, вершина и входит в контур длины к + 1.
Если же указанной выше вершины w нет, то множество вершин турнира Т, не входящих в контур С, можно разбить на две части S(C) и Р(С) так, чтобы для любых вершин a S{C), b
P(C) и v
С выполнялись условия (v,a)
AG и (b, v)
AG. Так как орграф T сильный, то S(C) и Р(С) не пусты и существует дуга, идущая из некоторой вершины a
S(C) в некоторую вершину b
Р(С) (рис. 66.3).
Таким образом, вершина u входит в контур длины к+1
Очевидно
Следствие 66.5. Сильный турнир гамилътонов.
Заметим, что предыдущее следствие вытекает также из теоремы 66.3.
Теорема 66.6 (Т. Галлаи и Б. Руа, 1967 г.). Если к — максимальная длина путей в орграфе G, то χ(G)< к + 1.
> Обозначим через В такое минимальное относительно включения подмножество в AG, что орграф G1 = G — В не имеет контуров. Для любой вершины v определим t(v) как число вершин пути в орграфе G1 с началом в v, имеющем максимальную длину. Приписав каждой вершине и цвет t(v), получим раскраску орграфа G не более чем к + 1 цветами. Остается доказать, что эта раскраска правильная, т. е. что t(и)<>t(v) для любых двух смежных вершин и и v. Но если (и, v) AG1, то t(u)>t(v). Если же (a, v)
B, то G1 + (u, v) имеет контур. Поэтому в G1 существует (v, u) -путь и, следовательно, t(v)> t(u).
Итак, доказано, что χ(G)< к + 1. <
Дата публикования: 2015-01-23; Прочитано: 5803 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!