Материал на экзамен

Планарность

•Плоский граф — граф с вершинами, расположенными на плоскости и непересекающимися ребрами.

•Планарный граф изоморфен плоскому.

•Всякий подграф планарного графа планарен.

•Задача о трех домах и трех колодцах. Провести от каждого из трех домов дорожки ко всем трем колодцам так, чтобы дорожки не пересекались. Граф этой задачи не является планарным.

•Грань графа — множество всех точек плоскости, каждая пара которых может быть соединена жордановой кривой.

•Граница грани — множество вершин и ребер, принадлежащих грани.

•Всякий плоский граф имеет одну, и притом единственную, неограниченную грань. Эта грань является внешней гранью графа, остальные — внутренние.

•Теорема Эйлера. Для всякого связного плоского графа n-m+f=2, где n — число вершин, m — число ребер, f — число граней.

•Подразбиение ребра — удаление ребра и добавление двух новых, инцидентных вершинам удаленного ребра и соединенных между собой новой вершиной.

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

•Теорема Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K5 и K3,3.

Деревья и лес

•Дерево — связный граф без циклов.

•Лес (или ациклический граф) — неограф без циклов (может быть и несвязным).

•Теорема. Для неографа G с n вершинами без петель следующие условия эквивалентны:

1.G — дерево;

2.G — связный граф, содержащий n-1 ребро;

3.G — ациклический граф, содержащий n-1 ребро;

4.Любые две несовпадающие вершины графа G соединяет единственная цепь.

5.G — ациклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.

•Остов (каркас) связного графа — дерево, содержащее все вершины графа. Определяется неоднозначно.

•Редукция графа — остов с наибольшим числом ребер.

•Цикломатическое (или циклический ранг) число графа ν=m- n+c, где n — число вершин, m — число ребер, c — число компонент связности графа.

•Коциклический ранг (или коранг) ν*=n-c.

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

•Неограф G является лесом тогда и только тогда, когда ν(G)=0.

•Неограф G имеет единственный цикл тогда и только тогда, когда ν(G)=1.

•Остов неографа имеет ν* ребер.

•Ребра графа, не входящие в остов, называются хордами.

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

Определение. Граф G – это математический объект, состоящий из множества вершин X = {x1, x2, ..., xn} и множества ребер A = {a1, a2,..., an}. Таким образом, граф полностью определяется совокупностью множеств X, A: G = (X, A).

Существуют два основных вида графов (и множество их подвидов):

ориентированные и неориентированные.

Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентированного графа называются дугами. Соответствующие вершины ориентированного графа называют началом и концом. Если направления ребер не указываются, то граф называется неориентированным (или просто графом).

Определение. Граф называется простым, если каждую пару вершин соединяет не более чем одно ребро.

Определение. Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным.

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

Определение. Граф, содержащий кратные ребра, называется

мультиграфом.

Неориентированное ребро графа эквивалентно двум противоположно направленным дугам, соединяющим те же самые вершины.

Ребро может соединять вершину саму с собой. Такое ребро называется петлей.

Определение. Граф с кратными ребрами и петлями называется псевдографом.

Определение. Две вершины называются смежными, если они инцидентны одному и тому же ребру. Два ребра называются смежными, если они имеют общую вершину.

Определение. Степенью вершины графа называется число ребер, инцидентных этой вершине.

Вершина, имеющая степень 0, называется изолированной, а степень 1

– висячей.

Определение. Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа.

Определение. Граф G = (X, A) – полный, если для любой пары вершин xi и xj существует ребро (xi, xj).

Определение. Граф G = (X, A) – симметрический, если для любой дуги (xi, xj) существует противоположно ориентированная дуга (xj, xi).

Определение. Граф G = (X, A) – планарный, если он может быть изображен на плоскости так, что не будет пересекающихся дуг.

Теория автоматов

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

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

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

Слово — строка символов, создаваемая через конкатенацию (соединение).

Алфавит — конечный набор различных символов (множество символов)

Язык — множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным.

