Индивидуалка. Графы и автоматы

Индивидуальная работа по теме:

«Графы и конечные автоматы»

Вариант 1.

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

2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

4. Найти минимальную форму автомата и граф переходов минимальной формы:

S
1 2 3 4 5 6	2 3 4 4 5 6	2 3 4 4 6 5	1 1 1 0 1 1	0 0 0 1 1 1

5. Составить программу для машины Тьюринта, вычисляющую значения функции .

Вариант 2.

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

2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

4. Найти минимальную форму автомата и граф переходов минимальной формы:

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

5. Составить программу для машины Тьюринта, вычисляющую значения функции .

Вариант 3.

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

2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

4. Найти минимальную форму автомата и граф переходов минимальной формы:

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

5. Составить программу для машины Тьюринта, вычисляющую значения функции .

Вариант 4.

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

2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

4. Найти минимальную форму автомата и граф переходов минимальной формы:

	0	1	0	1
S0 S1 S2 S3 S4	S1 S4 S3 S4 S4	S2 S2 S0 S0 S4	1 0 1 0 0	0 0 0 0 0

5. Дана последовательность из нулей и единиц. Написать программу машины, которая меняет местами нули и единицы (т.е. вместо нуля должна стоять единица, вместо единицы – нуль).

Вариант 5.

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

2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

4. Найти минимальную форму автомата и граф переходов минимальной формы:

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

5. Составить программу для машины Тьюринта, вычисляющую значения функции .

Вариант 6.

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

2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

4. Найти минимальную форму автомата и граф переходов минимальной формы:

1 2 3 4 5 6	s5 s6 s4 s3 s3 s4	s4 s3 s1 s2 s6 s5	1 1 1 1 0 0	0 0 1 1 1 1

5. Составить программу для машины Тьюринта, вычисляющую значения функции .

Вариант 7.

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

2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

4. Найти минимальную форму автомата и граф переходов минимальной формы:

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

5. Составить программу для машины Тьюринта, вычисляющую значения функции .

Вариант 8.

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

2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

4. Найти минимальную форму автомата и граф переходов минимальной формы:

S
1 2 3 4 5 6	2 3 4 4 5 6	2 3 4 4 6 5	1 0 1 0 1 1	0 0 0 1 1 1

5. На ленте машины Тьюринга написана конечная последовательность из нуля и следующих за ним единиц. Написать программу машины, которая переставляет нуль на последнее место.

Вариант 9.

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

2. Дан граф транспортной сети, – вход, – выход, – пропускная способность дуги. Используя алгоритм Форда-Фалкерсона, найти поток наибольшей величины.

3. По матрице смежности построить граф, определить его характеристики (связность, число компонент связности, длина максимального цикла, эйлерова характеристика).

4. Найти минимальную форму автомата и граф переходов минимальной формы:

1 2 3 4 5	s5 s2 s4 s3 s3	s4 s3 s1 s2 s5	1 1 1 1 0	0 0 1 1 1

5. Составить программу для машины Тьюринта, вычисляющую значения функции .

Вариант 10.

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