Лекции Русакова (1021002), страница 10

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

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

Эйлеровы цепи и цепи.рекаостровостровНужно пройти по всем мостам по одному разу и вернуться обратно..Утверждение.Если в псевдографе G имеется хотя бы одно ребро и отсутствуютвисячие вершины, то G содержит хотя бы один простой цикл.ДоказательствоЕсли в G имеется петля, то это уже цикл, если в G есть кратные ребра,то это тоже цикл. Допустим, что петель и кратных ребер нет.Пусть v1 и v2 – произвольные смежные вершины. Будем строитьпоследовательность v1, v2, v3… такую, что для любого i>2 вершины vi, vi-1смежны и vi≠vi-1 (т.к. в G нет висячих вершин, то эту последовательностьможно продолжать неограниченно).

Но рано или поздно какая-то из вершинповторится. Это и будет искомый цикл.88Утверждение.Для того чтобы связный псевдограф G обладал эйлеровым цикломнеобходимо и достаточно чтобы степени всех его вершин были четными.См. алгоритм.Утверждение.Для того чтобы связный псевдограф G обладал эйлеровой цепьюнеобходимо и достаточно, чтобы он имел ровно 2 вершины нечетнойстепени.(Нужно соединить начало и конец. Тогда задача сводится кпредыдущей).Алгоритм выделения эйлерова цикла в связном мультиграфе с четнымистепенями вершин1) Выделим из G цикл µ1. (т.к. степени верш. четны, то висячие верш.отсутствуют). Положим l=1, G’=G.2) Удаляем из G’ ребра, принадлежащие выделенному циклу.Полученный псевдограф снова обозначаем G’.

Если в G’ отсутствуют ребра,то переходим к шагу 4.3) Выделяем из G’ цикл. Присваиваем l:=l+1 и переходим к шагу 2.4) По построению выделенные циклы содержат все ребра по одномуразу. Если l:=1, то искомый эйлеров цикл найден (конец работы алгоритма).В противном случае находим циклы, содержащие хотя бы по одной общейвершине (в силу связности графа это всегда можно сделать). Склеиваем этициклы. Повторяем эти операции, пока не останется один цикл. Он и являетсяискомым.89Пример.Задача о Кенигсбергских мостах не имеет решения, т.к.

есть вершины снечетными степенями.2.18. Гамильтовы циклы.Эйлеровы циклы характеризуются тем, что существуют циклы,содержащие каждое ребро один раз. Гамильтовы циклы определяются дляконечно связных графов аналогичным образом, но только по отношению квершинам.Определение.Простой цикл называется гамильтовым, если он проходит черезкаждую вершину графа.Определение.Гамильтовой цепью в графе называется простая цепь, проходящаячерез все вершины по одному разу.90Пример:Так называемая задача о бродячем торговце (коммивояжёре) такжеявляется задачей относящихся к гамильтовым цепям.

Будем говорить, чтопростая цепь полная, если её нельзя продолжить при помощи добавлениярёбер к какому-нибудь из концов.Теорема.Полнаяпростаяцепьдлиныlимееттипцикла,еслиρ (a0 ) + ρ (a1 ) ≥ l + 1 , где ρ (a ) – локальная степень вершины a .Теорема.Максимальная (длиннейшая) простая цепь в связном графе можетиметь тип цикла только тогда, когда граф имеет гамильтов цикл.Теорема.91В связном графе либо имеется гамильтов цикл, либо длина егомаксимальных простых цепей удовлетворяет неравенству l ≥ ρ (a0 ) + ρ (a1 ) .Теорема.В графе без гамильтовых циклов длины его максимальных простыхцепей удовлетворяют неравенству l ≥ ρ1 + ρ 2 , где ρ1 и ρ 2– двенаименьшие локальные степени.Теорема.Если в графе G с n вершинами для любой пары вершин a0 и a1 ,ρ (a0 ) + ρ (a1 ) ≥ n − 1 , то G имеет гамильтову цепь.Если ρ (a0 ) + ρ (a1 ) ≥ n , то G имеет гамильтов цикл.Отсюда, в частности следует результат Дирака о том, что граф имеет1гамильтов цикл, если для каждой его вершины ρ (a ) ≥ n .22.19.

