Ярусно-параллельная форма графов

Граф, не имеющий контуров, может быть представлен в ярусно-параллельной форме. Ярусно-параллельная форма – это такой вид графа, у которого в верхний нулевой ярус помещены вершины, имеющие только исходящие дуги; в нижний ярус помещены вершины, имеющие только входящие дуги. На k -том ярусе помещены вершины, которые имеют входящие дуги из предыдущих ярусов, среди которых хотя бы одна дуга из (k-1)- того яруса.

Количество вершин в ярусе определяет ширину яруса. Наибольшая ширина яруса определяет ширину графа в ярусно-параллельной форме. Количество ярусов определяет высоту графа в ярусно-параллельной форме.

 

Алгоритм приведения графа к ярусно-параллельной форме.

1. Составляется матрица смежности графа.

2. Матрица смежности просматривается в поисках нулевых столбцов. Вершины, которым соответствуют нулевые столбцы, помещаются в нулевой ярус.

3. Из матрицы смежности столбцы и строки, соответствующие вершинам нулевого яруса.

4. Повторяется п.2 данного алгоритма до тех пор, пока не будут охвачены все вершины.

5. По исходной матрице смежности восстанавливаются дуги между вершинами.

 

ПРИМЕР

Привести граф к ярусно-параллельной форме.

 

 

Рис. 3.8 Граф

 

1. Матрица смежности имеет вид:

 

 

2. В нулевой ярус помещаются вершины 3 и 8.

3. Из матрицы смежности вычеркиваются строки и столбцы, соответствующие вершинам 3 и 8:

 

 

4. В первый ярус помещаются вершины 4 и 5.

5. Из матрицы смежности вычеркиваются строки и столбцы, соответствующие вершинам 4 и 5:

 

 

6. Во второй ярус помещается вершина 1.

7. Из матрицы смежности вычеркиваются строка и столбец, соответствующие вершине 1:

 

8. В третий (последний) ярус помещаются вершины 2,6 и 7.

Таким образом, граф может быть представлен в ярусно-параллельной форме:

 

Рис. 3.9 Граф

 

Высота графа - 4 яруса; ширина -3.

 

Деревья и леса

Отделенными называются вершины, для которых не существует соединяющего эти вершины пути.

Неотделенными называются вершины, между которыми существует путь.

Подграфом графа называется граф вида:

(3.19)

Компонентой связности называется подграф, порождаемый множество неотделенных вершин.

 

ПРИМЕР

 

На рис. 3.10 представлен граф, имеющий две компоненты связности {1,2,3,4} и {5.6}

 

 

Рис. 3.10 Граф

 

Связанным графом называется граф, имеющий одну компоненту связности.

Дерево – связный неориентированный граф, в котором отсутствует цикл.

На рис. 3.11 представлены графы- деревья.

 

 

 

Рис. 3.11 Граф

Лесом называетсяграф, имеющий несколько компонентов связности, причем каждая из компонент является деревом.

Цикломатическим числом (g) графа называется минимальное количество ребер, которое необходимо изъять из графа, чтобы он стал деревом. Цикломатическое число определяется по формуле:

, (3.20)

где N – количество ребер,

k – количество вершин.

 

 

Алгоритм получения дерева из графа

 

1. Выбирается любая вершина. Счетчик i принимаем равным 1 (i=1).

2. Если i = k, то дерево построено.

3. Если i ¹ k, то выбирается любая незадействованная вершина и ребро, соединяющее данную вершину с любой из выбранных.

4. Счетчик увеличивается на единицу.(i= i+1).

5. Переход на пункт 2.

 

ПРИМЕР

Преобразовать граф, представленный на рис. 3.12 в дерево:

 

Рис. 3.12

 

1. Найдем цикломатическое число , т.е. необходимо изъять 4 ребра.

2. Выбираем вершину 5.

3. Присоединяем вершину 3.

4.

5. Присоединяем вершину 4.

6.

7. Присоединяем вершину 1.

8.

9. Присоединяем вершину 2.

10.

11. Все вершины охвачены. Дерево построено

 

 

Рис. 3.13

ТЕОРИЯ АЛГОРИТМОВ

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

Алгоритм обладает следующими характеристиками:

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

2. Детерминированность. Система величин, получаемых в какой-то не начальный момент, однозначно определяется системой величин, полученных в предшествующие моменты времени.

3. Элементарность шагов алгоритмов. Закон получения последующей системы величин из предшествующих должен быть простым.

4. Массовость алгоритма. Начальная система величин может выбираться из некоторых потенциально бесконечного множества. Иначе говоря, алгоритм должен обеспечивать решение некоторому множеству (классу) задач с различными параметрами(коэффициентами).

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

Основная задача теории алгоритмов – это решение проблемы алгоритмическойразрешимости, а не поиск правила (способа/метода) ее решения. Теория алгоритмов дает ответ на вопрос «Данная задача имеет решение?», и не отвечает на вопрос «Как решается данная задача?»

