Алгоритм - установление - изоморфизм
Cтраница 1
Алгоритм установления изоморфизма за О ( У-log У) действий зависит от эффективного алгоритма разбиения множества дуг планарногЬ графа на подмножества таким образом, что две дуги принадлежат одному и тому же множеству тогда и только тогда, когда эти дуги неразличимы. Разбиение отыскивается следующим образом. [1]
В статье предлагается алгоритм установления изоморфизма двух планарных графов, который требует O ( V - logV) действий, где У т - число вершин в каждом из графов. [2]
Именно этот подход мы используем при построении алгоритма установления изоморфизма орграфов. [3]
 |
Изоморфные орграфы. [4] |
Однако при подходящем укорачивании дерева поиска такой метод дает основу для построения приемлемого алгоритма установления изоморфизма графов. [5]
Отличительной чертой другого алгоритма [144] является использование тех же приемов работы со множествами сопоставляемых элементов структуры, на которых основывается разработанный Сассенгутом [93] алгоритм установления изоморфизма двух структур, рассмотренный нами в § 9.3. В данном случае в качестве сопоставляемых элементов вместо атомов берутся связи. Составляются списки множеств одинаковых ( без учета кратности) видов связей, которые могут быть сопоставлены друг другу в сравниваемых ( в данном случае заведомо неизоморфных) структурах, соответствующих левой и правой частям анализируемого уравнения. [6]
Первые результаты об установлении изоморфизма планарных графов принадлежат Вейнбергу, который разработал эффективный алгоритм определения изоморфизма 3-связных планарных графов, требующий число действий, пропорциональное У2, а также алгоритмы установления изоморфизма последовательно-параллельных графов и деревьев. [7]
В данной работе описывается эффективный алгоритм установления изоморфизма двух планарных графов. Асимптотически число действий этого алгоритма определяется как О ( У-log У), где V - число вершин в каждом из графов. Здесь как промежуточный результат приводится также алгоритм установления изоморфизма деревьев, характеризующийся линейным числом действий. [8]
Предлагаемая статья состоит из пяти разделов. Введение и определение необходимых понятий теории графов составляют содержание первого раздела. Во втором разделе описывается алгоритм нахождения разбиения графа на однозначно определенные 3-связные компоненты за число действий, пропорциональное числу ребер графа. В третьем разделе дается алгоритм установления изоморфизма деревьев. В четвертом разделе описывается алгоритм установления изоморфизма 3-связных планарных графов за число действий, пропорциональное У-log V. В пятом описанные алгоритмы объединяются и описывается алгоритм установления изоморфизма произвольной пары планарных графов. [9]
Отметим, что он имеет ориентацию относительно его 2-сочленений. В силу этого обстоятельства 3-лепестку приписывается именно упорядоченная пара чисел. Числа равны 1югда и только тогда, когда 3-лепесток симметричен относительно замены его 2-сочленений. Если хотя бы одна компонента не является планарным графом, то алгоритм установления изоморфизма графов не работает, поскольку и весь граф не планарен. [10]
Для последующего полезно несколько обобщить задачу установления изоморфизма деревьев. Допустим, что каждой вершине приписано некоторое множество меток. Два помеченных дерева изоморфны, если можно установить взаимно однозначное соответствие между их непомеченными деревьями, такое, что любые две соответствующие вершины из разных помеченных деревьев имеют одно и то же множество меток. Теперь опишем алгоритм установления изоморфизма помеченных деревьев, который требует 0 ( V, L) действий, где V - число вершин, a L - число всех меток. Для сортировки применяется процедура основной сортировки или сортировки по ящикам, когда используется не более 2F 1 ящиков. Алгоритм может быть запрограммирован на вычислительной машине с произвольным порядком выбора. [11]
Предлагаемая статья состоит из пяти разделов. Введение и определение необходимых понятий теории графов составляют содержание первого раздела. Во втором разделе описывается алгоритм нахождения разбиения графа на однозначно определенные 3-связные компоненты за число действий, пропорциональное числу ребер графа. В третьем разделе дается алгоритм установления изоморфизма деревьев. В четвертом разделе описывается алгоритм установления изоморфизма 3-связных планарных графов за число действий, пропорциональное У-log V. В пятом описанные алгоритмы объединяются и описывается алгоритм установления изоморфизма произвольной пары планарных графов. [12]
Предлагаемая статья состоит из пяти разделов. Введение и определение необходимых понятий теории графов составляют содержание первого раздела. Во втором разделе описывается алгоритм нахождения разбиения графа на однозначно определенные 3-связные компоненты за число действий, пропорциональное числу ребер графа. В третьем разделе дается алгоритм установления изоморфизма деревьев. В четвертом разделе описывается алгоритм установления изоморфизма 3-связных планарных графов за число действий, пропорциональное У-log V. В пятом описанные алгоритмы объединяются и описывается алгоритм установления изоморфизма произвольной пары планарных графов. [13]
Страницы: 1