Примеры задач и упражнений.Пример 2.1 Построить граф G, заданный множеством вершин Х={X1,X2, X3, X4} и их отображениями Г(Х1)={X1, X2}, Г(Х2)={X3, X4}, Г(X3)={X1,X4}, Г(Х4)={X1, X2, X3}.Решение. Данный граф приведен на рис. 2.192Рис. 2.1Два графа G1 и G2 изоморфны, если существует такое взаимнооднозначное соответствие между множествами их вершин Х1 и Х2, чтовершины соединены ребрами в одном из графов в том и только том случае,когда соответствующие им вершины соединены в другом графе.

Если ребраориентированы, то их направления также должны соответствовать другдругу.Пример 2.2 Изоморфны ли графы, изображенные на рис. 2.2 и 2.3?93Рис.2.2Рис. 2.3Решение. Графы А1 и А2 не изоморфны, хотя они и имеют одинаковоечисло вершин и ребер. Но в графе А1 одно из ребер направлено от а к b, а вграфе А2 оно направлено в другую сторону. Графы В1 и В2 изоморфны, т.к.они имеют одно и то же число вершин и любые две вершины графа В1соединены ребром только тогда, когда соответствующие им вершины графаВ2 также соединены ребром.Пример 2.3 Являются ли полными (без учета петель) графы А1, В1,изображенные на рис.

2.2 и 2.3?Решение. Граф В1 не является полным, т.к. не все пары его вершинсоединены ребрами. Например, (а1, а6), (а3, а8) и другие. Граф А1 не являетсяполным, т.к. ребро (a, b) ориентировано только в одном направлении.94Рис. 2.4Пример 2.4 Дан ориентированный граф(рис. 2.4). Построить егоматрицы смежности и инцидентности.Решение. В соответствии с определением матрица смежности естьквадратная матрица с элементами множества вершин в качестве координат еестолбцов и строк.Элемент матрицы в строке i и столбце j равен 1, если есть ребро отвершины i к вершине j, -1- если есть ребро к вершине i от вершины j и 0 –если вершины i и j не соединены. Матрица смежности приведенав таблице 2.1В матрице инцидентности координатами строк являются элементымножества вершин, а координатами столбцов – элементы множества ребер.Элемент матрицы в строке i и столбце j равен 1, если ребро j исходит извершины i, -1 – если ребро j входит в вершину i, 0 – если ребро j неинцидентно вершине i.

Матрица инцидентности приведена в таблице 2.2.Пример 2.5 На рис. 2.5. задан граф G. Построить матрицу смежности ивыяснить, сколько путей длины три существует в графе G.95Рис. 2.5Решение.00A=001 0 00 1 00 0 10 0 0 00A3 = 000 0 10 0 00 0 00 0 0 Элемент( 3)a 14= 1,002A =0000A4 = 00следовательно,0000в00000 1 00 0 10 0 00 0 0 0000 данномграфесуществуетединственный путь длиной три.

Это путь из вершины Х1 в вершину Х4:VVV312X 1 →X 2 →X 3 →X4.Все элементы матрицы А4 равны нулю, следовательно, в графеотсутствуют пути длиной четыре.2.20. Задачи для самостоятельного решения.№ 2.1 Показать, что два графа на рис. 2.6 изоморфны.96Рис. 2.6№ 2.2 «Три дома и три колодца». Три поссорившихся соседа имеют триобщих колодца. Можно ли провести непересекающиеся дорожки от каждогодома к колодцу?№ 2.3 Найти степени и числа вершин для графов пяти правильныхмногогранников.№ 2.4 Для графов, изображенных на рис. 2.7, указать пары,изоморфные друг другу.97ГДЖКЕЗИЛМРис.2.7№ 2.5 Среди графов, указанных на рис. 2.8, выделить полные графы(без учета петель).98АБДВЕГЖРис.

2.8№ 2.6 Дан граф G (Рис. 2.9). Указать, какие из графов, изображенныхна рис. 2.9б, являются частями графа G и какие – подграфами.Рис. 2.9АБ99ВГДЖЕЗКЛИРис. 2.9б.МН№ 2.8 Какие из графов, приведенных на рис.2.8 и 2.9, являютсяплоскими?№2.9.Составитьматрицысмежностииинцидентностидляправильных многогранников.№ 2.10. Построить матрицы смежности графов, изображенных на рис.2.9.№ 2.11 Для заданного на рис. 2.10 (а÷к) графа построить: матрицусмежности, матрицу инцидентности, матрицу достижимостей.100АГЗБВДЕЖИКРис.

