Цепь - граф
Cтраница 1
Цепь графа - это маршрут, в котором каждое его ребро встречается не более одного раза; вершины в цепи могут повторяться и несколько раз. Как и маршруты, цепи графа могут быть ориентированными и неориентированными. Цепь удобно задавать последовательностью вершин графа, через которые она проходит. Цепь, не проходящая ни через одну из своих вершин более одного раза, называется простой ( элементарной) цепью. [1]
Любая гамильтонова цепь графа С с концевыми вершинами х1 и х2 может рассматриваться как гамильтонова цепь, проходящая через вершины графа О с добавленными ребрами ( хг, X) и ( х2, х), х, х 6 X. [2]
Если матрицы величин цепей графа R имеют большую размерность, то они могут быть представлены в виде блочных матриц. [3]
Если среди всех длиннейших цепей графа G нет ни одной стягивающей, то G не содержит стягивающей реберной цепи. [4]
Заметим, что / - увеличивающая цепь графа D соответствует ориентированной ( в) - цепи в графе DI и наоборот. [5]
Такое множество W называется полным множеством монотонных цепей графа G. Заметим, что, согласно свойству 2, цепи из полного множества упорядочены. Следовательно, можно применить к W метод дихотомии ( т.е. двоичный поиск), в котором элементарной операцией вместо простого сравнения чисел теперь будет дискриминация точки относительно цепи. Итак, если у нас г цепей в W и в самой длинной цепи р вершин, то поиск займет в наихудшем случае О ( log r - log р) времени. [6]
Рудеану [190] улучшает метод Фортета [116] нахождения га-мильтоновых цепей графа при помощи решения системы линейных уравнений в булевой алгебре. [7]
КА КВ, каждая г-я индексная компонента, отражающая у - ю покрывающую цепь графа h ( S ( G)) i, имеет вид, представленный на рис. 6.3, в. В этом случае мощности списков индекса / ( G) определяются выбором стягивающего реберного покрытия. [8]
В последнем случае мы будем называть концы этой простой линии концами цепи, а другие вершины цепи - внутренними вершинамиГ Под циклом или цепью графа G понимается его подмножество, которое соответственно есть цикл или цепь. Цикл графа G называется гамильтоновым, если он содержит каждую вершину этого графа. [9]
 |
Связный граф и два остовных дерева. [10] |
На каждом шаге показана строящаяся эйлерова цепь Z9 которая расширяется выделенным R циклом. Результирующая эйлерова цепь графа отмечена признаком О в начале строки. [11]
 |
Дерево вариантов маршрута обработки поверхности. [12] |
Различные цепи, выходящие из вершины графа, соответствующей какому-либо показателю заготовки, имеют последнее ребро, рассматриваемое как последний переход. Сами цепи описывают варианты многопереходной обработки. Поэтому формально различные варианты переходов и их последовательностей могут быть представлены ребрами и цепями графа. [13]
Непрерывная последовательность ребер ( ориентированных и неориентированных), в которой любые два соседних ребра имеют общую начальную точку, называется маршрутом графа. Одно и то же ребро может встречаться в маршруте несколько раз. Маршрут, в котором каждое его ребро встречается не более одного раза, называется цепью графов. Вершины в цепи могут повторяться несколько раз. Цепь элементарна, если она проходит через каждую из вершин не более одного раза. [14]
Страницы: 1