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

Пусть 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 -матрицы А вектор с_А = { с₁, с₂,..., с_m), i-я координата с_i которого равна чис­лу единиц в i-й строке этой матрицы, называется векто­ром строчных сумм. Аналогично определяется вектор столбцевых сумм d_A = (d₁, d₂,..., d_n): координата d_t равна числу единиц в i-м столбце. Очевидно, что

(1)

поскольку каждая из этих сумм равна числу всех единиц матрицы А.

Если А = A (G) — матрица смежности орграфа G, то

г. е. число единиц в i-й строке матрицы A(G) равно по­лустепени исхода i-й вершины, а число единиц в j-м cтолбце равно полустепени захода j-й вершины. Таким oбразом, для A — A (G) имеем

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

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

Нетрудно убедиться в том, что равенство (1) не является достаточным условием для существования бинарной n X m -матрицы А с векторами строчных сумм с_А и столб­овых сумм d_A. Например, нет матрицы А, для которой с_А = (3,0), d_A =(2,1).

Пара векторов с = (с₁, с₂,..., с_m), d = (d₁, d₂,..., d_n) целыми неотрицательными координатами называется графической, если существует бинарная m X w-матрица А, для которой с_А = с, d_A = d. Если истолковывать эту мат­рицу как приведенную матрицу смежности двудольного графа, то вектор с_А окажется списком степеней вершин того графа, принадлежащих одной доле, а вектор d_A — списком степеней вершин другой доли, так что условия графичности пары векторов являются условиями существования соответствующего двудольного графа — реализации этой пары. Этим и объясняется термин «графическая пара векторов».

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

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

Теорема 64.2. Пара векторов с = (с₁, с₂,..., с_m), d = (d₁, d₂,..., d_n) (2)

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

1) последовательность

(с₁ + m - 1, с₂ + m - 1,..., с_m + m - 1, d₁ , d₂,..., d_n) (3)

графическая;

2)

> Очевидно, что пара векторов (2) реализуется дву­дольным графом тогда и только тогда, когда последова­тельность (3) реализуется расщепляемым графом, для которого (с₁ + m - 1, с₂ + m - 1,..., с_m + m - 1) и (d₁ , d₂,..., d_n) — списки степеней вершин верхней и ниж­ней долей соответственно. Поэтому доказываемое непо­средственно вытекает из критерия расщепляемости гра­фической последовательности (утверждение 49.3). <

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

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

А. Рамачандран предложил новый вариант гипотезы реконструируемости для орграфов. Пусть G — ориентиро­ванный граф. Вместе с каждым подграфом G_V = G — v, будем рассматривать упорядоченную пару (d⁺(v), d^-(v)) полустепеней исхода и захода вершины v. Орграф G назовем N-реконструируемым, если он определяется с точностью до изоморфизма набором {(G_v, d⁺(v), d^-(v)}.

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

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

Обходы

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

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

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

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

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

2) для любой вершины v <= VG верно равенство D(v) = d^-(v);

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

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

d⁺(vi) = d^-(v₁)+1, d+(v₂)=d^-(v₂)-1

d⁺(v) = d^-(v) для любой вершины v, отличной от v₁ и v₂.

Контур (путь) орграфа 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 = { v₁, v₂,..., v_k) — путь в ор­графе G, v<=VG\VP, и пусть в G нет (v₁, и_к)-пути, мно­жество вершин которого совпадает с VP U v. Тогда |Е(и, VP)|<k+L

> Для любого i, 1<i<k-1, положим

Очевидно, что

иначе в G существовал бы путь, запрещенный условием леммы (рис. 65.1). Суммируя неравенства (1) по всем i = ( 1, к — 1) и учитывая при этом возможность существо­вания каждой из дуг (v, v₁) и (v _к, v), получим

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

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

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

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

> Теперь перейдем к доказательству теоремы 65.3, которое проведем от противного. Пусть орграф G удовлет­воряет условиям теоремы и не является гамильтоновым и пусть S = (v₁, v₂,..., v_k, v₁) —такой контур в G, мно­жество вершин которого не является собственным под­множеством множества вершин другого контура. Рассмот­рим отдельно два случая.

1) В G нет VS-путт. Возьмем какие-либо две верши­ны — одну в S, а другую — вне S. В сильном орграфе G есть контур S', содержащий эти две вершины и потому отличающийся от S.

Эти два контура имеют ровно одну общую вершину, скажем, v_a, иначе в G был бы VS-путь. Пусть теперь v_a+1 и v — вершины, непосредственно сле­дующие за v_a в контурах S и S' соответственно (рис. 65.2). Так как в орграфе G нет VS -путей, то вершина v не смежна ни с одной из вершин, входящих в S и отличных от v_a. По той же причине для любой вершины и VG\(VSU v) верно неравенство | Е(и, {v_a+1,v})|<2. Следовательно, для несмежных вершин v и v_a+1 имеем

что противоречит условию теоремы (здесь первая сумма учитывает дуги, соединяющие вершины v_a+1 и v с вер­шинами из VS, а вторая —дуги, соединяющие и_а+1 и v с остальными вершинами графа).

2) В орграфе G есть VS-nymи Выберем среди них путь

P = (v_a, и₁, и₂,..., и_а, V_a+ γ ) с минимальным γ (см. рис. 65.3). Из максимальности контура S следует, что γ > 1. Определим β как макси­мальное среди таких чисел i, что 1 < i < γ и в G есть (V_a+ γ, V_a) -путь Р', для которого

VP' = VS\{v_a+i,..., v_a+ γ -1 }

