Последовательность - вершина
Cтраница 3
В алгоритме предусмотрено пристраивание новой вершины не только в конец, но и в начало последовательности выделенных вершин. [31]
 |
Структура данных поиска, соответствующая трапеции с. [32] |
Более формально, процедура-функция ТРАПЕЦИЯ, строящая дерево поиска, получает на входе: Е - цепочку ребер ППЛГ, V - последовательность вершин внутри R, упорядоченную по возрастанию их ординат, и у - интервал / трапеции R. В процедуре используются вспомогательные операции, такие как поиск медианы и балансировка, которые будут описаны позже; Е, Е %, U и t / 2 - рабочие списки этого алгоритма. [33]
После внимательного изучения операций алгоритма перебора Робертса и Флореса становится очевидным, что даже после сделанного улучшения не слишком много внимания уделяется оставшейся части графа, в которой берется последовательность вершин, продолжающих построенную цепь. Обычно построение цепи 50 в процессе поиска ( 50 рассматривается и как упорядоченное множество вершин, и как обычное множество) подразумевает существование еще каких-то цепей в других частях графа. Эти предполагаемые цепи либо помогают быстрее построить гамиль-тонов цикл, либо указывают на отсутствие такого цикла, содержащего цепь 50, что позволяет сразу прибегнуть к возвращению. [34]
После внимательного изучения операций алгоритма перебора Робертса и Флореса становится очевидным, что даже после сделанного улучшения не слишком много внимания уделяется оставшейся части графа, в которой берется последовательность вершин, продолжающих построенную цепь. Обычно построение цепи S0 в процессе поиска ( S0 рассматривается и как упорядоченное множество вершин, и как обычное множество) подразумевает существование еще каких-то цепей в других частях графа. Эти предполагаемые цепи либо помогают быстрее построить гамиль-тонов цикл, либо указывают на отсутствие такого цикла, содержащего цепь S0, что позволяет сразу прибегнуть к возвращению. [35]
Далее мы сразу же замечаем, что 8, Эй, 91 равны удвоенным площадям проекций треугольника ( /, 2, 3) на координатные плоскости, если брать его каждый раз с направлением обхода /, 2, 3, a равно шестикратному объему тетраэдра ( О, 1, 2, 3), тоже взятому со знаком, соответствующим этой последовательности вершин. Эти четыре величины остаются, очевидно, неизменными в том и только в том случае, если треугольник ( 1, 2, 3) передвигать по его плоскости и так его при этом деформировать, чтобы его площадь и направление обхода оставались неизменными. Следовательно, они определяют треугольник или вообще часть плоскости, имеющую именно такую подвижность - то, что Грассман называет плоскостным элементом. Первые три координаты 8, SJ, 9J плоскостного элемента остаются без изменения также и при сдвиге плоскости треугольника параллельно ей самой; следовательно, они определяют площадь и направление обхода треугольника, который может свободно перемещаться в пространстве параллельно самому себе, - так называемый свободный плоскост ной элемент. [36]
Таким образом, исходный граф не содержит гамильтонова цикла. Последовательность вершин ( 10, 1 и 2) является началом максимальных простых цепей ( 6, 5, 4, 3, 8, 7), ( 6, 5, 4, 3, 8, 9), ( 6, 5, 9, 8, 3, 4), ( 6, 5, 9, 8, 7), ( 6, 7, 8, 3, 4, 5, 9), ( 6, 7, 8, 9, 5, 4, 3), ( 3, 4, 5, 6, 7, 8, 9), ( 3, 4, 5, 9, 8, 7, 6), ( 3, 8, 7, 6, 5, 4), ( 3, 8, 7, 6, 5, 9), ( 3, 8, 9, 5, 4), ( 3, 8, 9, 5, 6, 7) и ни одна из них не образует гамильтонова цикла. В силу симметрии то же самое справедливо для всех других цепей. [37]
 |
Модель задачи о мостах Кенигсберга. [38] |
Граф, в котором найдется маршрут, начинающийся и заканчивающийся в одной вершине, и проходящий по всем ребрам графа ровно один раз, называется эйлеровым графом. Последовательность вершин ( может быть и с повторениями), через которые проходит искомый маршрут, как и сам маршрут, называется эйлеровым циклом. [39]
Простой путь по G называется несокращаемым, если нельзя, удалив некоторые его внутренние вершины, получить другой простой путь по G, и сокращаемым в противном случае. Последовательность L вершин уграфа G называется [36] его слабой укладкой, если любой несокращаемый простой путь по G можно получить из L удалением некоторых его вершин. Назовем уграф G простым, если каждая его вершина имеет не более двух предшественников и не более двух преемников. [40]
О ( log г) в худшем случае, где i - число узлов дерева. Естественно, кольцевая последовательность вершин представляется в этой древовидной структуре данных ( называемой далее Т) цепочкой, и при этом первый и последний элементы считаются смежными. [41]
Повторять пункт 3 пока все вершины не будут посещены. Потомок формируется как последовательность посещаемых вершин. [42]
Путем в графе называется последовательность вершин и дуг, в которой каждый элемент встречается только раз. Контуры называются некасающимися, если они не имеют общих вершин. Передаточные функции путей и контуров равны произведению передаточных функций образующих их дуг. [43]
Путь (1.1) можно представить также последовательностью вершин х %, х5, х, хэ, хь, хв и такое представление часто оказывается более полезным в тех случаях, когда осуществляется поиск простых орцепей пли простых цепей. [44]
Путь (1.1) можно представить также последовательностью вершин х2, х5, х4, х3, хь, х6 и такое представление часто оказывается более полезным в тех случаях, когда осуществляется поиск простых орцепей пли простых цепей. [45]
Страницы: 1 2 3 4