Висяча вершина - Технічний словник Том II
Висячі вершини А, У, З, D і Е визначають варіанти набору базису даної системи рівнянь. Висячим вершинам графа відповідають базові елементи, проміжним - складові елементи системи. Алгоритм декомпозиції складних ХТС систем на суто підпорядковані елементарні та контурні підсистеми. Висячою вершиною прадерева стає та вершина, номер якої збігається з номером однієї з вершин, що належить. Всі висячі вершини розташовуються на тому самому рівні і не несуть інформації. Алгоритм декомпозиції складних ХТС систем на суто підпорядковані елементарні та контурні підсистеми. Кожна висяча вершина прадерева належить простому, або елементарному контуру параметричного потокового графа. Отже, елемент ХТС, що відповідає цій вершині графа, належить деякій простій контурній підсистемі. Кількість висячих вершин графа відповідає числу елементів масиву. Кожній висячій вершині такого дерева зіставлені один або два нащадки, причому кожній другій вершині потрібно зіставляти двох нащадків. Якщо число висячих вершин враховувати не потрібно, то лічильники, що відповідають їм, слід покласти рівними sv l, при цьому звернуться в одиницю відповідні їм функції u ( s) ( пор. Штрих у знака суми (1.22) означає підсумовування тільки за такими кольорами v Наприклад, якщо висячі вершини (див. рис. 1.15) за корінь не вибираються, то останній доданок цього малюнка слід відкинути. Для обов'язкових гілок потоки входять у базисні рішення Таким чином можна визначити з для кожної висячої вершини.мережевої задачі передбачає розгалуження, начг. Розгалуження закапчується в точці D, що відповідає дереву мінімальної довжини. При додаванні нової висячої вершини може з'явитися вершина1 з т 1 нащадками. Якщо у предка розщепленої вершини менше (яг 1) / 2) нащадків, то процес включення нової вершини закінчується; в іншому випадку процедура розщеплення продовжується. Якщо вершина, що розщеплюється, є корінь, то утворюється новий корінь, нащадками якого стають нові вершини. Загальна кількість висячих вершин прадерева завжди більше числа простих контурів графа, оскільки різні висячі вершини прадерева можуть відповідати одному й тому простому контуру. Якщо видалити висячу вершину з дерева, що складається з IFI вершин і Е ребер, залишиться дерево, що складається з IFI - 1 вершини і Е - 1 ребра. Продовжуючи цей процес видалення, прийдемо зрештою до тривіального дерева з однієї вершини.
При цьому висячим вершинам відповідають безлічі значень первинних даних, проміжним - підсумки певного ступеня (залежно від рівня вершини), а корінь ідентифікує завершення обробки та формування остаточного підсумку. Виділення контурів. Римськими цифрами відзначені висячі вершини прадерева. При графічному зображенні висячі вершини 5-дерева зазвичай не малюють. Якщо всім висячих вершин даної стадії розгалуження НГ ЦФ0, то процес мінімізації вважається завершеним. При цьому ЦФ0 відповідає оптимальному глобальному рішенню. Фактично, відбувається повний перебір всіх рішень, але з окремим рішенням, а, по їх підмножинам, що однаково забезпечує перебування глобального екстремуму. Завдання множини Про висячі вершин дещо змінює критерій 5 порівняно із записаним у ВПС. Ребро, інцидентне висячій вершині, називаютькінцевим. НФЗ, що відображаються висячими вершинами ДВР, і не існує жодної висячої вершини на всіх рівнях ієрархії шарів вершин ДВР, яка може бути обрана як активна вершина. Граф Хівуда. Якщо W закінчується висячою вершиною графа G, очевидно, що W немає послідовників. ЯВ-дерево з найменшим числом висячих вершин при заданій висоті отримують, роблячи кожному рівні число вершин з одним нащадком якнайбільше, а число вершин із двома нащадками якнайменше. Якщо вершина лише на рівні h 1 має двох нащадків, один із її нащадків лише на рівні h 1 обов'язково має лише одного нащадка. Плоский зв'язковий граф без висячих вершин, кожна грань якого, включаючи і зовнішню, обмежена циклом довжини 3, називається тріангуляція. Показати, що тріангуляція з п 3 вершинами має Зп - 6 ребер та In - 4 грані. Довести, що кількість висячих вершин не перевищує п/2, де п - число вершин кореневого дерева. Семантичне дерево має 2fc висячих вершин і для перевірки загальнозначущості необхідно пройти 2fc маршрутів від кореня до цих вершин. Gm] - безліч висячих вершин повного декомпозиційного дерева T (G) графа G, і для кожного графа Gt з цієї множини існує послідовність Li перетворень I, II, що переводить його в послідовно-паралельний граф.
Нехай кореневе дерево має k висячих вершин і не має вершин ступеня 2, відмінних від кореня. Ознакою кінця розгалуження є наявність висячої вершини в дереві розгалужень, що відповідає повному рішенню і має найкращу оцінку характеристики (3.1.10) порівняно з усіма іншими допустимими частковими або повними рішеннями. Кожна вершина, виключаючи корінь і висячі вершини, має принаймні / (щ) нащадків. Етйст 0TiCT) задається перерахуванням своїхвисячих вершин. Вважається, що граф не містить висячих вершин. Помічені дерева, що перераховуються членом v. У заданому поміченому дереві Т візьмемо висячу вершину і має найменшу позначку, і виберемо позначку а1 вершини, суміжної з і. При аналізі дій оператора часто використовується поняття висячої вершини графа. Наявність їх призводить до руйнування концептуальної моделі оператора, зокрема, зникнення деяких ребер повного графа або виникнення зайвих зв'язків. Висячі вершини графа є причиною аварійної ситуації; Завдання оператора полягає у своєчасному розпізнаванні цих вершин. Дерево Тг має n - r i висячу вершину. Кількість ліній, що з'єднують корінь графа з висячою вершиною, відповідає числовій характеристиці, яка називається розмірністю (число вимірювань) масиву. Очевидно, що кількість індексів у записі змінної з індексами має відповідати числу вимірювань масиву. Пошук набору елементарних ланцюгів пра-дерева, що закінчуються висячими вершинами, проводиться перебором гілок дерева СТГ та добудовуванням ланцюгів, що починаються з k-то вузла. Якщо висячою вершиною деякого ланцюга прадерева виявляється вузол /, то такий ланцюг, доповнений t - й хордою, утворює фундаментальний цикл. При завершенні простого ланцюга ДВР або за відсутності висячих вершин на даному/-му рівні верств вершин ДВР вибір активної вершини здійснюється на попередньому або найближчому попередньому рівні вершин ДВР, де існує можливість декомпозиції вершин, або альтернативних рішень. Реберно-орієнтована матриця та вектор безлічі ребер. Підматриця Ве. Попередньо проводиться дослідження заданого графа на предмет видалення висячих вершин та інцидентних ним ребер, а також стягування вершин, що мають локальний ступінь, що дорівнює двом. Крім того,необхідно перевірити, чи є вихідний граф зв'язковим, а також визначити, чи не розглядається граф заздалегідь планарним, або заздалегідь непланарним. Потім кожна компонента, що утворилася, включаючи цикл, перевіряється на можливість побудови плоского укладання. У графі перебуває довільний цикл, після видалення якого граф розпадається окремі фрагменти. Зазначимо, що будь-яке декомпозиційне дерево з висячими вершинами має рівно т - 1 операційну вершину.
Бінарне дерево називається Н - деревом, якщо всі висячі вершини знаходяться на тому самому рівні і кожна вершина з єдиним нащадком має правого сусіда з двома нащадками. Ексцентриситети вершин дерева. У будь-якому нетривіальному дереві є принаймні дві висячі вершини. З вищесказаного видно, що будь-яке підзавдання, що представляється висячою вершиною і не піддається дозволу, може бути в будь-який момент розбито на менші підзавдання. Але є лише два основних типи пошуку залежно від цього, як вибирається наступна висяча вершина продовження процесу розгалуження. Нехай кореневе дерево з п (п 2) висячими вершинами не має вершин ступеня 2, відмінних від кореня. З вищесказаного видно, що будь-яке підзавдання, що представляється висячою вершиною і не піддається дозволу, може бути в будь-який момент розбито на менші підзавдання. Але є лише два основних типи пошуку залежно від цього, як вибирається наступна висяча вершина продовження процесу розгалуження. Бінарне дерево називається HS-деревом, якщо справедливо наступне: всі висячі вершини знаходяться на одному рівні, і якщо вершина х має тільки одного нащадка, то цей нащадок є або висяча вершина, або сам має двох нащадків. Наявність голих вершин не впливає на характер компоненти,містить висячі вершини, оскільки їх ступінь дорівнює нулю. Кожен шлях, показаний на схемі від початку до висячої вершини, відповідає окремої моделі. Однак, незважаючи на відмінності, загальним у всіх моделей є те, що описують типові екстремальні завдання комбінаторного типу. Відомо, що отримання точного розв'язання таких завдань у випадку пов'язані з великими труднощами і загальних методів точного розв'язання поки що немає. Однак специфіка задач часто дозволяє знайти досить добрі наближені рішення. Є існують витрати F a на повну схему, що відповідає деякій висячій вершині Аьа. Значення в клітині (i, /) матриці, що відповідає висячій вершині, обраної К), замінюємо на оо. Послідовно провести орієнтацію тих ребер змішаного ІПМ, які інцидентні висячим вершинам графа, у напрямку зазначеної висячої вершини. Цю стадію на графі рис. 7в описує ребро 5 з висячою вершиною.