В.А. Носов - Комбинаторика и теория графов (1023552), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Затем проходим эйлеров цикл в компоненте графа G1, затем снова двигаемся по циклу С до следующейнеизолированной вершины графа G1. Ясно, что процесс заканчивается в исходной вершине, что и показывает существование эйлерова цикла. ♦Аналогичным образом доказываетсяТеорема 2. Связный граф G является полуэйлеровым тогда и только тогда, когдав нем существует точно две вершины нечетной степени. ♦ Аналогичное определениеможно сделать для ориентированных графов. Ориентированный эйлеров путь это ориентированный путь, содержащий каждую дугу точно один раз.

Ориентированный графназывается эйлеровым, если в нем существует ориентированный эйлеров путь.Аналогично теореме 1 можно доказать следующее утверждение.Теорема 3. Ориентированный граф G(V,E), у которого связан соответствующийскелетный граф, является Эйлеровым тогда и только тогда, когда либо для всех вершинv, di(v) = d0(v), либо существуют точно две вершины v1 и v2 такие, что d0(v1) = di(v1) + 1,d0(v2) + 1 = di(v2), а для остальных вершин81di(v) = d0(v).(3)В первом случае любой эйлеров путь является ориентированным циклом, во втором начинается в вершине v 1 заканчивается в вершине v2.Теорема 4. Пусть G - связный граф, имеющий точно 2s > 0 вершин нечетнойстепени.

Тогда существует s и не существует меньшего числа путей P1, … , Ps, которые всовокупности содержат все ребра графа G точно по одному разу. При этом каждый изпутей P1, … , Ps начинается в одной нечетной вершине и кончается в другой.♦ Согласно факта 1 в графе G имеется четное число 2s вершин нечетной степени. Разобьем эти вершины на s пар (v1, w1), … , (vs, ws). Образуем теперь новый граф G1,добавив каждой паре (vi,wi), i = 1, s ребро. Тогда G - связный граф, у которого все вершины четны.

Согласно теореме 1 в графе G1 существует эйлеров цикл С, проходящий повсем ребрам точно по одному разу. Удалим из цикла С добавленные ребра и получим sпутей P1, … , Ps, проходящих каждое ребро точно один раз. Ясно, что каждый путь начинается и кончается в нечетной вершине. Пусть теперь имеется t путей t < s P1, … , Pt,содержащих все ребра графа G. Тогда каждая нечетная вершина должна быть концомпути и, значит, имея 2s нечетных вершин, нельзя покрыть все ребра графа G менее, чем sпутями. ♦Приведем теперь алгоритм построения эйлерового пути в данном эйлеровомграфе.Теорема 5. Пусть G - эйлеров граф.

Тогда следующая процедура всегда возможна и приводит к построению эйлеровой цепи графа G.Выходя из произвольной вершины, идем по ребрам графа произвольным образом, соблюдая следующие правила:1) стираем ребра по мере их прохождения (вместе с изолированными вершинами, которые при этом образуются);2) на каждом этапе идем по ребру, удаление которого нарушает связность, только в том случае, когда нет других возможностей.♦ Убедимся сначала, что указанная процедура может быть выполнена на каждом этапе.

Пусть мы достигли некоторой вершины v, начав с вершины u, v ≠ u. Удаливребра пути из v в u, видим, что оставшийся граф G1 связен и содержит ровно две нечетных вершины v и u. Согласно теореме 2 граф G1 имеет эйлеров путь Р из v в u. Поскольку удаление первого ребра инцидентного u пути Р либо не нарушает связности G1, либопроисходит удаление вершины u и оставшийся граф G2 связен с двумя нечетными вер82шинами, то отсюда получаем, что описанное выше построение всегда возможно на каждом шаге. (Если v = u, то доказательство не меняется, если имеются ребра, инцидентныеu).

