Критерий же существования гамильтонова цикла В произвольном графе еще не найден .

 

Рис.10. Гамильтонов Рис.11. Полугамильтонов Рис.12. Не гамильтонов              граф                                  граф                                        граф

Рассмотрим несколько достаточных условий существования гамильтоновых циклов в графе.

1) всякий полный граф является гамильтоновым. Действительно, он содержит такой простой цикл, которому принадлежат все вершины данного графа.

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

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

 

Не является гамильтоновым и граф, представляющий собой простой цикл с "перекладиной", на которой расположены одна или несколько вершин

Примеры выполнения заданий

7)

1. Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо "красный", либо "синий" граф не является плоским.

Решение:

Пусть оба эти графа - плоские. Тогда у них вместе не более, чем
(3 · 11 - 6) + (3 · 11 - 6) = 54 ребра. Однако в полном графе с 11 вершинами 55 ребер. Противоречие.

2. Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5, - не плоский.

Решение:

Не выполняется неравенство 3V - 6 ≥ E.

3. Семиугольник разбит на выпуклые пяти- и шестиугольники, причем так, что каждая его вершина является вершиной по крайней мере двух многоугольников разбиения. Докажите, что число пятиугольников разбиения не меньше 13.

Решение: Докажите сначала неравенство E £ 3V - 6, используя то, что из каждой вершины выходит по крайней мере 3 ребра. Обозначим количество пятиугольников через a, количество шестиугольников через b.

Заметим, что 5a + 6b + 7 = 2E £ 6F – 12 = 6(a + b + 1) – 12. Отсюда a ³ 13.

4. Граф задан геометрически. А) Определите, содержит ли данный граф гамильтонов цикл? Б) Выпишите гамильтонов цикл у данного графа, если он есть:

Решение:

А) да, содержит, т.к. граф – полный и не содержит перекладин и висячих вершин.

Б) гамильтонов цикл выделен сплошной линией: (1,2), (2,3), (3,4), (4,5), (5,1).

Задания для самостоятельного выполнения

 

Запишите: 1) любой путь, не являющийся цепью; 2) цепь и простую цепь; 3) цикл, простой цикл, если таковые имеются.

Можно ли нарисовать картинки, не отрывая карандаша от бумаги и проводя каждую линию ровно один раз? Какие из них являются эйлеровыми графами?

0)	1)	2)
3)	4)	5)
6)	7)
8)	9)

 

3. Граф задан геометрически. Выпишите гамильтонов цикл у данного графа, если он есть:

Решение:	Решение:
Решение:	Решение:
Решение:	Решение:
Решение:	Решение:
Решение:	Решение:

Практические занятия №13,14  Автоматы

 

Элементы теории

 

Система A=(X;Q;Y;j;y) называется конечным автоматом,
где

X = {a1,…,am}	- входной алфавит с входными сигналами,
Q = {q1,…,qn}	- множество состояний,
Y = {b1,…,bp}	- выходной алфавит с выходными сигналами,
j: X ´ Q ® Q	- функция переходов, т.е. j(x, q) ÎQ "xÎX; "qÎQ,
y: X ´ Q ® Y	- функция выходов, т.е. y(x, q) Î Y "xÎX; "qÎQ.

 Существуют следующие способы задания автоматов:

- с помощью таблицы. Функции j и y задаются таблицей, строки которой соответствуют буквам входного алфавита, а столбцы – состояниям. В пересечении строки a_j и столбца q_i помещается состояние
y (a_j, q_i), в которое переходит автомат из состояния q_i под воздействием входного символа a_j, и значение j (a_j, q_i), которое при этом появляется на выходе;

- в виде диаграммы. Состояния q_i изображаются на плоскости кружками, из которого проводится стрелка в q_u, если автомат, находящийся в состоянии q_i, при подаче некоторого входного символа может быть переведен в состояние q_u;