В рамках такого подхода к определению понятия алгоритма можно определить три основных направления:

1. Первое направление связано с уточнением понятия эффективно вычисляемой функции. В результате был выделен класс так называемых рекурсивных функций.

2. Второе направление связано с машинной математикой. Здесь сущность понятия алгоритма раскрывается путем рассмотрения процессов, осуществляемых в машине. Впервые это было сделано Тьюрингом, который предложил общую и вместе с тем самую простую концепцию вычислительной машины. Ее описание было дано Тьюрингом в 1937 г. А это направление в теории алгоритмов получило название - машина Тьюринга.

3. Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым. х Нормальные алгоритмы Маркова. Это направление получило название нормальные алгоритмы Маркова.

 

Рекурсивная функция

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

Простейшие функции:

1. Функция сохранения нуля (нуль-функция)

(4.1)

2. Функция сдвига

(4.2)

3. Функция-проекция

(4.3)

Правила преобразования функций

 

1. Правило подстановки (суперпозиции)

Пусть даны функции:

Тогда

(4.4)

где g и h являются или простейшими, или выведенными из простейших.

Правило вывода (4.4) означает, что функция получена из функций правилом суперпозиции

 

ПРИМЕР

Функция может быть получена путем применения раз правила суперпозиции на основе функций

, (4.5)

 

2. Правило примитивной рекурсии

Основывается на простейших или выведенных из простейших функциях g и h:

Пусть

Тогда новая функция может быть выведена по правилу:

(4.6)

Следует отметить, что функция зависит от аргументов, функция зависит от аргументов, функция зависит от аргументов. Иначе говоря, правило примитивной рекурсии позволяет получить n + 1 -местную функцию из n -местной и n + 2 - местной функций.

ПРИМЕР

 

Пусть некоторая функция задана правилом рекурсии

Нетрудно заметить, что функция , функция

Вычислим значение функции при .

Нетрудно заметить, что функция выполняет сложение двух чисел и .

3. m - оператор (оператор нахождения наименьшего корня у)

Оператор определяет наименьшее значение у, при котором при фиксированном значении. Принято обозначение

(4.7)

(Читается: «наименьшее такое, что »). Аналогично определяется функция многих переменных:

(4.8)

Для вычисления функции существует следующий алгоритм:

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

2. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу. И т. д.

Если окажется, что для всех функция , то функция считается неопределенной.

 

ПРИМЕР

Дана функция . Необходимо определить при

Таким образом,

 

Функция называется частично рекурсивной, если она получена из простейших функций за конечное число шагов на основе правил подстановки, примитивной рекурсии или m - оператора.

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

Функция называется общерекурсивно й, если она частично рекурсивная и всюдуопределенная.

 

Тезис А. Черча. Если функция является общерекурсивной, то она выполнима, т.е. имеет алгоритм решения.

 

Машина Тьюринга

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

Машина Тьюринга включает в себя:

1. Внешний алфавит - конечное множество символов . В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово. Обычно символ Внешний алфавит - конечное множество символов обозначает пробел.

2. Внутренний алфавит - конечное множество символов . Для любой машины число состояний фиксировано. Два состояния имеют особое назначение - начальное состояние машины, - заключительное состояние (стоп-состояние).

3. Операторы перемещения Т={Л, П, Н}. Л, П, Н – это символы сдвига «влево», «вправо» и «на месте».

4. Бесконечная лента Бесконечная лента характеризует память машины. Она разбита на клеточки. В каждую клеточку может быть записан только один символ из внешнего алфавита.

5. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ

6. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ.

 

 

Рис. 4.1. Функциональная схема машины Тьюринга.

 

7. Программа машины Тьюринга (Р) - совокупность всех команд, Программа представляется в виде таблицы и называется Тьюринговой функциональной схемой.

	a0	a1	a2
q1	а0Пq1	a1Пq1	a2Лq2
q2	а1Пq2	a2Нq0	a0Нq0

 

Таким образом, машина Тьюринга может быть представлена в виде четверки:

(4.9)

Работа машины Тьюринга:

Информация, хранящаяся на ленте, является набором символов из внешнего алфавита. Начальное состояние управляющей головки характеризуется символом внутреннего алфавита . Работа машины складывается из тактов. В течение любого такта машина Тьюринга осуществляет следующие действия: машина Тьюринга находится во внутреннем состоянии , считывает входной символ и по таблице работы совершает операцию сдвига , переходя в состояние , при этом входное слово заменяется на :

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

 

ПРИМЕР

Построить машину Тьюринга, которая будет стирать последнюю единицу в последовательности единиц.

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

 

Проверим работоспособность машины Тьюринга:

1.

2.

3.

4.

5.

Тезис А. Черча. Если функция выполнима, то она всегда может быть представлена в виде машины Тьюринга.