2.10.№ 2.15 Груз доставляется из пункта Х0 в пункт Х7 через перевалочныепункты Х0…Х7 (Рис.2.11). Расстояния между пунктами ХiXjуказаны насоответствующем графе. Найти путь минимальной длины между Х0 и Х7 иего длину.101АБВГРис. 2.11Глава 3. Основы теории формальных грамматик.3.01. Основные определения формальных грамматик.В общем случае язык представляет собой бесконечное множество, абесконечные объекты даже задать трудно: их невозможно задать простымперечислением элементов.Определение.Любой конечный механизм задания языка называется грамматикой.Определение.Формальный язык представляет собой множество цепочек в некоторомконечном алфавите.102К формальным языкам можно отнести искусственные языки дляобщения человека с машиной – языки программирования.Для задания описания формального языка необходимо:1.

Указать алфавит, то есть совокупность объектов, называемыхсимволами (или буквами), каждый из которых можно воспроизводить внеограниченном количестве экземпляров (подобно обычным печатнымбуквам или цифрам).2. Задать формальную грамматику языка, то есть перечислитьправила, по которым из символов строятся их последовательности,принадлежащие определяемому языку, – правильные цепочки.Правила формальной грамматики можно рассматривать как продукции(правила вывода), то есть элементарные операции, которые, будучиприменены в определенной последовательности к исходной цепочке(аксиоме), порождают лишь правильные цепочки.

Сама последовательностьправил, использованных в процессе порождения некоторой цепочки,является ее выводом.Определенный таким образом язык представляет собой формальнуюсистему.По способу задания правильных цепочек формальные грамматикиразделяются на порождающие и распознающие.Определение.К порождающим относятся грамматики языка L, по которым можнопостроить любую «правильную» цепочку с указанием ее структуры и нельзяпостроить ни одной неправильной цепочки.103Определение.Распознающая грамматика языка L – это грамматика, позволяющаяустановить, правильна ли произвольно выбранная цепочка и, если онаправильна, то выяснить ее строение.Распознающаяграмматиказадаеткритерийпринадлежностипроизвольной цепочки данному языку.Формальные грамматики широко применяются в лингвистике ипрограммировании в связи с изучением естественных языков и языковпрограммирования.Автоматные и лингвистические модели строятся на базе теорииформальных грамматик, основы которой были заложены в работах лингвистаН.

Хомского.Определение.Основными объектами, с которыми имеет дело теория формальныхграмматик, являются символы, представляющие собой базовые элементыкакого-либо непустого множества А любой природы, а также цепочки,построенные из этих элементов. Множество А называют алфавитом.Символы будем обозначать строчными буквами латинского алфавита, ацепочки – в виде «ffghhh», которые будем считать ориентированными слеванаправо.Цепочки будем обозначать также специальными символами –прописными буквами латинского алфавита или греческими буквами,например: γ = ffg, В = аbbа.Определение.104Пустая цепочка ε это цепочка, которая не содержит ни одного символа.Определение.Длиной цепочки будем называть число символов, входящих в этуцепочку.Длина цепочки обозначается следующим образом:|γ| = | ffg | = 3;|В| = | аbbа| = 4;|ε| = 0.3.02.

Основные операции формальных грамматик.Определение.Конкатенацией двух цепочек Х и Y называется такая цепочка Z, котораяполучается непосредственным слиянием цепочки Х, стоящей слева, ицепочки Y, стоящей права.Например, если X = ffg, Y = ghh, то конкатенация Х и Y – это цепочка Z= ffgghh. Обозначим операцию конкатенации символом о (или “.”).Свойства операции конкатенации можно записать следующимобразом:1) свойство замкнутости:о: А* × А* → А*;2) свойство ассоциативности:(∀Х ∈ А*, Y ∈ A*, Z ∈ A*)[(X o Y) o Z = X o (Y o Z)],105где через А* обозначено множество всех возможных цепочек(разумеется, бесконечное), составленных из конечного множества А базовыхэлементов (символов) словаря, включая пустую цепочку ε; символ хобозначает операцию декартова произведения двух множеств; а X, Y, Z –произвольные цепочки, принадлежащие А*.Рассмотрим пару (А*, 0).

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

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