Остальная вершина - граф
Cтраница 2
Эта очередность оказывает, как будет доказано, очень сильное влияние на эффективность алгоритма. Опишем теперь более детально методы нахождения расстояния от фиксированной вершины, называемой источником, его всегда будем обозначать через s, до всех остальных вершин графа. [16]
Соотношения ( 4), ( 5) при заданном базисе позволяют построить решение с помощью элементарных алгебраических операций. При этом обращения базисной матрицы не требуется: ее элементы являются индикаторами принадлежности дуг базисного дерева цепям, соединяющим корень ( узел 0) с остальными вершинами графа. [17]
Каждая i-я вершина графа ( исключая базовую) обладает собственной проводимостью, а две смежные вершины графа имеют взаимную проводимость. Собственная проводимость /, вершины i равна сумме комплексных проводимостей ветвей структурного графа ( или полюсных компонентов), расположенных между данной и базовой вершинами, когда все остальные вершины графа замкнуты накоротко ( объединены) с базовой. Взаимная проводимость iv / j между двумя вершинами г и / равна сумме комплексных проводимостей ветвей, расположенных между этими вершинами, когда все остальные вершины графа замкнуты накоротко с базовой вершиной. [19]
Программа без процедур представляет собой конечный ориентированный граф с размеченными вершинами и дугами. В нем выделены две вершины: вход - вершина без заходящих в нее дуг и с единственной исходящей дугой, и выход - вершина без исходящих из нее дуг. Остальные вершины графа, если они имеются, по своему типу делятся на преобразователи и распознаватели. Из каждого преобразователя исходит одна дуга, из распознавателя - две. Разметка вершин подчиняется правилу: всякому преобразователю сопоставляется оператор из S, всякому распознавателю - булево выражение из S. Дуги, исходящие из распознавателя, помечаются символами 0 и 1 соответственно, другие дуги меток не имеют. [20]
Граф программы - это циклический ориентированный граф G ( X, U), вершины которого х представляют различные шаги программы. Вершины связаны дугами и, представляющими разветвления и циклы в программе. Граф программы содержит одну начальную вершину Xi, предшествующую всем остальным вершинам графа и не имеющую входящих дуг, и одну конечную вершину хх, которая следует за всеми остальными вершинами и не имеет исходящих дуг. [21]
Каждая i-я вершина графа ( исключая базовую) обладает собственной проводимостью, а две смежные вершины графа имеют взаимную проводимость. Собственная проводимость /, вершины i равна сумме комплексных проводимостей ветвей структурного графа ( или полюсных компонентов), расположенных между данной и базовой вершинами, когда все остальные вершины графа замкнуты накоротко ( объединены) с базовой. Взаимная проводимость iv / j между двумя вершинами г и / равна сумме комплексных проводимостей ветвей, расположенных между этими вершинами, когда все остальные вершины графа замкнуты накоротко с базовой вершиной. [22]
Как видно, наличие вершин с различными локальными степенями упрощает процесс распознавания изоморфизма графов. Это позволяет выбирать начальные условия для эвристики разбиения. В однородных графах все степени вершин одинаковы, поэтому начальные условия выбираются произвольно случайным образом. В этой связи при установлении изоморфизма в однородных графах временная сложность алгоритма в самом лучшем случае равна О ( п), в самом худшем случае - О ( га. Если графы неизоморфны, то за одну итерацию установить результат невозможно. Необходимо провести сравнение на изоморфизм одной случайно выбранной вершины из одного графа со всеми остальными вершинами другого графа. [23]
Страницы: 1 2