Автоматы

Автоматы могут быть детерминированные и недетерминированные.

Детерминированный Конечный Автомат (ДКА) — последовательность (кортеж) из пяти элементов , где:

• — множество состояний автомата

• — алфавит языка, который понимает автомат

• — функция перехода, такая что

• — начальное состояние

• — множество конечных состояний.

Недетерминированный Конечный Автомат (НКА) — последовательность (кортеж) из пяти элементов , где:

• — множество состояний автомата

• — алфавит языка, который понимает автомат

• — отношение перехода,

, где — пустое слово. То есть, НКА может совершить скачок из состояния q в состояние p, в отличие от ДКА, через пустое слово, а также перейти из q по a несколько состояний (что опять же в ДКА невозможно)

• — множество начальных состояний

• — множество конечных состояний.

Слово

Автомат читает конечную строку символов a1,a2,…., an , где ai Σ,

которая называется входным словом. Набор всех слов записывается как Σ*.

Принимаемое слово

Слово w Σ* принимается автоматом, если qn F.

Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:

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

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

Часть математического аппарата теории автоматов напрямую применяется при разработке лексеров и парсеров для формальных языков, в том числе языков программирования, а также при построении компи-

ляторов и разработке самих языков программирования.

Другое важнейшее применение теории автоматов — математически строгое нахождение разрешимости и сложности задач.

Типовые задачи

•Построение и минимизация автоматов — построение аб-

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

•Синтез автоматов — построение системы из заданных

«элементарных автоматов», эквивалентной заданному автомату. Такой автомат называется структурным. Применяется, например, при синтезе цифровых электрических схем на заданной элементной базе.

Способы задания автомата

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, d, l} , т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l. При этом среди множества A = {a0,a1,…, an} необходимо

выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

Табличный способ.

При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

Строки этих таблиц соответствуют входным сигналам x(t), а столбцы

– состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = d[ ai,xj], в которое автомат перейдет из состояния ai под воздействием сигнала xj; а в таблице выходов – соответствующий этому переходу выходной сигнал yg = l[ ai,xj].

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

алфавит состояний.

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

В этой таблице каждому столбцу приписан, кроме состояния ai, еще и

выходной сигнал y(t) = l(a(t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.

Графический способ задания автомата (задание автомата с помощью графа).

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

— переходам между ними. Две вершины графа ai и as соединяются дугой, направленной от ai к as, если в автомате имеется переход из ai в as, т.е. as = d(ai, xj). В автомате Мили дуга отмечается входным сигналом xj, вызвавшим переход, и выходным сигналом yg, который возникает

при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).

Конечным автоматом называется система <X, Y, Q, Y, Q>, в которой X и Y являются конечными входным и выходным алфавитами, Q

— конечным множеством внутренних состояний, Y(x, q) — функцией переходов и Q(x,q) — функцией выходов.

Как указывалось ранее, Y(x,q) задает порядок преобразования входных символов и состояния автомата на предыдущем такте в состояние на последующем, a Q(x,q) — преобразования входных символов и

Конечные автоматы с выходом. Структурный синтез

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

Полученный таким образом размеченный ориентированный граф называют конечным автоматом с выходом.

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

где — входной алфавит (его элементы — входные символы); —

выходной алфавит (его элементы — выходные символы); — конечное множество состояний конечного автомата с выходом; — выделенное состояние, называемое начальным состоянием конечного автомата с выходом; — выделенное непустое подмножество состояний, каждый элемент которого называют заключительным состоянием

— отображение, называемое функцией выходов конечного автомата с выходом.

Графом (или диаграммой) конечного автомата с выходом называют ориентированный граф, множество вершин которого совпадает с

множеством состояний , а множество дуг определяется так: из вершины (состояния) ведет дуга в вершину (состояние) тогда и

только тогда, когда для некоторого входного символа

(причем, поскольку есть отображение, для каждой пары указанное состояние единственное).

Каждой дуге диаграммы конечного автомата с выходом сопостав-