Послідовність - ребро - Велика Енциклопедія Нафти та Газа
Послідовність – ребро
Крім того, Ейлер вдалося довести і протилежне твердження, так що граф, в якому будь-яка пара вершин пов'язана деякою послідовністю ребер, є Ейлеровим тоді і тільки тоді, коли всі його вершини мають парний ступінь. [31]
Зважаючи на діафами, відповідні рис. 5.33 (зліва) та 5.34 (справа), покажіть, як відбувається відвідування вузлів у графі, побудованому для послідовності ребер 0 - 2, 1 - 4, 2 - 5, 3 - 6, 0 - 4, 6 - 0 та 1 - 3 (Див. вправу 3.70), при рекурсивному пошуку в глибину. [32]
Граф G (X, А) називають повним, якщо для будь-якої пари вершин є принаймні одне ребро. Послідовність ребер , у якій будь-які сусідні ребра суміжні, називають маршрутом графа. [33]
Введемо ще кілька визначень, які нам знадобляться для подальшого розгляду. Послідовність ребер 1ц, в якій у кожного ребра одна вершина є граничною з наступним ребром, а інша з попереднім, називається ланцюгом, і про граф, в якому будь-які дві вершини можна з'єднати ланцюгом, говоритимемо, що граф зв'язаний. [35]
Послідовність ребер, у якій вихідна та кінцева вершини збігаються, називається циклом. Якщо послідовність ребер включає цикли, вона може бути елементарної. [36]
Структурне дерево - це помічений граф (помічені ребра та вузли), де вузли відповідають граматичні типи або синтаксичні одиниці, а ребра відрізняються своїм порядковим номером. Ланцюг дерева - послідовність ребер, кожне з яких пов'язане з попереднім. У лінгвістиці слова або послідовності, які функціонують як елементи іншої конструкції, називаються складовими. [37]
Завдання такого типу вирішуються теоретично графів, неодноразово згадуваної нашій книзі. Шляхом у графі називається така послідовність ребер, в якій кожні два сусідні ребра мають загальну вершину. [39]
Припустимо, що вершини х і у з'єднуються R Lxy системою з k l простих ланцюгів, які попарно не мають інших загальних вершин. Кожному такому ланцюгу відповідає L послідовність різних ребер , у якої сусідні ребра суміжні ( мають загальну інцидентну вершину), причому всі k послідовностей попарно не мають спільних ребер. [40]
Виходимо тепер з z і починаємо шлях наступним ребром, що виходить з р. Щоразу, коли ми проходимо ребро дерева, ми продовжуємо побудову шляху; коли ми проходимо зворотне ребро, воно стає останнім ребром поточного шляху. Таким чином, кожен шлях складається з послідовності ребер дерева (їх число 0), за якими слідує одне зворотне ребро. Новий шлях починається з початкової вершини останнього зворотного ребра; якщо в цій вершині не досліджених ребер більше немає, повертаємось до попередньої вершини на останньому шляху. Процес триває доти, доки у графі G не вичерпаються непройдені ребра. Алгоритм 8.14 здійснює це розкладання орграфа на шляху та цикл. [41]
На рис. 2.4.2 a, b, e, g – висячі вершини, с, d та f – вузли. Очевидно, їх можна розглядати як частину послідовності ребер, що з'єднують інші вершини. [42]
Нехай граф Р немає двічі циклічних вершин. Назвемо ланцюгом подграф графа Р, що складається з послідовності ребер , у якій кінець попереднього ребра є початком наступного, і жодна вершина не зустрічається двічі. [43]
Вочевидь, що час роботи процедури VERTEX ( /) пропорційно числу ребер, інцидентних Vj. Аналогічно можна побудувати процедуру FACE (/),що виробляє послідовність ребер, що оточують грань //; для цього в описаній вище процедурі VERTEX (/) масиви HV та 1/1 потрібно замінити відповідно масивами HF та FI. Зазначимо, що процедура VERTEX шукає ребра, рухаючись навколо вершини проти годинникової стрілки, тоді як процедура FACE шукає ребра, рухаючись навколо грані за годинниковою стрілкою. [44]
Іноді важливо розрізняти різні способи впорядкування ребер при утворенні ланцюгів або циклів, в інших випадках не існує. Обидві ситуації трапляються досить часто, тому запровадження різних термінів для впорядкованих і невпорядкованих послідовностей ребер цілком виправдано. [45]