Список практических заданий. 2. Задать Графы G1-G3, изображение на рис

1. Равны ли графы - на рис.6.5? Задать графы - множествами их вершин и ребер. Сравнить графы.

2. Задать Графы G1-G3, изображение на рис. ниже матрицами инцидентности и смежности, а также списком ребер.

3. Изобразить граф, соответствующий отношению, представленному следующей матрицей:

R a b c d e a
a
b
c
d
e

4. Имеют ли пятигранник – призма и пятиугольник с петлями в некоторых вершинах гамильтонов цикл (цепь).

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

Вопросы для обсуждения на форуме

1. Решение задач теории графов

Список дополнительной литературы:

1. Берж К. Теория графов и ее применение. М.: Иностранная литература, 1962.

2. Кристофидес Н. Теория графов: алгоритмический подход. М.: Мир, 1978. 432 с.

3. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971.

4. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях \Г.И. Москинова. – М.: Логос. 2000. – 240с.

5. Лекции по теории графов / Емеличев В.А., Мельников О.И., М.: Наука, 1990. 384 с.

Семинар №8. Конечные автоматы

Цель семинара:

Закрепить навыки применения конечных автоматов в деятельности информационного менеджера.

План занятия:

Семинар рассматривает 3 темы: переработка информации с помощью конечных автоматов, детерминированные конечные автоматы и недетерминированные конечные автоматы. На рассмотрение вышеперечисленных тем выделяется 3 часа.

Задача 1. Построить (синтезировать) автомат, на вход которого могут поступать в любой последовательности и, возможно, с любым числом повторений монеты 1,2 и 3 коп. Автомат продает билет, если сумма опущенных монет равна 3. В случае превышения суммы автомат возвращает деньги.

Решение.

Входной алфавит в описании задан явно: X={1,2,3}.

Выходной алфавит будет содержать буквы (сигналы): Б- выдает билет, В- возвращает деньги, Н- ничего не выдает, т.е. Y{Н,Б,В}.

Внутренние состояние будем отождествлять с суммой, которую помнит автомат. Будем иметь в виду, что после продажи билета или возврата денег автомат помнит нулевую сумму: Q={q0, q1, q2}, здесь индекс соответствует сумме.

Автомат в виде графа представлен на рис. 7.1.

Рис. 7.1. Граф автомата выдающего билет

Это автомат Мили. Надпись 1/Б; 2,3/В у стрелки q2q0 означает, что если в состоянии q2 будет принят сигнал 1, выходной сигнал будет Б, а для входных сигналов 2 и 3 выходным будет В. Этот же автомат можно представить в виде двух таблиц: табл. 7.1 и табл. 7.2.

Таблица 7.1. переходов

  q0 q1 q2
q1 q2 q0
q2 q0 q0
q0 q0 q0

Таблица 7.2. выходов

  q0 q1 q2
Н Н Б
Н Б В
Б В В

Задача 2. Построить автомат, на вход которого могут поступать монеты 1, 2 и 3 коп. Автомат выдает сигнал “чет.” (Ч), если сумма опущенных монет четная, и “нечет.” (Н), если нечетная (рис.7.2).

Решение.

Рис. 7.2. Граф автомата четности

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

Таблица 7.3. переходов

  Н Ч
 

Задача 3.Осуществить переход от автомата Мили, заданного табл. 7.4 и табл. 7.5 к эквивалентному автомату Мура.

Таблица 7.4. переходов

  q0 q1 q2
q1 q2 q0
q2 q0 q0
q0 q0 q0

Таблица 7.5. выходов

  q0 q1 q2
Н Н Б
Н Б В
Б В В

Решение.

Перерисуем табл. 7.4, указав в клеточках i j состояния bij синтезируемого автомата Мура (табл. 7.6). Попав в любое из таких состояний, автомат Мура должен обеспечить дальнейшую реализацию прежней функции переходов только уже в ”терминах” состояний автомата Мура, т.е. состояния b0, b03, b12, b13, b21, b22, и b23 должны обеспечить переходы, аналогичные тем, которые имели место для состояния q0 в автомате Мили, b01 -аналогичное q1, а b02 и b11-аналогичные q2.

Таблица 7.6.

  q0/b0 q1 q2
q1 b01 q2 b11 q0 b21
q2 b02 q2 b12 q0 b22
q3 b03 q0 b13 q0 b23

Полученный автомат Мура приведен в табл. 7.7.

Таблица 7.7.

    Н Н Б Н Б В Б В В
  b0 b01 b02 b03 b11 b12 b13 b21 b22 b23
b01 b11 b21 b01 b21 b01 b01 b01 b01 b01
b02 b12 b22 b02 b22 b02 b02 b02 b02 b02
b03 b13 b23 b03 b23 b03 b03 b03 b03 b03

Автомат получился явно избыточным, уменьшить число состояний дело техники. Главное, что он ”работает” точно так же, как и исходный автомат Мили

Задача 4.Осуществить переход от автомата Мура, заданного графом рис. 7.3 к эквивалентному автомату Мили.

Рис. 7.3. Граф автомата Мура

Решение.

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

Рис. 7.4. Граф эквивалентного автомата Мили для автомата Мура рис.7.3

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

Таблица 7.8. переходов

 

Таблица 7.9. выходов

 
ч н
н ч
ч н

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

Наши рекомендации