(возможно, β = 1 и тогда Р' = (v_a+ γ, v_a+ γ _+1, …., v_a). Та­ким образом, | VP'| = к — β + γ. Так как PUP' также яв­ляется контуром, из максимальности контура S вытекает, что (} < у. Из выбора числа β следует, чтов G нет (V_a+ γ, V_a) -пути с множеством вершин VP' U (v_a+t), так что в силу леммы 65.4 вершина v_a+ β соединена с Р' не более чем к — β + γ + 1 дугами.

Пусть Р" = (v_a+ γ, v_a+ γ _+1, …., v_a).. Так как контур S максимален, то в G нет (v_a+i, v _а)-пути с множеством вер­шин VP" U и₁. Из леммы 65.4 теперь следует, что верши­на и₁ соединена с Р" не более чем к — γ + 2 дугами.

Из минимальности числа γ вытекает, что и₁ не смеж­на ни с какой вершиной v_a+1, 1< i <γ, и что для любой вершины и VG\(VSU и₁) выполняется неравенство

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

Учитывая полученные выше соотношения, а также то, что

и в графе могут существовать дуги вида (v_a+β, v_a+i), (v_a+i,v_a+β), 1< i <γ получаем

что противоречит условию теоремы. <

Очевидно

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

Пути

Пусть

(1)

— какое-либо множество путей орграфа G, попарно не имеющих общих вершин. Если множества VPi вершин этих путей составляют разбиение для VG, т. е.

то множество путей М называется разбиением орграфа G на пути. Минимальное число l путей, составляющих раз­биение орграфа G, обозначим через l(G).

Ниже фигурируют понятия числа независимости a₀{G) и хроматического числа χ(G) орграфа G, которые для ориентированных графов определяются так же, как и для неориентированных, т. е. a₀ (G)= a₀ (G₆), χ(G)= χ(G_b).

Теорема 66.1 (Т. Галлаи и А. Милгрэм, 1960 г.). Для любого орграфа G верно неравенство l(G) ≤ a₀ (G).

Фиксируем некоторое разбиение (1) орграфа G на пу­ти. Пусть N(M) = { a₁, a₂,..., a_l), a_i Pi,— множество на­чальных вершин этих путей. Докажем более сильное ут­верждение:

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

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

Вначале покажем, что, не ограничивая общности, мож­но считать | М| < a₀(G)+ 1. В самом деле, пусть | М| ≥ a₀(G)+ 2. Рассмотрим орграф G₁ = G — VP₁. Очевид­но, что a₀(G₁) ≤ a₀(G). Пo индуктивному предположе­нию существует разбиение М₁ орграфа G₁ на пути с

Пусть теперь | М| — a₀(G)+ 1. Тогда множество N(M) = (a₁, a₂,..., a_l) не является независимым, т. е. в нем есть хотя бы одна пара смежных вершин. Предполо­жим, что (a₁, a₂) AG. Если путь P ₁ состоит из единст­венной вершины a ₁, то объединив P ₁ и Р ₂ в путь (a₁, a₂ ...), получим нужное разбиение.

Если же путь P ₁ =(a₁, b₁,...) имеет более чем одну вершину, то рассмотрим орграф G₁ = G — a₁. По индук­тивному предположению существует такое разбиение М₁ орграфа G₁ на пути, что | М| < a₀(G₁) < a₀(G) и N(M₁)<={b₁, a₂, a₃,..., a_l). Если b₁ N(M₁), то М' полу­чим из M₁, добавив вершину а₁ к пути, начинающемуся в b₁. Аналогично можно поступить и тогда, когда а₂ N(M₁).

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

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

Следствие 66.2 (теорема Дилворта, 1950 г.). Если орграф G транзитивен, то l(G) = a₀(G).

> Согласно предыдущей теореме l(G) <= a₀(G). Но две вершины транзитивного орграфа, принадлежащие од­ной цепи, смежны, поэтому a₀(G)<= l(G). Итак, l(G) = a₀(G).

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

> Поскольку любые две вершины произвольного тур­нира Т смежны, то a₀(T)= 1. Поэтому существует цепь Р, содержащая все вершины турнира Т. <

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

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

> Пусть S(и) и Р(и)— множество всех тех вершин v и, соответственно, w турнира Г, для которых (и, v) AT и (w, u)^AT. Оба эти множества не являются пу­стыми, поскольку орграф Т сильный. По той же причине существует хотя бы одна дуга (v, w), идущая из S(и) в Р(и) (рис. 66.1). Следовательно, вершина и лежит на контуре длины 3.

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

Пусть C = (v₀, vi,..., v_h), v_Q = v_k = и,— контур дли­ны к. Предположим, что для некоторой вершины w, не

входящей в этот контур, су­ществуют такие дуги (w, х) и (у, w), что х VC и у VC. Тогда в С есть такие две смежные вершины v_i и v_i+1, что (v_i, w) и (w, v_i+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, что орграф G₁ = G — В не имеет контуров. Для любой вершины v определим t(v) как число вершин пути в орграфе G₁ с началом в v, имею­щем максимальную длину. Приписав каждой вершине и цвет t(v), получим раскраску орграфа G не более чем к + 1 цветами. Остается доказать, что эта раскраска пра­вильная, т. е. что t(и)<>t(v) для любых двух смежных вершин и и v. Но если (и, v) AG₁, то t(u)>t(v). Если же (a, v) B, то G₁ + (u, v) имеет контур. Поэтому в G₁ существует (v, u) -путь и, следовательно, t(v)> t(u).

Итак, доказано, что χ(G)< к + 1. <