3.7 Деревья и леса.

Связный граф без циклов называется деревом.

Граф без циклов называется лесом.

Теорема. T(V,E) - дерево тогда и только тогда, когда T(V,E) - связный граф и |E|=|V| - 1.

Теорема. В любом дереве имеется не менее двух висячих вершин.

3.8 Цикломатическое число графа. Построение

Остовного дерева связного графа.

Остовным деревом связного графа G(V,E) называется любой его подграф, содержащий все вершины G и являющийся деревом.

На рисунке приведены два графа G и по одному из их остовных деревьев T.

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

Теорема. Цикломатическое числом графа G(V,E) не зависит от последовательности удаления ребер и имеет место формула:

= |E|| - |V|+k(G),

где k(G) - число компонент связности.

4.1 Понятие конечного детерминированного автомата

Автоматы можно рассматривать как механизмы, состоящие из:

• блока управления, который может пребывать в различных состояниях (S внутренний алфавит);

• входного канала;

• выходного канала.

Входной канал считывает входные сигналы (Х) из внешней среды. Выходной канал выдает выходные сигналы (Y) во внешнюю среду. Работа автомата протекает в дискретные такты времени t=1,2,3,…. По команде   в некотором такте времени   блок управления установлен в состоянии   и входной канал воспринимает  , тогда в этом же такте   в выходной канал выдается символ  , а к следующему такту  +1 блок управления перейдет в состояние  .

Определение. К.Д.А. называется система  , где    алфавит состояний,  – входной алфавит,  – выходной алфавит. Множества S, X, Y – конечные.

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

 – функция выходов.

Если в автомате выделено одно состояние , называемое начальным (обычно  ), то автомат называется инициальным.

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

1. Таблица переходов–выходов.

   S\X		…		…
   
   

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

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

3. С помощью канонических уравнений:

в момент t=1 автомат находится в начальном состоянии  . В каждый момент t=1,2,3,… дискретного времени автомат, находясь в некотором состоянии s(t) из множества S, под действием входного сигнала   выдает выходной сигнал   из множества Y, согласно функции выходов  , а затем меняет свое состояние на s(t+1) согласно функции переходов .

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

После преобразования входного сигнала   в выходной   его значение к следующему такту времени теряется. Иначе говоря, в любой тактовый момент t в устройстве нет информации о сигналах в предыдущие моменты, то есть о значениях  , ,  ,… . Поэтому, если при вычислении значения функции переходов и выходов по формуле необходима информация об этих тактовых моментах, то ее нужно каким-либо образом "запомнить". В этом и состоит содержательное назначение состояний. Состояния – это вспомогательные объекты, которые подбираются таким образом, чтобы в совокупности с входным значением   однозначно определить выходное значение  . Обычно состояния кодируют ту информацию, которая поступила до момента t.

Пример. Построить таблицу переходов–выходов К.Д.А, реализующего функцию:

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

={"на первом такте поступил 0"};

={"на первом такте поступила 1"}.

И  –начальное состояние.

Построим таблицу переходов–выходов:

  Для   нарисуем диаграмму Мура:

И дополним таблицу переходов–выходов: