16) Определение понятий «граф», «инцидентность», «смежность», «степень вершины». Примеры.

В математической теории графов и информатике граф — это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

Матрица инцидентности

Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении -ой строки с -м столбцом матрицы записывается:

1

в случае, если связь «выходит» из вершины ,

−1,

если связь «входит» в вершину,

0

во всех остальных случаях (то есть если связь является петлёй или связь не инцидентна вершине)

Данный способ является самым ёмким (размер пропорционален ) для хранения, но облегчает нахождение циклов в графе.

Матрица смежности

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

Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.

• Двумерный массив;

• Матрица с пропусками;

• Неявное задание (при помощи функции).

Степенью вершины v графа G называется число инцидентных ей рёбер, т.е. число рёбер, выходящих из  данной вершины. (В случае псевдографов каждая петля добавляет 2 в степень вершины). Обозначается степень вершины v графа G:  degGv или просто deg v,  если ясно, о каком графе G идет речь.

17) Машины Тьюринга

В реальности такой машины нет, это абстрактный механизм, представляющий собой бесконечную ленту, разделенную на ячейки и считываютще-записывающую головку. Машина работае в соответствии со своей спецификацией (набором правил). Которая определяет поведение машины. Например, можно представить машину с двумя правилами: 1) Если в текущей ячейке записан символ "А" и машина находится в состоянии 1, то нужно записать в ячейку Б и переместиться на один шаг вправо, а состояние изменить на 2. 2) Если в текущей ячейке записан символ "А" и машина находится в состоянии3, то нужно записать переместиться на один шаг вправо, а состояние изменить на 1. Такое правило приведет к тому, что машина заменит на ленте все символы А, стоящие на нечетных местах на Б, а А, стоящие на четных местах оставит без изменения (предполагается, конечно, что в начальном состоянии машина находится в состоянии 1, четность определеняется от текущей позиции и лента заполнена справа символами А). То есть, нельзя рассказать подробно, как работает МТ вообще, только конкретные реализации. Поскольку ее работа зависит от начального состояния "головки", состоянием ленты и "программы", представленной в виде правил перехода из состояния в сотсояние. Там есть еще ньюансы, например детерминированность, множество лент и т.п. Так не обЪяснишь в 2-х словах, возникает много сопутствующих вопросов, требующих обЪяснения, но в принципе как-то так.

В состав машины Тьюринга входит бесконечная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано. Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные. Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма. Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.