Последовательность - ребро
Cтраница 4
Рассматривая геометрический граф, можно зафиксировать некоторую вершину и, последовательно двигаясь по смежным ребрам к вершинам, прийти в другую вершину или вернуться в исходную. В геометрическом графе это означает, что мы непрерывным образом двигаемся по последовательности простых кривых. Последовательности ребер, по которым можно двигаться непрерывным образом, играют фундаментальную роль в теории графов. [46]
Когда /, ik, последовательность замкнутая, в противном случае - она открытая. Начальная вершина - V - t, конечная - Vik, все остальные вершины - внутренние вершины. Цепь в графе G - открытая последовательность ребер, в которой все вершины различны; цикл в графе G - замкнутая цепь, в которой все внутренние вершины различны. Направленные цепи и направленные циклы в графе G определяются аналогично их эквивалентам в графе G, и вершина Vj называется достижимой из вершины V (, если существует направленная цепь из Vj в Vj. [47]
Для неориентированных графов, к которым принадлежит рассматриваемый, при наличии записи в строке i и столбце j обязательно существует запись в строке j и столбце i. На рис. 3.14 показан пример матрицы смежности для неориентированного графа. Программа 3.18 демонстрирует создание матрицы смежности для вводимой последовательности ребер. [48]
Теперь легко понять, как можно извлечь из РСДС последовательность ребер, инцидентных данной вершине, или последовательность ребер, окружающих данную грань. Пусть граф имеет п вершин и / граней. Следующая прямая процедура VERTEX ( /) вырабатывает последовательность ребер, инцидентных вершине р /, в виде последовательности адресов, хранящихся в массиве А. [49]
Маршрутом называется путь, проходящий от одной вершины к другой через ребра и вершины графа. Если граф представляет файл или список, то последовательность ребер является поисковой последовательностью. [50]
Это различие возникает в силу того, что существует различие между энергиями соответствующих связей. Если основание B ( i) является парным с основанием B ( k), а основание B ( i 1) - парным с основанием B ( k - 1), то можно сказать, что соответствующие ребра Ь - смежные. Последовательность ребер Ь такая, что каждый член смежен со своим последующим, образует область двойной спирали или стебель. Энергия такого стебля зависит не только от его состава ( сколько ребер Ы и Ь2 он содержит), но и от последовательности его ребер. [51]
 |
Примеры деревьев. [52] |
Для неориентированного графа понятия дуга, путь и контур заменяются понятиями ребро, цепь, цикл. Ребро - это отрезок, соединяющий две вершины. Граф на рис. 2 - 1 имеет восемь дуг, но семь ребер. Цепью - называется последовательность ребер. Циклом называется конечная цепь, у которой начальная и конечная вершины совпадают. [53]
Каждой вершине соответствует связный список с узлами для всех вершин, связанных с данной. В неориентированных графах, если существует узел для вершины j в i-том списке, то должен существовать узел для вершины i в j - том списке. На рис. 3.15 показан пример представления неориентированного графа с помощью списков смежности. Программа 3.19 демонстрирует метод создания такого представления для вводимой последовательности ребер. [54]
Однако существует более простой и прямой путь. Вершины трапеции располагаются в массиве по возрастанию ординат. Модификация процедуры ТРАПЕЦИЯ происходит следующим образом. Последовательность ребер просматривается дважды. [55]
Обсудим теперь вопрос о том, какую функцию алгебры логики реализует контактная схема. Эта функция равна единице при тех значениях аргументов, при которых в схеме есть проводимость, и нулю, если проводимости нет. По схеме естественным образом строится ДНФ для функций проводимости - Назовем цепью любую последова тельность контактов, в которой у каждого контакта можно так упорядочить полюсы ( начало и конец), что у первого контакта началом является вход схемы, начало каждого следующего контакта совпадает с концом предыдущего и конец последнего контакта совпадает с выходом схемы. При этом один и тот же контакт может участвовать в цепи несколько раз, причем при разных его вхождениях в цепь полюсы могут быть упорядочены по-разному. Геометрически цепь представляет собой связную последовательность ребер графа, идущую от входа к выходу. Для того чтобы на выходе схемы был ток при некотором наборе значений переменных, необходимо и достаточно, чтобы, по крайней мере, в одной цепи все контакты были замкнуты. [56]
Страницы: 1 2 3 4