Список практических заданий. 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. переходов

	Н	Ч
	qн	qч
	qч	qн
	qн	qч
	qч	qн

 

Задача 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. переходов

	qн	qч
	qч	qн
	qн	qч
	qч	qн

 

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

	qн	qч
	ч	н
	н	ч
	ч	н

 

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