Промышленный лизинг Промышленный лизинг  Методички 

1 2 3 4 5 6 7 8 9 [ 10 ] 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

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

Известен простой алгоритм построения подобного обхода в тех ситуациях, когда этот обход возможен [4].

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

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

Гамильтон показал, что для додекаэдра эти числа равны [5]. Однако описать все множество графов, допускающих существование путей, перемещаясь по которым можно обойти все узлы, побывав в каждом ровно один раз, не удалось до сих пор. Нет и эффективного алгоритма.

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

С этой задачей тесно связана проблема моряка, часто называемая также задачей о странствующем торговце (коммивояжере), который должен посетить определенный набор городов и вернуться домой как можно скорее. Довольно большой пример определения замкнутой воздушной линии, соединяющей столицы 48 штатов США и имеющей наименьшую возможную длину, был просчитан до конца [6].

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

Важный класс графов составляют графы, называемые деревьями. Дерево - это связный граф, который вовсе не имеет замкнутых путей (рис. 4).

Этот граф обладает следующим оптимальным свойством: среди всех связных графов с данным числом вершин дерево имеет наименьшее число ребер, а именно:

число Квершин дерева и число £его ребер различаются на единицу

Справедливо и обратное утверждение:

V=E + l,




Рис. 4

если число вершин связного графа на единицу больше числа его ребер, то этот граф является деревом.

Если граф - конечный и связный, то легко построить дерево (и, как правило, не одно), множество вершин которого совпадало бы с множеством всех вершин заданного графа, а все ребра дерева одновременно были бы ребрами этого графа.

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



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

На рис. 5 последовательно (шаг за шагом) показано построение порождающего дерева для графа с семью вершинами.


Рис. 5д Рис. 5е

Ясно, что порождающих деревьев у конечного связного графа может быть много. В частности, если граф - полный (любые две вершины соединены ребром), то число порождающих деревьев равно пп~2, где л- число его вершин [7].



1 2 3 4 5 6 7 8 9 [ 10 ] 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92