Задачи для самостоятельной работы

Для всех задач граф задан матрицей смежности.

3.7.1. Определить кратчайший путь во взвешенном графе с помощью волнового алгоритма (элемент матрицы - вес соответствующей дуги).

 

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 1

x 2

x 2

x 3

x 3

x 4

x 4

x 5

x 5

x 6

x 6

x 7

x 7

x 8

x 8

 

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 1

x 2

x 2

x 3

x 3

x 4

x 4

x 5

x 5

x 6

x 6

x 7

x 7

x 8

x 8

 

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 1

x 2

x 2

x 3

x 3

x 4

x 4

x 5

x 5

x 6

x 6

x 7

x 7

x 8

x 8

 

 

3.7.2. Найти компоненты связности графа.

 

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 1

x 2

x 2

x 3

x 3

x 4

x 4

x 5

x 5

x 6

x 6

x 7

x 7

x 8

x 8

 

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 1

x 2

x 2

x 3

x 3

x 4

x 4

x 5

x 5

x 6

x 6

x 7

x 7

x 8

x 8

 

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 1

x 2

x 2

x 3

x 3

x 4

x 4

x 5

x 5

x 6

x 6

x 7

x 7

x 8

x 8

 

 

3.7.3. Найти систему независимых циклов графа.

 

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 1

x 2

x 2

x 3

x 3

x 4

x 4

x 5

x 5

x 6

x 6

x 7

x 7

x8

x 8

 

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 1

x 2

x 2

x 3

x 3

x 4

x 4

x 5

x 5

x 6

x 6

x 7

x 7

x8

x 8

 

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 1

x 1

x 2

x 2

x 3

x 3

x 4

x 4

x 5

x 5

x 6

x 6

x 7

x 7

х 8

x 8

 

4. Произвести раскраску графа из предыдущего задания.

 

4. КОНЕЧНЫЕ АВТОМАТЫ

 

Цель данного занятия - освоить язык описания конечных автоматов и приобрести навыки в их анализе и взаимном преобразовании.

Общие положения

 

Конечный автомат [1] - это набор из пяти элементов ,

где - алфавит внутренних состояний;

- входной алфавит (алфавит входных символов);

- выходной алфавит (алфавит выходных символов);

d - функция переходов из состояния в состояние;

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

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