Начальные и конечные вершины. Ранги вершин

Вершина графа наз. начальной, если в неё не входит ни 1 ребро, конечной – если из неё не выходит ни одно ребро. Во всяком конечном ациклическом графе есть хотя бы 1 нач. и 1 кон. Вершины. Доказательство. Все пути графа G конечны и имеют длину, не превосходящую вершины, т.к. в ациклическом графе в пути вершины повторяться не могут. Существует максимальный путь, который нельзя удлинить ни в начале, ни в конце. Начало пути – начальная вершина, конец – конечная. Максимальным рангом R(V) ориентированного графа G наз. максимальная из длин путей этого графа с концом в V. Если рассмотреть начальную вершину графа, то её ранг =0. Если через V проходит цикл, то её ранг =+∞. В ациклическом графе все ранги вершин конечны. В ациклическом графе ранг неначальной вершины определяется R(V)=max(R(V_i-1))+1

Бінарне дерево

Бінарне дерево – кінцева множина вершин в яких або пуста або складається з кореня і двох неперетинаючихся бінарних піддерев. Бінарне дерево не впорядковане.

91. «И-ИЛИ» дерево

Вершина, з якої виходять «И» - зв’язки називається вершиною типу «И», щоб розглянути вершину типа «И» - треба вирішити всі її дочерні вершини. Вершина, що зв’язує альтернативи називається вершина типу «або» і для того щоб розглянути її необхідно вирішити будь-яку з її дочірних вершин.

Для аналізу таких графів і пошуку рішень в них можна використовувати алгоритми обхода в глубину і в вширину але вони не є ефективними через велику комбінаторну складність. Для таких графів існують алгоритми евристичного пошуку.

У якості оціночної функції вводиться вартість. Вона визначається як сума вартостей його ребер. Ціль алгоритма знайти рішающе дерево мін. вартості. Вартість вершин = вартості отриманого вирішального дерева.

Для оцінки вартості вершин будемо використовувати додаткову інфу про дочірні вершини. Для оцінки вартості вершин типу «АБО»

На будь-якій стадії пошуку кожна дочірня вершина («АБО») відповідає альтернативному вирішальному дереву. Процес пошуку приймає рішення продовжити пошук для дерева, ціна шляху для якого є мінімальною.

Дерево с корнем. Ветви.

Пусть в дереве g отлична вершина V⁰ – эта вершина корень дерева, а дерево – дерево с корнем, в таком дереве можно естественным образом ориентировать ребра. Вершину V’ дерева g можно соединить с корнем V⁰ при помощи единственно возможной цепи.

 

Если на ребрах дерева обозначить ориентацию от V’ к V” то такое дерево будет наз. ориентированым.

Обычно в ориентированном дереве все ребра имеют направление от корня к концу вершины, однако если определено противоположное направление от конца вершины к корню, то такой граф наз. сетью сборки. В каждую вершину ориентиро - ванного дерева, за искл. корня, входит только одно ребро, все инцидентные корню ребра связывают корень с вершинами, следовательно корень явл. началом ребер. В конечном дереве число вершин на 1-у больше числа ребер. Пусть V-вершина дерева g с корнем V₀. В(V)- множество всех вершин, связанных с корнем, цепям проходящими через вершину V.Это множество порождает подграф g(V), кот. наз. ветвью вершины V в дереве с корнем V₀. Как подграф дерева, g(V) тоже не имеет циклов. Любые две вершины V’,V” принадлежат В(V), связанные в этой ветви маршрутом, составленным из участков цепей L(V’) и L(V”) от корня V₀ до этих вершин. Докажем, что эти участки целиком принадлежат g(V). Это справедливо, т.к. в каждую вершину такого участка ведет цепь из корня V₀, являющаяся начальным участком соотв. цепи LV’ и LV” и проходящая через вершину V, т.е. ветвь g(V) является связанной и сама является деревом. Рассмотрим g(V) как дерево с корнем V. Для любой вершины V’ принад ле - жащей g(V), связывающая ее с вершиной V цепь LVV’ является концом цепи LV₀V’, связывающей в дереве g эту вершину с корнем V₀.

Центры деревьев. Теорема.

Теорема. Центрами деревьев является вершина максимального типа и только она.Доказательство. Любая цепь l с началом в вершине V0(вершина максимального типа), проходит последовательно по вершинам уменьшающихся типов. Ее ребро V0V1 может привести вершину типа к, либо в вершину меньшего типа. Следующие ребра уже обязательно попадут в вершины меньшего типа. Таким образом, для L цепи l с началом в вершине типа к, имеем: l(L) k и , если вершина макс.типа единственная макс.удаленная от вершины макс.типа в дереве = ее типу к если (к-1).Рассмотрим случай, когда вершина V имеет не макс.тип. Покажем, что она начало более длинной цепи. Построим цепь lVV0, связыв.эту вершину с вершиной макс.типа. Если вершина V0- единственная вершина макс.типа, то она связанна с 2 вершинами типа (к-1). Можно построить цепь lV0V1 длины (к-1), не проходящую через последнее ребро цепи lVV0 и не имеющую с этой цепью общих вершин, иначе был бы цикл. Цепь l, которая явл.l(V2V1)и l(V1V0), если в дереве Д есть вершина V1 и V0 макс.типа, то можно построить связывающую их цепь. Если она проходит через другую вершину макс.типа, ее длина >2. Тогда V0 явл. началом цепи (к-1) с первым ребром V0V3, ведущим в вершину V3 типа (к-1). Эта цепь не имеет с построенной ранее цепью общих вершин, иначе был бы цикл. Длина цепи ≥(к+1).Для любой вершины не макс.типа и удаление (макс)>k. Дерево может иметь либо 1, либо и 2 центра.