- совокупностью четверок вида:  q_ia_j ® q_la_p,. Если на вход автомата, находящегося в состоянии q_i, в момент времени t подается символ a_j, то на выходе автомата в этот же момент времени появляется символ a_p, и в следующий момент времени t+1 автомат будет находиться в состоянии q_l.

- в виде системы булевых функций. Каждому q_j ÎQ взаимно-однозначно ставится в соответствие двоичная последовательность длины r - двоичный код a(q) = z₁z₂…z_r. Аналогично каждому a_iÎX и каждому b_k ÎY ставим взаимно-однозначно в соответствие двоичные последовательности b(a) = x₁x₂…x_k; g(b) = y₁y₂…y_s.В результате автомат будет задан системой булевых функций {j₁,j₂,…,j_r,y₁,y₂,…,y_s};

- в виде канонических уравнений. Если в момент времени t=1,2,… на вход автомата A=(X; Q; Y; j; y) последовательно подаются входные символы x(t)ÎX и при этом автомат находится в состоянии q(t)ÎQ, то под воздействием символа x(t) автомат перейдет в новое состояние q(t+1)ÎQ и выдаст выходной сигнал y(t). Величины x(t), y(t), q(t), q(t+1) связаны между собой следующими каноническими уравнениями:

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

Задачи анализа автоматов

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

Примеры выполнения заданий

1. Работа автомата задана таблично и выдает на выходе символ “*”, всякий раз, когда во входном алфавите встречается цепочка из комбинаций символов 0, 1, 2. Опишите работу автомата с помощью совокупности четверок. X = {0, 1, 2}, Y = {0, 1, 2} и Q = {q₀, q₁, q₂, q₃}. Определите, что распознает автомат.

 

Символы алфавита	С о с т о я н и я
	q0	q1	q2	q3
0	q1,1	q2,1	q0,0	q0,0
1	q0,1	q0,1	q0,1	q0,1
2	q0,2	q0,2	q3,1	q0,*

Решение:

q00® q11 q01® q01 q02® q02

q10® q21 q11® q01 q12® q02

q20® q00 q21® q01 q22® q31

q30® q00 q31® q01 q32® q0*

Автомат распознает цепочку вида: 1111*

2. Описание автомата - двоичного сумматора последовательного действия задано с помощью совокупности четверок. X = {00, 01, 10, 11}, Y = {0, 1}, Q = { q ₀, q ₁ }. Опишите работу автомата с помощью диаграммы.

q 0 <0,0> → q00 q 0 <0,1> → q01 q 0 <1,0> → q01 q 0 <1,1> → q10

q1<0,0> → q01 q1<0,1> → q10 q1<1,0> → q10 q1<1,1> → q11

Решение.

q1    (00,0)Ú(01,1)Ú(10,1)         (01,0)Ú(10,0)Ú(11,1)                                  (11,0)      q1   q0                                      (00,1)

Задания для самостоятельного выполнения

1. Работа автомата задана с помощью совокупности четверок и выдает на выходе символ “ * ”, всякий раз, когда во входной последовательности алфавита { a, b } встречается цепочка символов. Определите, что распознает автомат. Опишите работу автомата таблично.

0)

q0b → q0b q0a → q1a

q1b → q2b q1a → q0b

q2b → q3b q2a → q0b

q3b → q0b q3a → *

1)

q0b → q1b q0a → q0b

q1b → q0b q1a → q2a

q2b → q3b q2a → q0b

q3b → q0b q3a → *

2)

q0a → q1a q0b → q0a

q1a → q2a q1b → q0a

q2a → q0a q2b → q3b

q3a → q0a q3b → *

3)

q0b → q1b q0a → q0b

q1b → q2b q1a → q0b

q2b → q0b q2a → q3a

q3b → q0b q3a → *

4)

q0a → q1a q0b → q0a

q1a → q2a q1b → q0a

q2a → q3a q2b → q0a

q3a → q0a q3b → *

5)

q0b → q1b q0a → q0b

