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

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

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

Необходимость очевидна, так как, двигаясь по эйлеровому циклу, войдя в вершину по одной дуге, мы выходим из неё по другой дуге, т.е. каждой «дуге выхода» соответствует «дуга входа». Каждая пара дуг даёт вклад, равный двум, в степень вершины, а поскольку эйлеров цикл содержит все дуги, то степень каждой вершины представлена суммой двоек, и значит чётна.

Достаточность.

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

Шаг 1. . Единственный граф, удовлетворяющий условиям теоремы изображён на рисунке.

Очевидно, его единственная дуга и образует эйлеров цикл.

Индуктивный переход.

Предположим, что утверждение теоремы (её достаточной части) справедливо для любого графа, у которого .

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

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

Каждая его компонента связности — конечный связный граф с чётными степенями вершин и дуг, меньшим либо равным . Тогда, по предположению индукции, на каждой компоненте связности существует эйлеров цикл. Обозначим Эйлеровы циклы компонент соответственно. Поскольку исходный граф связен, то цикл имеет хотя бы по одной общей вершине с компонентами графа . Выберем по одной общей с циклом вершине на каждой компоненте .

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

Теорема.

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

Теорема.

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

Теорема.

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

Теорема.

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

Теорема.

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

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

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

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

Пример 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

Решение.

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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