Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 38
Текст из файла (страница 38)
Если существует маршрут пз и в и, то говорят, что и является предком и», а и»вЂ” потомком и. Эти понятия не имеют смысла для орграфов, имеющих циклы, так как для таких графов вершина может исходять сама из себя. Пример 6.5. Для ацвклического орграфа, изображенного иа рис, 7,25, из вершин из, и» и из ребра не 24В образом: ири», если и в» или существуют маршруты из и в ю и обратно. Если (Ул (<(ар) — разбненне У и (Е».
1» 1< р, а Е ((т Х (т»)О Е) являются соответствующими множествами ребер, то подграфы С (У»,Е,) (1 ~ 1Щ р) называются сильно связными компонентами С. Очевидно, что ршЕь и А(р) может быть определено вз А(Еь) как А(р)0 А(Ее)О Д А(Нь);»1 граф С сильно связный тогда и только тогда, когда С имеет только одну сильно связную компоненту, т. е. есля р 1. Пример 6.4. Для орграфа ва рвс. 7.24 имеем выходят, о~ является предком оз, оз является прямым потомком оз и т. д.
Существует тесная связь мея;ду ацпклическнмн орграфами к частично упорядоченными отношениями. В частности, имеет место следующий результат, доказательство которого мы оставляем в качестве упражнения. Заметим, что для сокращения некоторых доказательств, Рвс. 7.25 приведенных ниже, частичные порядки будут основаны скорее на отношении <, чем на отношении <, и, следовательно, являются трапзнтивными и нерефлексивнымн. П р е д л о ж е н и е. а) Пусть отношение < является частичным отношение.ы порядка на конечном множестее У, Тогда, если Е ((и, в): о<ш), то пара 6 (т', Е) является ациклическим графом.
б) 11усть 0 (У, Е) — ациклическиб орераф и отношение < определяется следующим образом: о< ю, если и является предком и. Тогда отношение < яеляеткя частичным отношением порядка на т', е В терминах орграфов можно дать точнов определение структурам данных, иавестпым как ориентироеанное дерево. Ориентированное дерево Т ( т', Е) — зто вциклическпй орграф, в котором одна вершина о, аз у не имеет предков, а каждая другая вершина имеет только одного непосредственного предка; о, называется корнем дерева.
Бинарное дерево — зто ориентированное дерево, в котором каждая вершина имеет не более двух непосредственных потомков, т. е. б+(о)<2 для всех озз т', Говорят, что бинарное дерево является полным, если каждая вершина, пе являющаяся листом, имеет ровно два пепосредствек пых потомка, 247 Предло женке. Следующие утверждения эквивалентны по отношению к оргрофу С-(т, Е): а) гэ является деревом. б) Граф т'(гэ) свяэный, и существует вершина о„ которая нв имеет предков, а есе другие вершины имеют только по одному непосредственному предку.
в) 0 имеет вершину о„которая соединяется с любой другой ввришной единственным маршрутом. г) О имеет вершину о„которая не имеет предков; все другие вершины имеют только одного непосредственного предка; существует маршрут к каждой вершине иэ и,. доказательство оставляем в качестве упражневпя. гт 6.3.
Упорядоченные орграфы и обходы. Списки смежности являются альтернативной по отношению к матрице смежности формой представления орграфов. Заданное списком смежности представление определяет порядок ребер, вгвходяшнх ка каждой вершины. Определение. Упорядоченным орграфом называется пара С* (У, Е), где У вЂ” конечное множество вершин, а Š— множество упорядоченных списков орнентпрованных ребер. Элементы Е имеют впд Г.-((о, ), ", (, ш.)), где о, ш,жу. э Пр имер 6.6.
Упорядоченный орграФ 0 (Ьь ог, оэ, ов), (((ои ог), (оь ог), (оь о,)), ( (оэ~ ог) е (ог оэ) ) ) ) может быть представлен спнскамп смежности '" Ш-ЕП~ и может быть наображен диаграммой (рнс. 7,26). оэ Рве. 7.26 Упорядоченный орграф б определяет едннственкый неупорядоченньш орграф; мы только вамевнем каждый список ((о, ил!), ..., (о, ил,)) множеством ((о, ил,), ... (о, и~,)). Орграф, определенный таким образом, называют орграфом, подчиненныл! О.
Упорядоченный вциклпческпй орграф является упорядоченным гра4ам, чьим подчиненным орграфом является ацпклпческпй орграф. Упорядоченное ориентированное дерево является упорядоченным орграфои, чей подчиненный орграф явлнется оряентпрованным деревом. П р п и е р 6.7. л ((Р$, ° ° .> об)> (((Р!> РР)> (о$> Рз))> ((оз> г4)> (од иь)> (оз> оа)))) является упорядоченным орпенткрованным деревом, где о! — корень. Оно может быть о> пвображепо, как показано ва 2 рпс.
7.27. Р Упорядоченные орпентпрованные деревья будем пзо- 1 о! бран!ать спуском вершкн 2Э слева направо (рпс. 7.27). Если прпнять такое согла- о ое женое, то помора ребер ол можно опускать. Рпс. >.27 О~ределенпе. 1) Пусть Я» и Яе — мпон",ества. Пометкой упорядоченного оргра4>а 6 (1>„Е) называется пара отображевлй (1, д), где 7': у-~51- — пометка вершин, я: Е- () Ее — пометка ребер. Л 1 Отображенве д имеет впд б(((о> и!) ' ' ("> ил))) (ц! ' ' > с>л) анде' 2) Говорят, что два пол!ечепвых графа О! ° (У1, Е!) п Ст (Ут, Ет) с функциями пометок ((ь д!) п (11, бт) соответственно эквнвалептны, если существует бпекцпя й: У! - $'т такая, что а) ((о, !а!)> ..., (о, илл))!нЕ! тогда п только тогда, 249 когда ((й( ), й(ш )), ° ° ., (й( ), й(го)))'- =Ез (аквпвалентны как упорядоченные графы); б) ~~(и) га(Ь(и)) для всех иш т' (меткп вершнв совпадают); в) для всех ((и, ш1), (и, из), ..., (и, ш,))иЕ1 имеем у~(((и, ш~), ..., (и, ш,) )) ° -угШй(и) й( Л~)), ", (й( ), й(ш.)))) (метки ребер совпадают).
г Следуя $5, определим обход орграфа как перестановку нли полное упорядочивание вершпн. Для упорядоченных орграфов все делается точно так же, Для упорядоченных орпентпровавных деревьев часто полезны другие обходы. Некоторые яа них будут описаны ниже. Определение. Пусть Т ((иь ..., и ), Е) — упорядоченное орпентпроаапное дерево п Е,* ((и, ш~), ... ..., (и, ш,) ) ш Е. Определим отношение < па множестве (шн ..., ги,) следующим образом: ш<<ш, тогда п только тогда, когда г<). Определнм таким обрааом отношение < для каждого списка Е. г' Предложение. Отношение < является отношением частичного порядка на У, Докааательство. Пз соотношения и < и следует список вида ((Ь го ), " , (у, ), " , (у, и) " , И, ь)), который невозможен, так как в дереве не существует цпклов.
Следовательно, и < и для любого и ш У. Иа соотношений и< и н и < я следует, что существуют х, у ш У таяне, что Ь, ((х, ю1), ..., (х, и),..., (х, ш), ..., (х, шь)), Ь„((у, и1), ..., (у, ш), ..., (у, и), ..., (у, и,)). Если хчьу, то б-(го) 2, что невозможно, так как Т— дерево. Следовательно, х у п Е ((х, ш ), „ (х, и), ..., (х, ш), ...
..., (х, и), ..., (х, ш,)), -. е. и < и. Поэтому отношенке < есть частвчпо упорядоченное отношение ва У. г Отношение < сравнивает только вершпны, выходящие вз одной вершпкы. 250 Пример 6.8. Для упорядоченного ориентированного дерева на рис. 7.28 имеем ((ом оз), (ол~ оь)е (оо оь), (оь, оь~) ялп оь< оь, оь<оь, оь<оь и оь<оь. ье 3 а ы е ч а в и е. Ооозначнм множество всех спусков пз вершины о за У через Г+(о); аналогично через Г (о) обозначим множество входов в о. Определепне.
Отношение с нааывают транееереальным нарядном вершин упорядоченного направленного дерева Т (У, Е). е' Наша цель в оставшейся гг оь части главы — вывести рааличные полезные методы обхода для дерева о использованием сиыметрнп путем расширения оь трансверсального порядка. Пе- Рас. 7.26 ред точным определением обходов необходимы два результата, Пусть < определяет отношенве <, ва У следующим образом: если ил< ьоь то юь <,и; для всех ьо; а Г+ (и~ь) ),) (из) и для всех ю;ев яиГ+(иу) (3 (юь). П редложение.
1) <ы<,; 2) <, — частично упорядоченное отноиьение на У. Доказательство. $) Утверждение очевидно. 2) а) Из о с,о следует, что илп оси, или существуют х, уьиу такие, что хсу и оьвГ+(х)0(х и оьв еь Г+(у) 0 (уЕ Однако о < о, так как < — отношение частичного порядка. Аналогично пз х с у следует х чь у; следовательно, оеь Г+(х)0 (х) и оьа Г+(у)0 (у). Однако зто означает, что б (о) 2 или б (и) 2 для некоторого юза Г (о). Это невозможно, потому что Т (7, Е)-дерево.
Таким обрааом, о <,о для всех о ьи у. б) и <,ю означает, что о < и нли что существуют х, уьз У такие, что х<у и оьь Г+(х)0(х) и ьоаь Г+(у)0 0 (у); ьо с,и озпачает, что ьо < и нлп что существуют т, ьж т' такие, что т< з и ьоьь Г+(т)0(г) и иьь Г+(ь)0 0 Ы; ю ьа Г+(г) 0 Ы и ьо ьз Г+(у) 0 (у) дают, что или т ьи Г+(у), нлп у ья Г+(г). Следовательно, дерево имеет одну из форы, пзобра« жевных на рис, 7,29. Если таз Г'(у), то еж Г'(у) я 25ь т ( у дает х <,з. Однако и «е Г+(з), следовательно, т с,и, н так как ие Г+(х), то, следовательно, и<,п.
Если у ш Г+(г), то х«в Г+(г) и г<з дает х<,ю Однако ало 8 Ф' ф Рас. 7.29 п«в Г+(з)0(з); следовательно, х(,п, а и«в Г+(х) дает и (,и. Следовательно, <. является отношением частичного порядка на )г. г" Иногда и (,и читают как «и находится слева от иг«. Предложение. Пусть Т (У, Е) — упорядоченное ооиентироеанное дерево. Тогда для иь и,ш г' (7чь)) или и,(,и„илии,с,и„или лге и, и и, надсадятся на маршруте. Доказательство. Пусть и, игш'г" п и~чьи~ Тогда существует вершина и„такая, что и~<а Г'(и,) 0 (и.) и и~«в «нГ+(и.)0(и,). Если и~ и, или иг и., то и< и и, находятся ва маршруте; в противном случае рассмотрим прямые спуски юн ..., и~«из и.. Тогда илп и,~а Г+(пь) и и~«в Г+(иг ) для в,чью, или иь иг«в Г+(й«). В первом случае имеем плн и~<, иь пли и,(, и, в зависимости от того, в,< иг илп ю„<ы,.
Во втором случае повторяем процесс из иг„, пока пе будут выполнены условия первого случая, илп получаем и, и,илпи,* и;, в этом случае и~ п и, находятся на маршруте. е' 252 Много полезных обходов дерева определяют посредством расширеппя отпошепкя .. до полного упорядочивания У. Используя пркведенпый выше результат, надо только расширить <„чтобы сравнивать вершины, которые находятся иа маршруте, для определения полного порядка иа г', для которого <, является подпорядком.
Определение. Пусть Т ((г, Е) — упорядочеиное направленное дерево. Определим полную упорядочеппость <, иа г следующим абрагом: если вг спускается ие и„ то щ<г иб в лротпввом случае и <гав если и,<,иь Оглашение <г называют прсдяорядкож иа Г.
У Очевидно, что <,ы<в а Рис, Т.ЗО Пример Вхд Пусть Т (7, Е)-упорядочеипое направленное дерево, изображеиное иа рпс. 7.30. Тогда предпорядок иа У (а, 6, с, д, е, ), я, Ь, П можно записать как а <~6 <г е <~(<1с <гЫ <~б <~(<гЬ, Соответствующий обход вершины имеет вид а, 6, е, (, с, г(, д, ), Ь.У Определение. Пусть Т (У, Е)-упорядочеиное орпентированиое дерево. Определим отпошеиие <г полвого порядка иа У следующим образом: если и, спускается па еь то щ <ги,; в противном случае ш <гоп если и,<,иь Отношение <г называют посгиорядком на У. а' Очевидно, что <,ш <г. Пример 6.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