q1b → q2b q1a → q0b

q2b → q3b q2a → q0b

q3b → q0b q3a → *

6)

q0a → q0a q0b → q1b

q1a → q0a q1b → q2b

q2a → q0a q2b → q3b

q3a → q0a q3b → *

7)

q0b → q0b q0a → q1a

q1b → q0b q1a → q2b

q2b → q0b q2a → q3b

q3b → q0b q3a → *

8)

q0a → q1a q0b → q0b

q1a → q0a q1b → q2b

q2a → q3a q2b → q0b

q3a → q0a q3b → *

9)

q0a → q0a q0b → q1b

q1a → q2a q1b → q0a

q2a → q3b q2b → q0a

q3a → q0a q3b → *

Решение:

Символы алфавита	С о с т о я н и я
	q0	q1	q2	q3
a
b

2. Работа автомата задана таблично и выдает на выходе символ “&”, всякий раз, когда во входном алфавите встречается цепочка символов. Определите, что распознает автомат. Опишите работу автомата с помощью совокупности четверок.

0)

Символы входного алфавита	Состояния
	q0	q1	q2	q3
О	q0,О	q2,О	q0,О	q0,О
К	q1,К	q0,О	q0,О	q0,О
Т	q0,О	q0,О	q3,Т	q0 &

1)

Символы входного алфавита	Состояния
	q0	q1	q2	q3
С	q0,С	q2,С	q0,С	q0,С
О	q1,О	q0,С	q0,С	q0,С
А	q0,С	q0,С	q3,А	q0 &

2)

Символы входного алфавита	Состояния
	q0	q1	q2	q3
М	q0,М	q0,М	q3,М	q0 &
А	q0,М	q2,А	q0,М	q0,М
С	q1,С	q0,М	q0,М	q0,М

3)

Символы входного алфавита	Состояния
	q0	q1	q2	q3
А	q0,А	q2,А	q0,А	q0,А
Д	q1,Д	q0,А	q0,А	q0,А
Р	q0,А	q0,А	q3,Р	q0 &

4)

Символы входного алфавита	Состояния
	q0	q1	q2	q3
О	q0,О	q2,О	q2,О	q0,О
Р	q1,Р	q0,О	q2,О	q0,О
М	q0,О	q0,О	q3,М	q0 &

5)

Символы входного алфавита	Состояния
	q0	q1	q2	q3
Р	q0,Р	q0,О	q3,Р	q0 &
М	q1,М	q0,О	q0,О	q0,О
И	q0,Р	q2,И	q0,О	q0,О

6)

Символы входного алфавита	Состояния
	q0	q1	q2	q3
А	q0,А	q2,А	q0,А	q0А
П	q1,П	q0,А	q0,А	q0,А
Р	q0,А	q0,А	q3,Р	q0 &

7)

Символы входного алфавита	Состояния
	q0	q1	q2	q3
М	q0,М	q0,М	q3,М	q0 &
И	q0,М	q2,И	q0,М	q0,М
Р	q1,Р	q0,М	q0,М	q0,М

8)

Символы входного алфавита	Состояния
	q0	q1	q2	q3
Р	q0,Р	q0,Р	q3,Р	q0 &
У	q0,Р	q2,У	q0,Р	q0,Р
Т	q1,Т	q0,Р	q0,Р	q0,Р

9)

Символы входного алфавита	Состояния
	q0	q1	q2	q3
Л	q0,Л	q2,Л	q0,Л	q0,Л
Т	q1,Т	q0,Л	q0,Л	q0,Л
Я	q0,Л	q0,Л	q3,Я	q0 &

 

3.Работа автомата задана с помощью диаграммы и выдает на выходе символ “*", всякий раз, когда во входном алфавите встречается цепочка символов. Определите, что распознает автомат. Опишите работу автомата с помощью совокупности четверок

0)

    (б, б)              (К, б) Ú (б, *)

q0

q1

 

 

                                       (К, К)