Покажем, что данная процедура приводит к эйлерову пути. Действительно, в G неможет быть ребер, оставшихся непройденными после использования последнего ребра,инцидентного u, поскольку в противном случае удаление ребра, смежному одному изоставшихся, привело бы к несвязному графу, что противоречит 2). ♦В качестве одного из применений эйлеровых графов приведем следующее.Пусть А = {0, 1, … , m-1} - алфавит из m букв. Ясно, что имеется mn различныхслов длины n в алфавите А. Последовательностью де Брейна называется циклическоеслово a0 a1 … aL-1 в алфавите А, такое, что подпоследовательности вида ai ai+1 … ai+n-1i = 0, … , L-1 состоят из всех возможных L = mn слов длины n. Наиболее важный случайдля приложений m = 2. Последовательности де Брейна производятся полноцикловымирегистрами сдвига.

Покажем существование последовательностей де Брейна.Пример.n = 1, m = 201n = 2, m = 20011n = 3, m = 20001011100011101Определим ориентированный граф Gm,n(V,E) следующим образом:1) V является множеством всех mn-1 слов длины n-1 над А.2) E является множеством всех mn слов длины n над А.3) дуга (a1, a2, … , an) имеет начальной вершиной (a1, … , an-1)и конечной вершиной (a2, … , an).Приведем граф G2,3 :83Ясно, что последовательности де Брейна соответствует замкнутый путь в графеGm,n, содержащий каждую дугу точно один раз. Обратно, ориентированный цикл в Gm,n,содержащий каждую дугу точно один раз, приводит к построению цикла де Брейна, есливыписывать соответствующие дуги подряд.Пример. Для графа G2,3 имеем эйлеров путь000, 001, 011, 111, 110, 101, 010, 100а соответствующую последовательность де Брейна00011101Теорема 6. Для любых целых m и n граф Gm,n имеет ориентированный эйлеровцикл.♦ Покажем сначала, что граф Gm,n сильно связен, а значит его соответствующийскелетный граф связен.

Действительно, пусть b1, … , bn-1 и c1, … , cn-1 две вершины. Тогда их соединяет следующий ориентированный путь(b1, b2, … , bn-1, c1), (b2, … , bn-1, c1, c2), … , (bn-1, c1, … , cn- 1).Далее di(v) = d0(v) = m для любой вершины v.Действительно, из вершины v = (b1, b2, … , bn-1) выходят дуги вида:(b1, b2, … , bn-1, c)и входят дуги вида (c, b1, … , bn-1), c ∈ A.Теперь по теореме 3 в графе Gm,n существуют эйлеровы циклы.Следствие. Для любых целых m, n последовательности де Брейна существуют.♦ Известен следующий результат.Теорема 7.

Для любых натуральных m, n существует точно(m!) mmnn−1последо-вательностей де Брейна.84§ 3. Гамильтоновы графы.Изучаемое понятие связано с существованием в графе цикла, проходящего ровно один раз через каждую вершину. Граф называется гамильтоновым, если в нем такойцикл существует и полугамильтоновым, если существует путь, проходящий через каждую вершину точно один раз. Ясно, что это определение можно распространить на ориентированные графы, если путь считать ориентированным. В отличие от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такогокритерия нет.

Большинство известных фактов имеет вид: “если граф G имеет достаточное количество ребер, то граф является гамильтоновым”. Приведем одну из таких теорем, известную как теорема Дирака.Теорема 1. Пусть в графе G(V,E) с n вершинами (n ≥ 3) выполняется условиеd(v) ≥nдля любого v ∈ V. Тогда граф G является гамильтоновым.2♦ Заметим сначала следующее.

Если к любому графу G добавить некоторое ко-личество новых вершин, соединяя каждую из них с каждой вершиной графа, то мы получаем гамильтонов граф G’. Пусть мы добавили к графу G(V,E) минимальное число kновых вершин, k > 0, после чего граф стал гамильтоновым. Рассмотрим гамильтоновцикл v1, w, v2 , … , v1 в графе G’, где vi ∈ V, w - одна из новых вершин. Следовательно,v2 не является смежной с v1 в графе G, поскольку тогда мы могли не использовать вершину w, что противоречило бы минимальности числа k. Далее, пусть вершинаv2’смежная с v2, а v1’- смежная с v1.

