Лекция 5. Эйлеровы пути и циклы. Критерий существования. Оценки сложности (1162201), страница 2

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

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

Поэтомуребра могут выходить из вершин первого стека. В первый стек первойпопадает вершина x1 и она последней его покидает. Поэтому построенныймаршрут замкнут: выходит из первой вершины и туда же возвращается.Кроме того, все ребра входят в построенный цикл: если ребро e = (x, y)входит в E, то из первого стека не может быть удалена вершина x, как иy. Далее, в процессе построения стеков на каждом шаге пройденное ребровычеркивается, поэтому любое ребро не может присутствовать вмаршруте более одного раза.

Теорема доказана.Оценка сложности построения эйлерова цикла: Алгоритм Флери заноситребро в первый стек один раз. Во второй стек аналогично. Следовательно,число необходимых вычислений имеет порядок O(m).13 / 17Полные циклыПусть n ∈ N, N = 2n .ОпределениеПоследовательность a1 , a2 , ..., aN +n−1 над алфавитом {0, 1}, называетсяполным циклом(последовательностью де Брёйна), если множество словa1 a2 ...an ; a2 a3 ...an+1 ; ...; aN aN +1 ...aN +n−1 состоит из всех возможных Nпоследовательностей b1 b2 ...bn из нулей и единиц.Пример. n = 2, N = 4 ⇒ a1 , a2 , ..., aN = 0011 ⇒ {00, 01, 11, 10} –множество всевозможных слов длины 2, записанных в алфавите из нулейи единиц.

Если положить другой набор, например 0101, то пары будуттакими: {01, 10, 01, 10}, т.е. последовательность 0101 не является полнымциклом. Легко проверить непосредственно, что при n=2 указанный наборопределяет единственно возможный полный цикл.n = 3, N = 8 ⇒ a1 , a2 , ..., aN = 0001011100 ⇒{000, 001, 010, 101, 011, 111, 110, 100} – множество всевозможных словдлины 3, записанных в алфавите из нулей и единиц. Рассмотрим другойнабор: 00011101 ⇒ 000, 001, 011, 111, 110, 101, 010, 100 – также множествовсевозможных слов длины 3, записанных в алфавите из нулей и единиц.14 / 17Полные циклы. Граф де БрёйнаРассмотрим произвольное слово b1 b2 ...bn длины n над алфавитом {0, 1} исоединим дугой, т.е. направленным ребром слова b1 b2 ...bn−1 и b2 b3 ...bn ,которые считаем элементами множества V .

Под петлями понимаем слова11...1 и 00...0. В полученном псевдоорграфе |V | = 2n−1 , |E| = 2n .Gn = (V, E) – граф де Брёйна. Рассмотрим его свойства.b1 b2 ...bn−1 ∈ V ⇒ (0b1 b2 ...bn−2 , b1 b2 ...bn−1 ), (1b1 b2 ...bn−2 , b1 b2 ...bn−1 ) паравходящих в вершину b1 b2 ...bn−1 дуг,(b1 b2 ...bn−1 , b2 ...bn−2 0), (b1 b2 ...bn−1 , b2 ...bn−2 0) – пара выходящих из этойвершины дуг. Следовательно, из каждой вершины графа выходит парадуг и в нее входит пара дуг.

Кроме того, Gn – связный граф: если двепроизвольные вершины b1 b2 ...bn−1 , c1 c2 ...cn−1 ∈ V , то последовательностьдуг (b1 b2 ...bn−1 , b2 b3 ...bn−1 c1 ), (b2 b3 ...bn−1 c1 , b3 b4 ...bn−1 c1 c2 ), ...,..., (bn−1 c1 c2 ...cn−2 , c1 c2 ...cn−1 ) соединяет эти два слова.15 / 17Полные циклыЛемма 1Множество эйлеровых циклов в графе Gn взаимно однозначносоответствует множеству полных циклов длины 2n .Доказательство.

По построению ребер графа Gn ребро(b1 b2 ...bn−1 , b2 b3 ...bn−1 c1 ) однозначно соответствует слову b1 b2 ...bn−1 c1 ,таких различных слов 2n , поэтому множество из 2n таких «соседних»слов, т.е. циклов де Брёйна, однозначно соответствует последовательностидуг в эйлеровом цикле.Определение. Орграф G называется 2-графом, если для каждойвершины имеется 2 дуги входящие и две выходящие из нее.Построенный граф Gn является 2-графом.Определение. Для 2-графа G двойственным графом называется графG∗ = (B, U ), для которого:1. B0 ∈ E ⇔ b0 ∈ B2.

B0 , B1 ∈ E, B0 = (a, b0 ), B1 = (b0 , c) ⇒ ∃(b0 , b1 ) ∈ UИз доказательства леммы 1 следует G∗n = Gn+116 / 17Полные циклыЛемма 2Если 2-граф G = (V, E) : |V | = m имеет M полных циклов, то G∗ имеетM · 2m−1 полных циклов.Следствие (Теорема де Брёйна)n−1Для всякого натурального n существует ровно 22−nциклов де Брёйна.17 / 17.

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

Список файлов лекций