Последовательность - ребро
Cтраница 2
На рис. 16.2 приведен пример скругления последовательности касательных ребер трехмерного тела одинаковым радиусом. [16]
Путь в графе или орграфе - это последовательность ребер, по которым можно поочередно проходить. Другими словами, путь из вершины А в вершину В начинается в А и проходит по набору ребер до тех пор, пока не будет достигнута вершина В. Mu требуем, чтобы любая вершина встречалась на таком пути не более, чем однажды. У всякого пути есть длина - число ребер в нем. [17]
Почему следующее утверждение неверно: маршрут есть последовательность ребер таких, что смежные ребра графа являются всегда смежными ребрами в последовательности ребер, образующей рассматриваемый маршрут. [18]
Определим на графе G маршрут L как такую последовательность ребер, что каждые два соседних ребра имеют общую концевую точку. В случае ориентированного графа маршрут называют путем. Очевидно, что решение задачи методом поиска в пространстве состояний ( т.е. нахождение последовательности операторов, преобразующей начальное состояние в конечное) сводится к задаче поиска пути L на графе G. Часто бывает удобно приписывать дугам графа веса, отражающие стоимость применения соответствующих операторов. Стоимость пути между двумя вершинами определяется как сумма стоимостей всех дуг, образующих этот путь. В ряде приложений возникает задача нахождения путей ( пути), имеющих минимальную стоимость, между любыми элементами из множества Х0 и любыми элементами из множества Xf. Отметим, что граф G может быть задан как в явном виде, так и неявно. Неявное задание графа G состоит в определении множества Х0 и множества операторов, которые будучи применимы к некоторой вершине графа, дают все ее дочерние вершины. [19]
 |
Строение РСДС. [20] |
Теперь легко понять, как можно извлечь из РСДС последовательность ребер, инцидентных данной вершине, или последовательность ребер, окружающих данную грань. Пусть граф имеет п вершин и / граней. Следующая прямая процедура VERTEX ( /) вырабатывает последовательность ребер, инцидентных вершине р /, в виде последовательности адресов, хранящихся в массиве А. [21]
Маршрутом на графе между вершинами а и b называется последовательность ребер с началом в а и концом в Ь, в которой каждое следующее ребро начинается там, где кончается предыдущее. [22]
Если v0vn, но все остальные вершины различны, то последовательность ребер называется простым циклом, а соответствующее неупорядоченное множество ребер - неупорядоченным простым циклом. Заметим, что в геометрическом графе простые цепи образуют простые незамкнутые кривые ( см. определение выше), а простые циклы - простые замкнутые кривые. [23]
Маршрутом, связывающим вершину А с вершиной В, называется последовательность ребер, которую необходимо пройти, продвигаясь от вершины / 1 ч вершине В. Маршрут, начальная и конечная вершины которого совпадают, называется контуром. Граф называется связным, если для любой пары его вершин существует маршрут. [24]
Простая цепь ( путь) в ненаправленном ( направленном) графе представляет собой последовательность ребер ( дуг) и вершин, в которой не повторяется ни одна вершина; контур ( цикл) представляет собой цепь ( путь), начальная и конечная вершины которого совпадают. Говорят, что граф является связным без учета направленности, если существует простая цепь между любой парой вершин. Граф с ( п 1) вершинами является п-кратно связным, если удаление ( п - 1) или меньшего числа вершин не делает его несвязным. Говорят, что две цепи не пересекаются, если они не имеют общих вершин, за исключением конечных точек. Дерево представляет собой связный подграф, в котором отсутствуют контуры. Стягивающее дерево ( остов) представляет собой ( максимальное) дерево, которое содержит все вершины графа. Ребро графа, которое входит в дерево, называется ветвью. Ребро графа, которое не входит в дерево, называется хордой. Дерево начинается в у, откуда исходят все пути дерева. [25]
Граф называется связным, если любые две его вершины соединяются хотя бы одной последовательностью ребер, и несвязным в противном случае. Ребро графа, удаление которого приводит к разбиению графа на две несвязные части, называется мостом. Другими словами, мостом называется ребро, соответствующее проходной цепи в гигантской циклизованной макромолекуле. Вершина с этим же свойством называется точкой сочленения. Более общим понятием является / с-сечение - набор таких k мостов и / г-вершин, удаление которых приводит к разбиению графа на две несвязные части. Граф, не, содержащий ни одного / е-сечения, называется / с-неприводимым, а в обратном случае - / с-приводимым. [26]
Теперь легко понять, как можно извлечь из РСДС последовательность ребер, инцидентных данной вершине, или последовательность ребер, окружающих данную грань. Пусть граф имеет п вершин и / граней. Следующая прямая процедура VERTEX ( /) вырабатывает последовательность ребер, инцидентных вершине р /, в виде последовательности адресов, хранящихся в массиве А. [27]
 |
Возможные виды короны. [28] |
Амы можем получить за константу времени ребра еа и е а, следующие за е а в последовательностях ребер, окружающих грани fi и / 2 соответственно. [29]
Почему следующее утверждение неверно: маршрут есть последовательность ребер таких, что смежные ребра графа являются всегда смежными ребрами в последовательности ребер, образующей рассматриваемый маршрут. [30]
Страницы: 1 2 3 4