Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
поступить аналогичным образом. В результате получим последовательность
разных вершин, которая не может бесконечно увеличиваться-обязательно
наступит повторение вершин, а это означает, что в графе существует цикл.
Если удалить висячую вершину из дерева, состоящего из I V\ вершин и \Е\
ребер, то останется дерево, состоящее из
I V\ - 1 вершины и \Е\ - 1 ребра. Продолжая этот процесс удаления,
прийдем в конце концов к тривиальному дереву из одной вершины. Таким
образом, любое дерево удовлетворяет условию
ребро. Допустим, что существует цикл, содержащий это ребро. Тогда
существует путь из s в i, не проходящий через ребро е. Поэтому можно
удалить это ребро из графа, не нарушая связности. Продолжая этот процесс,
прийдем в конце концов к связному подграфу без циклов с тем же множеством
V вершин, т.е. к дереву. Такой подграф называется остовным деревом графа
или остовом. Ясно также, что равенство
выполняется только для деревьев. У произвольного графа, не являющегося
деревом, число ребер больше:
Существует простой алгоритм для нахождения остова. Мы рассмотрим даже
более общую задачу о минимальном остове, когда каждому ребру поставлено в
соответствие некоторое неотрицательное число (расстояние) и требуется
найти остов с минимальным суммарным расстоянием.
m = \е\ + 1.
Пусть теперь G-произвольный связный граф,
m = \е\ + 1
\е\ > m - 1.
60
Можно представить себе проектируемую телевизионную кабальную сеть для
района-новостройки, где для каждого ребра указано расстояние в км:
ТВ-цен
2
Кажется естественным осуществлять реализацию этого плана поэтапно:
вначале соединить все пункты минимальной сетью, а затем наращивать
дополнительные связи.
Начинаем поиск остовного дерева с произвольной вершины, скажем, с 1.
Находим все ребра, выходящие из этой вершины, и выбираем ребро с
минимальным расстоянием:
Теперь просматриваем все ребра, входящие в множество {1,2}, и находим
минимальное ребро:
Продолжая этот процесс, получаем в конце остовное дерево с минимальным
суммарным расстоянием R = 20 км:
4.4. Ордерево. Иерархические структуры
Ориентированный граф (орграф) называется ордеревом, если граф, получаемый
при игнорировании ориентации дуг, является деревом.
Аналогично поступаем с множеством {1, 2, 5}:
42)
Gf
6i
Пример ордерева:
(Й
(М
@ (?)
В таком графе отсутствуют циклы и закорачивания-нельзя, например, из
вершины а провести дугу в вершину d (используя терминологию предыдущей
главы, мы получили бы транзитивную зависимость, которая при игнорировании
ориентации приводила бы к циклу (a, Ъ, d)).
В ордереве в каждую вершину, кроме одной, которая называется лидером или
корнем, входит ровно одна дуга.
Ордерево описывает обычно иерархическую структуру (отношение
подчиненности). Представленное на рисунке дерево называют деревом,
выходящим из корня а. Можно изменить ориентацию каждой дуги на
противоположнуюо. Тогда получится дерево, входящее в корень а. Все пути в
таком графе заканчиваются вершиной а.
Чтобы найти остовное дерево, выходящее из вершины а для заданного орграфа
(или же определить, что его не существует), поступаем так же, как и в
неориентированном случае.
Пусть, например, задан орграф:
Выбираем какое-либо ребро, выходящее из вершины а:
Теперь находим ребро, выходящее из множества {a, d):
То же самое проделаем для множества {а, Ь, с} и т. д.:
Таким образом, существует остовное дерево, выходящее, из вершины а.
В то же время не существует остовного дерева, выходящего из вершины /:
Дальнейшее продолжение невозможно, так что вершину а мы не можем
присоединить к данному дереву.
Это можно было предвидеть заранее-в вершину а не входит ни одна дуга
(такая вершина называется корневой). Таким образом:
Если в орграфе присутствует корневая вершина, то любое остовное дерево
может выходить только из этой вершины.
Если в орграфе присутствует больше одной корневой вершины, то не
существует остовного дерева.
Компактная запись ордерева в памяти компьютера осуществляется с помощью
слов х <8> у.
xia а а с d А у\Ь с d f е g\'
Чтобы узнать, что х (r) у действительно соответствует некоторому ордереву,
нужно подсчитать общее число различных букв в обоих словах. Это число
равно числу вершин графа:
IVI =7.
63
Затем следует сравнить это число с длиной слова, которая совпадает с
числом ребер:
IE I =6.
Если выполняется соотношение
m = \е\ + 1,
то заключаем, что х <8> у определяет ордерево.
4.5. Бинарный поиск
Пусть R = {а, b, с, ...}-множество из N. элементов. Допустим, что
относительно некоторого объекта х известно лишь, что он является
элементом множества R. Требуется идентифицировать этот объект, т.е.
установить, какой букве он соответствует. В простейшем случае можно по
очереди выполнить сравнения
х = а? х = А?, ... ,
пока не получим положительный ответ. Очевидно, в этом случае может
потребоваться N сравнений. Ускорить поиск можно, разбивая R на два
непересекающихся подмножества:
R = А + А, А С R,
и задавая вопрос:
