4.2.2. Дерево и лес

Н–граф называется неориентированным деревом (или просто деревом), если он связен и не содержит циклов, а значит петель и кратных ребер.

Дерево – минимальный связный граф в том смысле, что при удалении хотя бы одного ребра он теряет связность не содержащий циклов. Наличие этих двух свойств (связности и отсутствия циклов) позволяет жестко связать число вершин и число ребер: в дереве с n вершинами всегда n-1 ребро.

Лес - несвязный н–граф без циклов; связные компоненты леса являются деревьями. Любая часть леса или дерева также не имеет циклов, т.е. является лесом или деревом. Любая цепь в таком графе – простая, иначе она содержала бы цикл.

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

Вершина v графа G называется концевой или висячей если ее степень . Ребро, инцидентное концевой вершине называется концевым. Если конечное дерево состоит более чем из одной вершины, оно имеет хотя бы две концевые вершины и хотя бы одно концевое ребро.

Ориентация неориентированного дерева осуществляется следующим образом. В дереве G отмечается (выбирается) вершина - так называемый корень дерева G, и все ребра такого дерева с корнем ориентируются от этой вершины – корня. Вершину ребра можно соединить единственной цепью L с корнем . Если эта цепь не содержит ребра , в это ребро вводится ориентация от к , в противном случае – от к . Такая ориентация согласована с ориентацией того же ребра, определенной через вершину .Данная ориентация дерева с корнем единственна. Ориентированное таким образом дерево с корнем называется ориентированным деревом. В нем все ребра имеют направление от корня. При выборе другой вершины – корня получаем другой орграф – дерево.

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

Пусть дано конечное дерево G. Вершинами типа 1 называют его концевые вершины. Если из дерева G удалить все вершины типа 1 и инцидентные им концевые ребра, то в оставшемся дереве концевые вершины называют вершинами типа 2 в дереве G. Аналогично определяются вершины типов 3, 4 и т.д. Конечное дерево имеет вершины лишь конечного числа типов, причем число вершин максимального типа равно единице или двум.

Цикломатическим числом конечного н–графа G называется , где - число связных компонент графа; - число его ребер; - число вершин. Цикломатическое число любого конечного н–графа неотрицательно.

Пример 2.

Пусть дан граф типа дерева - на рис. 4.5 Сколько вершин максимального типа имеется в данном графе? Каково цикломатическое число графа? Чему равно цикломатическое число графа , являющегося лесом и представленного двумя одинаковыми деревьями ? Построить ориентированное дерево с корнем , являющимся вершиной максимального типа.

Рис. 4.5. Граф G типа дерево

Типы вершин графа отмечены на рис. 4.6,а, граф содержит две вершины максимального (4 - го) типа.

Рис. 4.6. Граф G типа дерево а) типы вершин, б) ориентированное дерево с корнем .

Цикломатическое число любого дерева . Действительно, число вершин в дереве на единицу больше числа ребер (см. выше), т.е. - = = -1, а число связных компонент графа типа дерева = 1. Таким образом, цикломатическое число любого дерева, в том числе графа , v = 0.

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

Построенное из н–графа G ориентированное дерево с корнем, являющимся вершиной максимального типа 4 (левая вершина – на рис. 3,а, изображено на рис. 3,б.

Вопросы для повторения

1.Маршрут это?

2.В каком случае маршрут называется циклическим?

3.Что представляет собой цепь?

4.В каком случае цепь является простой цепью?

5.Дайте определение Эйлерова цикла?

6.В чем заключается отличие Эйлерова и Гамильтонова циклов?

7.Когда граф называется деревом?

8.Чем являются связные компоненты леса?

9.Вершина называется концевой если?

Резюме по теме

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

Глава 5. Основы теории конечных автоматов

Тема 5.1. Переработка информации с помощью конечных автоматов

Цель: рассмотреть основы теории конечных автоматов.

Задачи:

1. Рассмотреть понятие абстрактного автомата.

2. Выявить способы задания автоматов.

3. Рассмотреть взаимосвязь между автоматами Миля и Мура.

5.1.1. Понятие абстрактного автомата

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

Абстрактный автомат задается с помощью следующей пятерки множеств:

А = { X, Y, S,  , },

где Х = {X₁, X₂ ... X_M} – входной алфавит автомата или множество входных символов;

Y = {Y₁, Y₂ ... Y_N} – выходной алфавит автомата или множество выходных символов;

S = {S₀, S₁ . . . S_K-1} – алфавит или множество внутренних состояний автомата;

S₀ – начальное состояние автомата (в момент времени t = 0).

 – функция переходов;

 - функция выходов автомата.

Автомат называется конечным автоматом, если множества X, Y, S конечны (или счетны).

Автомат функционирует в дискретные моменты времени t = 0, 1, 2 ...n (рис. 5.1).

Рис. 5.1. Конечный автомат

В каждый момент времени автомат находится в одном из состояний из множества S.

Функция переходов  определяет в каждый момент времени t следующее состояние автомата в зависимости от текущего состояния и входного сигнала или символа входного алфавита. Другими словами, функция  каждой паре «состояние – входной сигнал» ставит в соответствие следующее состояние.

: SX  S;  - есть отображение декартова произведения SX в S.

Функция переходов может быть записана следующим образом: S_t+1 = (S_t, X_t ).

Функция выходов  определяет в каждый момент времени t выходной сигнал автомата.

Существует две модели автоматов – автомат Мили и автомат Мура. Они отличаются функцией выходов, которая определяется следующим образом:

Y_t =  (S_t , X_t) - для автомата Мили, или : SXY.

Y_t =  (S_t) - для автомата Мура.

В автомате Мили выходной сигнал в момент времени t зависит как от входного сигнала в момент времени t, так и от текущего состояния.

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

Состояние автомата – это память автомата о прошлых входных воздействиях.

Автоматы также называют последовательностными машинами (Sequential Machines), так как входная последовательность преобразуется в последовательность состояний и выходную последовательность.

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

Слово или цепочка – это конечная последовательность символов (букв) входного алфавита. Должны выполняться следующие условия (условия автоматности):

1. Длины входных и выходных слов одинаковы;

2. Одинаковым начальным отрезкам входных слов соответствуют одинаковые начальные отрезки выходных слов.

Пример 1.

Автомата - последовательный сумматор (рис. 5.2). На вход сумматора поступают одноименные разряды слагаемых a_i и b_i, на выходе формируется разряд суммы S_i. Последовательный сумматор является автоматом с памятью – он должен помнить, был или не был перенос из i-1 разряда.

Рис. 5.2. Последовательный сумматор

Входной алфавит автомата X = {00, 01, 10, 11}, выходной алфавит автомата Y = {0,1}, алфавит состояний автомата S = {0,1}.

Состоянию “0” соответствует отсутствие переноса, состоянию “1” - наличие переноса.

Граф переходов автомата имеет следующий вид (рис.5.3).

Рис. 5.3. Граф переходов последовательного сумматора

Таблица 1. Задание последовательного сумматора

X S	00	01	10	11
0	0/0	0/1	0/1	1/0
1	0/1	1/0	1/0	1/1