Тогда v2’ не может следовать за v1’ в цикле. Действительно, в этом случае цикл v1, w, v2, … , v1’, v2’, … , v1 можно заменить наv1, v1’, … , v2, v2’,… , v1 и снова высвободить вершину w. Значит, число вершин графаG’, не являющихся смежными с v2, не меньше числа вершин, смежных с v1, посколькуна гамильтоновом цикле за любой вершиной, смежной с v1, следует вершина, не смежная с v2.

Число вершин, смежных с v1, не меньше, чемn+ k, то же и для вершины v2.2Далее, поскольку любая вершина графа G’является либо смежной, либо не смежнойвершине v2, то, значит, общее число вершин n + k не меньше, чем 2(n+ k) = n + 2k. По2лученное противоречие показывает, чтоk = 0, т.е. исходный граф гамильтонов. ♦Приведем примеры гамильтоновых графов.851. Полный граф Kn гамильтонов.2. Граф единичного куба Bn гамильтонов.3.

Определим ориентированный граф Г(Sn) - вершинами которого являются n!перестановок. При этом от перестановки s1 к перестановке s2 идет дуга, если существуеттранспозиция, переводящая перестановку s1 в s2. Полученный граф Г(Sn)является гамильтоновым.В качестве примера приведем граф Г(S3) :112323Из предыдущего следует, что многие важные прикладные задачи сводятся к построениюгамильтонова цикла некоторого графа. Учитывая важность задачи перечисления перестановок. приведем еще один такой алгоритм на языке построения гамильтонова цикла вГ(Sn).

Алгоритм построения цикла опишем индуктивно. Пусть Ln - список всех перестановок символов 1, 2, … , n. Обозначим через Ln(i) (1 ≤ i ≤ n+1) множество перестановоксимволов 1, … , i-1, i+1, … , n+1, полученных следующим образом: Ln(n+1) = Ln и Ln(i),(1 ≤ i ≤ n) получено из Ln(i+1) заменой всех появлений i на i+1.Тогда положимLn+1= Ln(n+1) ∨ (n+1), L n(n) ∨ n, Ln(n-1) ∨ (n-1), L n(n-2) ∨ (n-2), … (4)Здесь символ ∨ означает, что в списке Ln(i) ∨ i все перестановки из Ln(i) дополняютсядописыванием справа элемента i.

Список L n(i) - это список Ln(i), написанный в обратном порядке. Нетрудно показать индукцией по n, что таким образом построенная последовательность перестановок содержит каждую перестановку точно один раз и каждаяпоследующая перестановка отличается от предыдущей одной транспозицией.Пример.n=3Имеем:L2(3) :(12) → (21)L2(2) :(13) → (31)L2(1) :(23) → (32)86L3 = L2(3) ∨ 3, L 2(2) ∨ 2, L2(1) ∨ 1 == (123) → (213) → (312) → (132) → (231) → (321) .Понятие "почти все" графы.Пусть G(n) – множество всех графов на множестве вершин V = {1, 2, ..., n}.Пусть P – некоторое свойство, которым каждый граф из G(n) может обладать или нет.Пусть Gp(n) – множество тех графов из G(n), которые обладают свойством P.Говорят, что почти все графы обладают свойством P, если| Gp ( n)|lim| G( n)|n→∞=1и почти нет графов со свойством P, еслиlim| Gp ( n)|n→∞| G( n)|=0В качестве примера использования данного понятия докажем один результат.Теорема.

Почти нет эйлеровых графов. Пусть G1(n) – множество эйлеровых графов, G(n) – множество всех графов,G2(n) – множество графов, вершины которых имеют четную степень. По теореме Эйлераимеем G1(n) ⊆ G2(n), т.к. в G2 не учтена связность.Ясно, что графы из G2(n) можно получить из графов G(n – 1) добавлением новойвершины и соединением ее со всеми вершинами нечетной степени.Имеем| G( n − 1)| = 2| G2 ( n)|≤ 2| G( n)| = 2 n−1 2  n−1 2 =2 n  − n+ 1 2 n  2Отсюда получаем, что|G2(n)| = 0(|G(n)|)и|G1(n)| = 0(|G(n)|)что и доказывает утверждение. Отметим без доказательства другие утверждения такого типа.Теорема. Почти все графы связны.Теорема.

Характеристики

Список файлов книги