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

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

Процесс склейки эйлерова цикла из цикла и циклов похож на сборку ожерелья с подвесками. Индуктивный переход, а вместе с ним и вся теорема доказана.

Определение.

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

Теорема (критерий квазиэйлеровости).

Для того, чтобы конечный связный граф был квазиэйлеровским необходимо и достаточно, чтобы степени всех его вершин были чётными числами (при этом важен выбор начала цикла) или степени всех его вершин, за исключением ровно двух, были чётными числами, причём в первом случае эйлерова цепь является эйлеровым циклом, а во втором случае эйлерова цепь начинается в одной из вершин нечётной степени, а заканчивается в другой вершине нечётной степени.

23.Гамильтовы циклы.

Эйлеровы циклы характеризуются тем, что существуют циклы, содержащие каждое ребро один раз. Гамильтовы циклы определяются для конечно связных графов аналогичным образом, но только по отношению к вершинам.

Определение.

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

Определение.

Гамильтовой цепью в графе называется простая цепь, проходящая через все вершины по одному разу.

Пример:

Так называемая задача о бродячем торговце (коммивояжёре) также является задачей относящихся к гамильтовым цепям. Будем говорить, что простая цепь полная, если её нельзя продолжить при помощи добавления рёбер к какому-нибудь из концов.

Теорема.

Полная простая цепь длины имеет тип цикла, если , где – локальная степень вершины .

Теорема.

Максимальная (длиннейшая) простая цепь в связном графе может иметь тип цикла только тогда, когда граф имеет гамильтов цикл.

Теорема.

В связном графе либо имеется гамильтов цикл, либо длина его максимальных простых цепей удовлетворяет неравенству .

Теорема.

В графе без гамильтовых циклов длины его максимальных простых цепей удовлетворяют неравенству , где и – две наименьшие локальные степени.

Теорема.

Если в графе с вершинами для любой пары вершин и , , то имеет гамильтову цепь.

Если , то имеет гамильтов цикл.

Отсюда, в частности следует результат Дирака о том, что граф имеет гамильтов цикл, если для каждой его вершины .

24.Примеры задач и упражнений.

Пример 2.1 Построить граф G, заданный множеством вершин Х={X₁, X₂, X₃, X₄} и их отображениями Г(Х₁)={X₁, X₂}, Г(Х₂)={X₃, X₄}, Г(X₃)={X₁, X₄}, Г(Х₄)={X₁, X₂, X₃}.

Решение. Данный граф приведен на рис. 2.1

X₄

Рис. 2.1

Два графа G₁ и G₂ изоморфны, если существует такое взаимно-однозначное соответствие между множествами их вершин Х₁ и Х₂, что вершины соединены ребрами в одном из графов в том и только том случае, когда соответствующие им вершины соединены в другом графе. Если ребра ориентированы, то их направления также должны соответствовать друг другу.

Пример 2.2 Изоморфны ли графы, изображенные на рис. 2.2 и 2.3?

Рис.2.2

Рис. 2.3

Решение. Графы А₁ и А₂ не изоморфны, хотя они и имеют одинаковое число вершин и ребер. Но в графе А₁ одно из ребер направлено от а к b, а в графе А₂ оно направлено в другую сторону. Графы В₁ и В₂ изоморфны, т.к. они имеют одно и то же число вершин и любые две вершины графа В₁ соединены ребром только тогда, когда соответствующие им вершины графа В₂ также соединены ребром.

Пример 2.3 Являются ли полными (без учета петель) графы А₁, В₁, изображенные на рис. 2.2 и 2.3?

Решение. Граф В₁ не является полным, т.к. не все пары его вершин соединены ребрами. Например, (а₁, а₆), (а₃, а₈) и другие. Граф А₁ не является полным, т.к. ребро (a, b) ориентировано только в одном направлении.

Рис. 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.

Рис. 2.5

Решение.

Элемент , следовательно, в данном графе существует единственный путь длиной три. Это путь из вершины Х₁ в вершину Х₄:

