дискретная-математика - Задачи на графы

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

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

В задаче 4 надо нарисовать 5 точек-вершин (по числу строк) и 11 ориентированных рёбер (по числу столбцов). Первому столбцу соответствует ребро, выходящее из первой вершины (число 1 в первой строке) и входящее в 4-ю вершину (число -1 в четвёртой строке). Далее нужно выяснить, за какое минимальное число шагов можно из любой вершины пройти в любую другую -- это и будет диаметр графа. Здесь, правда, надо уточнить определение: имеется ли в виду, что ориентация на графе учитывается, или же диаметр понимается как диаметр обычного графа.