Единственное ребро

Cтраница 3

Алгоритм основывается на последовательном выделении не пересекающихся по ребрам цепей, стягивающих наибольшее число ребер. На основании некоторых эвристик определяется ребро ( например, по максимуму суммы степеней инцидентных ему вершин), вершины которого считаются концевыми вершинами искомой цепи, вначале состоящей из этого единственного ребра. Затем цепь начинает удлиняться до тех пор, пока это возможно, из обеих своих концевых вершин. Обозначим через Es множество ребер, вошедших в искомую цепь на S предыдущих шагах алгоритма. После того как цепь становится невозможно продолжить, определяется множество не стянутых ею ребер, для которых вновь ищется длиннейшая цепь, стягивающая максимально возможное число ребер. [31]

Множества Si и S2 разделимы вертикальной прямой. ( а-каждая компонента o ( Sb S2 является монотонной по вертикали цепью. ( Ь - o ( Si, S2 состоит из единственной цепн. [32]

Поэтому, если все вершины диаграммы Вороного имеют степень три, то компоненты множества o ( Si S2) не пересекаются также и по вершинам. Каждая компонента множества a ( S S2) разбивает плоскость на две части. Таким образом, цепь либо содержит единственное ребро, представляющее прямую линию, либо ее первое и последнее ребра являются лучами. [33]

Сильно циклически связанные ребра ut v. [34]

Множество всех ребер, сильно циклически связанных с ребром и е С /, образует некоторую часть графа Г ( ЬЬ), называемую блоком, определяемым ребром и. Множество вершин Lb этого графа называется блоковым множеством, определяемым ребром и. Блок является связным графом и может состоять из единственного ребра. [35]

G в виде двудольного графа G ( V, V), где V есть копия V, с взаимно однозначным соответствием а; а между вершинами этих множеств. Каждому ребру ( а Ь) в G соответствует единственное ребро ( а, Ь) в G ( V, V), и наоборот. Любому паросоче-танию М в G ( V, V) соответствует часть Я1) в G не более чем первой степени. Компоненты Cj графа Н являются ориентированными простыми циклами и ориентированными простыми цепями. [36]

G в виде двудольного графа С ( У, V), где V есть копия F, с взаимно однозначным соответствием а а между вершинами этих множеств. Каждому ребру ( а, Ь) в G соответствует единственное ребро ( а, Ь) в G ( V, У), и наоборот. G ( V, V) соответствует часть Я) в G не более чем первой степени. Компоненты d графа Н яв-ляются ориентированными простыми циклами и ориентированными простыми цепями. [37]

Существует интересное обобщение деревьев - кактусы, которые также пересчитаны. Кактус - это связный граф, в котором ни одно из ребер не принадлежит более чем одному элементарному циклу. Таким образом, каждый блок кактуса представляет из себя или элементарный цикл, или единственное ребро. [38]

Доказательство леммы 13.2. Согласно предложению 13.2, редуктивный алгоритм Грэхема сохраняет ацикличность. Если в процессе редукции ациклического гиперграфа Я, выполняемой с помощью этого алгоритма, на каком-либо шаге окажется, что промежуточный гиперграф нередуцирован, то к нему можно применить правило УР. Если же этот промежуточный гиперграф редуцирован, то либо мы уже достигли гиперграфа с единственным ребром, либо выполняется предложение 13.4, и мы можем использовать правило УВ для удаления некоторой терминальной вершины. Поскольку при применении правил редукции в алгоритме Грэхема общее количество ребер и вершин уменьшается, то этот алгоритм постепенно редуцирует Я до пустого гиперграфа. С другой стороны, алгоритм редукции не может завершиться успешно в случае циклического гиперграфа Я. Действительно, такой гиперграф должен иметь по крайней мере три ребра. Если бы редукция Я завершалась успешно, то одним из ее промежуточных результатов оказался бы гиперграф, обладающий в точности двумя ребрами и тем самым ациклический. [39]

Множество вершин 5 в связном графе G называется разрезом ( или вершинным разрезом, или разрезающим множеством), если граф G - S не является связным. Подобное определение существует и для множества ребер. Если S есть разрезающее множество графа G, состоящее из единственной вершины v, то вершина г; называется точкой сочленения ( или разделяющей вершиной) графа G, а если S состоит из единственного ребра е, то е есть разрезающее ребро, или мост, графа G. Связный граф, не содержащий точек сочленения, называют неразложимым, или несепарабельным ( а также неразделимым), или 2-связным ( двусвязным), графом или просто блоком. [40]

Графическая формулировка таких задач облегчает вычислительный процесс. Некоторые из используемых при этом понятий связаны с деревьями специального типа. Граф без точек сочленения называется звездой, и следовательно, связный граф можно представить как объединение звезд, связанных в точках сочленения. Из обычного определения дерева следует, что дерево есть граф с точками сочленения, составляющие звезды которого состоят из единственного ребра. Если составляющие звезды являются многоугольниками, то граф называется деревом Хусими. Граф, показанный на рис. 6.9, становится деревом Хусими, если две его точки сочленения соединить второй цепью. [41]

Проиллюстрированный выше процесс реально представляет собой всего лишь способ слежения на всех стадиях анализа за теми гранями многогранника, положение которых в трехмерном пространстве уже было определено. Основное правило слияния двух узлов, если они связаны по крайней мере двумя дугами, представляет собой другую формулировку условий, при которых положение одной грани может быть найдено по известным положениям смежных с ней других граней. Первоначальное добавление дуги может рассматриваться как некоторая уловка, позволяющая развязать процесс. Она равносильна утверждению, что две грани имеют общие неколлинеарные ребра; это явно невозможно, но дополнительное ребро представляет собой фиктивный эквивалент того, что положения двух плоскостей заданы. В данном примере это был случай, когда добавление единственного ребра позволяет нам слить все узлы в один. Мы неформально показали, что структура видимой части трехгранного тела может быть определена rio четырем известным точкам, если дуальный граф 1-сливаемый. В более общем случае дуальный граф k - сливаемый, если нужно добавить не меньше, чем k дуг, чтобы посредством ряда слияний уменьшить граф до единственного узла. Нетрудно показать, что структура видимой части трехгранного тела определяется по & 3 независимым точкам во всех случаях, когда дуальный граф fe - сливаемый. Например, многогранник рис. 12.10, а имеет 2-сливаемый дуальный граф, и легко убедиться, что для определения видимой структуры должны быть известны положения пяти точек. [42]

Страницы: 1 2 3