.

Все элементы матрицы А⁴ равны нулю, следовательно, в графе отсутствуют пути длиной четыре.

25.Задачи для самостоятельного решения.

№ 2.1 Показать, что два графа на рис. 2.6 изоморфны.

Рис. 2.6

№ 2.2 «Три дома и три колодца». Три поссорившихся соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к колодцу?

№ 2.3 Найти степени и числа вершин для графов пяти правильных многогранников.

№ 2.4 Для графов, изображенных на рис. 2.7, указать пары, изоморфные друг другу.

Рис.2.7

№ 2.5 Среди графов, указанных на рис. 2.8, выделить полные графы (без учета петель).

Рис. 2.8

№ 2.6 Дан граф G (Рис. 2.9). Указать, какие из графов, изображенных на рис. 2.9б, являются частями графа G и какие – подграфами.

Рис. 2.9

Рис. 2.9б.

№ 2.8 Какие из графов, приведенных на рис.2.8 и 2.9, являются плоскими?

№ 2.9. Составить матрицы смежности и инцидентности для правильных многогранников.

№ 2.10. Построить матрицы смежности графов, изображенных на рис. 2.9.

№ 2.11 Для заданного на рис. 2.10 (ак) графа построить: матрицу смежности, матрицу инцидентности, матрицу достижимостей.

Рис. 2.10.

№ 2.15 Груз доставляется из пункта Х₀ в пункт Х₇ через перевалочные пункты Х₀…Х₇ (Рис.2.11). Расстояния между пунктами Х_iX_j указаны на соответствующем графе. Найти путь минимальной длины между Х₀ и Х₇ и его длину.

Рис. 2.11

1. Основы теории формальных грамматик.

26.Основные определения формальных грамматик.

В общем случае язык представляет собой бесконечное множество, а бесконечные объекты даже задать трудно: их невозможно задать простым перечислением элементов.

Определение.

Любой конечный механизм задания языка называется грамматикой.

Определение.

Формальный язык представляет собой множество цепочек в некотором конечном алфавите.

К формальным языкам можно отнести искусственные языки для общения человека с машиной – языки программирования.

Для задания описания формального языка необходимо:

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

2. Задать формальную грамматику языка, то есть перечислить правила, по которым из символов строятся их последовательности, принадлежащие определяемому языку, – правильные цепочки.

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

Определенный таким образом язык представляет собой формальную систему.

По способу задания правильных цепочек формальные грамматики разделяются на порождающие и распознающие.

Определение.

К порождающим относятся грамматики языка L, по которым можно построить любую «правильную» цепочку с указанием ее структуры и нельзя построить ни одной неправильной цепочки.

Определение.

Распознающая грамматика языка L – это грамматика, позволяющая установить, правильна ли произвольно выбранная цепочка и, если она правильна, то выяснить ее строение.

Распознающая грамматика задает критерий принадлежности произвольной цепочки данному языку.

Формальные грамматики широко применяются в лингвистике и программировании в связи с изучением естественных языков и языков программирования.

Автоматные и лингвистические модели строятся на базе теории формальных грамматик, основы которой были заложены в работах лингвиста Н. Хомского.

Определение.

Основными объектами, с которыми имеет дело теория формальных грамматик, являются символы, представляющие собой базовые элементы какого-либо непустого множества А любой природы, а также цепочки, построенные из этих элементов. Множество А называют алфавитом.

Символы будем обозначать строчными буквами латинского алфавита, а цепочки – в виде «ffghhh », которые будем считать ориентированными слева направо.

Цепочки будем обозначать также специальными символами – прописными буквами латинского алфавита или греческими буквами, например: γ = ffg, В = аbbа.

Определение.

Пустая цепочка ε это цепочка, которая не содержит ни одного символа.

Определение.

Длиной цепочки будем называть число символов, входящих в эту цепочку.

Длина цепочки обозначается следующим образом:

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

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