В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 104
Текст из файла (страница 104)
Уб, 14 УБ У! У2 Уз УБ К У2 К УБ Уб, Чб К У2,14, К, ЧБ У! Уб. 14, К. Уб, УБ К. УБ, У4, К, 14 К, Уз, Уб, К 14» Уз, К У!, УБ, Уг, Уз, Чз, К К У4, У2 Уз К К УеУБ,К,УБ К УБ Уз Уб У! 14. Уб, Ч46 16 11 8 10 8 1! Т 9 Ч1 У2 Уз У4 Уб Чв 0 2 6 1 0 0 3 0 3 2 0 0 8 6 0 3 1 6 Т 2 3 0 1 0 0 0 1 1 0 2 0 0 8 0 4 0 Деревья Риа. 14.3. Дерево 456 Глава 14. Теория графов и поиск путей с минимальной стоимостью Деревья (Ггеез) являются наиболее часто используемым подклассом графов. Д - Деревья находят мпоакество применений в кибернетике и в компьютерных сетях, Й х. иткс приводятся несколько эквивалентных определений деревьев.
+ Дерево представляет собой простой граф, удовлетворяющий следующе шему условию: если 1 ну являются вершинами дерева Т, то вершины 1 и ' соедт у оединяет единственный простой путь. + Простой граф из Ж вершин является деревом, если у него Ж вЂ” 1 ребер н нет циклов. + Простой граф из Жвершин является деревом. если у негоЖ-1 ребер и он является связным. На рис.
14.3 приведен пример дерева. Одна из вершин лерева может быть назначена его карне,и (гоог). Как правило, она иаображается вверху диаграммы. На рис. 14.3 корнем дерева является вершина Кь Под вершиной на одном уровне располагаются вершины, смежные с корнем. Это вершины, которые от корня дерева отделяет расстояние в 1 ребро. Под каждой из этих вершин располагаются вершины, смежные с вершинами первого уровня. Они удалены от корня дерева на расстояние 2. Так продолжается произвольное количество уровней. У каждой вершины, кроме корня, есть единственная родительская (рагепг) вершина, смежная с ней со стороны корня.
У каждой вершины может быть ноль или болыпе дочерних (сЫ!п) вершин, смежных с ней с противоположной стороны от кортик Вершина, не илтеюшая дочерних вершин, называется концевой вершиной, или листом (1еа(). Для удобства корню дерева назначается уровень О. Вершинам, располагающимся непосредственно под корнем, назначается уровень 1. Вершины, являющиеся дочерними по отношению к вершинам уровня 1, образуют уровень 2. Все эти вершины соединены с корнем путями с расстоянием в два ребра. Связующее дерево Прежде чем дать определение важной концепции связующего дерева, нам требуется определение подграфа. Надграгродг (за ьдгар11) графа с называется подмножество вершин и ребер графа 6, выбранное таким образом, что для каждого ребра, входящего в подграф, две инцидентные этому ребру вершины также входят в под- 14.1.
Элементарные понятия теории графов 457 граф. Более формально, граф бу((л, Е") является подграфом графа П(Ъ', Е), если, во-первых, (л 1- (ти Е" <- Е, а во-вторых, для калсдого ребра е', принвдлежащегоЕ" (то есть е' е Е') и инцидентного вершинам а' и тв', выполняется условие а', гвуе Ъд, Подграф Тура фа С называется связующим деревалг (храпи(пп ггее) графа 6, если подграф Т представляет собой дерево п включает в себя все вершины графа Г.' Другими словами, связующее дерево Т создается нз графа С путем удаления из него ребер таким образом, что в графе б исчезают все циклы, но он остается связным. Связность графа сохраняется, пока мы будем удалять по одному ребру из одного существующего цикла. Таким образом, если у нас есть граф, по меньшей мере, с одним циклом, то при удалении одного ребра из этого цикла цикл разрывается, но связность сохраняется.
Повторяя зту операцию, можно удалить все циклы, сохранив при этом связность. Дерево, показанное на рис. 14.3, является связующим для графа, представленного на рис. 14.1. а. В обшелт случае связующее дерево графа не является уникальным.
Например, на рис. 14.4 показаны два других связующих дерева для того же графа'. Риа. 14 4. Связные деревья для графа, показанного ив рис. 14.1 Поиск в ширину для создания связующего дерева Нам может понадобиться найти связующее дерево для имеющегося графа. Эта задача подробно исследоваласгь так как автоматизированные методы поиска связующих деревьев применимы ко мноптм проблемам. В часпюстн, один из наиболее распространенных методов нахождения связующих деревьев известен под назва- ' Дая простоты сравнения с рис.
14.1 деревья, показанные ва рпс. 14.4. ве с<ютветствуют привятоыу соглаюевию, по котороыу корень дерева изооражается наверху. 488 Глана 14. Теория графов н поиск путей с минимальной стоимостью 14.1, Элементарные понятия теории графов 4бо к4 !'5 Дерево включает вершину (1] Дереке включает вершины (1, 2) ~/з )/5 Дерево включает вершины (1, 2, 3, 4) Уа кз Дереео включает еершнны (1, 2, 3) Ча ка к5 Дерево включает еершнны (1, 2, 3, 4, б) р 1/5 ДеРево включает еершнны (1, 2, 3, 4, б, 6) рно. 14нп Поиск е ширину вершин графа, представленного на рнс. 14Л 'Н Не надейтссь, что это сокрашан~а аам не понадобится. Мне нзаесл!а па меньшей мере одна статья.
а которой ага сокрашенне применяется без расшпфрпакн. Теперь аы знаста, чго оно означает. нием поискав ширину (Вгеаг)г)г-Еггз1 5еагс)!, ВЕК!). Как лгы увидим в разделе 14 2 алгоритм нахождения кратчайшего маршрута Дейкстры (()!))сзсга) использует м тод поиска в ширину. В основе метода поиска в ширину лежит идея обработки всех вершин данно а нного ур вня, пр де чем пер йти к едующему ур впю.
В ходе поз!ска мь! разде;яем вершины графа яа множества вершин разных уровней. Начнем с любой вершин!е шины х и назначим ей уровень О. Всем вершинам, смежным с вершиной х, назначается у ся уро вень 1. Пусть Уг!, Къ ..., $ ь являются вершинами уровня й Рассмотрим все вершинь! смежные с вершиной к!!, не находящиеся на уровнях О, 1, 2, ..., г, и назначим этим ве шинам уровень (! + 1).
Затем рассмотрим все вершины, смежные с вершиной ) и, та„ же не принадлежащие уровням О, 1, 2, ..., г; и также назначим этим вершинам уровещ, (г + 1). Будем продолжать этот процесс до тех пор, пока не переберем все вершины Проиллюстрируем этот процесс на примере, а затем рассмотрим алгоритм. Пример поиска связного дерева для графа, показанного на рис. 14.1, а, представлен на рис. 14 5 (для простоты под каждым графом перечисляются только вершины дерева, без ребер), Сначала следует выбрать порядок, в котором будут перебираться вершины графа. Мы будем перебирать вершины по порядку их номеров: кь 1'г, )'з, 'к'.ь 1'ь Уз.
Затем вы ерем берем из них первую вершину и пометим ее как корень дерева. Пусть сначала дерево сос во состоит из этой единственной вершины У! и не имеет ребер. Затем добавим к дереву все ре реву все ребра ()г!, х) и все вершины х; инцидентные этим ребрам. Таким обра- зом, на первом этапе мы добавим к дереву ребра (Рь кг), ()г!, Уз), (Рь 12) и верши- нь! )ги уз, ) о Добавленные на первом шаге элементы образуют первый уровень. На каждом ждем шаге добавляются только еще не входящие в дерево вершины графа и со- ответствующие ребра.
Таким образом гарантируется отсутствие в создаваемом дереве циклов. Повторим эту процедуру для всех вершин уровня 1, рассматривая все верши- ны по очереди и добавляя их к дереву; (г,: ничего, кз. ребра ( $'з ((5), ( км Уз) и вершины К;, 15, $4. -ничего. К этому моменту к дереву оказываются добавленными все вершшгы графа, В противном случае процедура бы повторялась с вершинами уровня 3 и так далее до тех пор, пока к дереву не будут добавлены все вершины графа. На рис. 14.5 каждая добавляемая к лереву вершина изображается черным цве- том, а каждое добавляемое ребро — серым цветом. Перебираемые новые вершины изображаются серым цветом.
Серые вершины образуют своего рода границу меж- ду дер во еревом и остальным графом, являясь кандидатами на добавление. По завер- шении работы алгорить!а затененные ребра образуют связующее дерево. Вот более формальное определение алгоритма ВРИ. На входе алгоритма мы имеем связный граф 6 с пронумерованными вершинами (г!, Рь ..., )'м а на выходе получаем связующее дерево. В алгоритме используется временное множество вершин 5. 1.
Инициализация. Множеству 5 присваивается значение (У!), а дерево представляет собой граф, состоящий из вершины )г! и не имеющий ребер. Вершина )г! назначается вершиной дерева. 2, Добавление ребер. Обрабатываются вершины множества 5 по порядку. Для каждой вершины х из множества 5 обрабатывается каждая смежная вершина у из множества 5 по порядку. Затем к дереву добавляется ребро (х, у), а тшоке вершина у прн условии, что при этом в дереве не возникнет цикла. Если на этом шаге к дереву не добавлено пи одного ребра, работа алгоритма останавливается и результатом становится связующее дерево.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
