The 23 references with contexts in paper G. Ivanova S., V. Ovchinnikov A., В. Овчинников А., Г. Иванова С. (2016) “Полная характеристика структуры неориентированного графа // Completely Described Undirected Graph Structure” / spz:neicon:technomag:y:2016:i:4:p:106-123

1
Овчинников В.А. Графы в задачах анализа и синтеза структур сложных систем. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 423 с.
Total in-text references: 3
  1. In-text reference with the coordinate start=1867
    Prefix
    При формализованном установлении идентичности сложных систем их структуры представляют различного вида графами: ультраграфами HU (X, U), гиперграфами H(X, U), ориентированными G  (X, U) и неориентированными G~(X, U) графами, где X – множество вершин, U – множество ребер
    Exact
    [1]
    Suffix
    . Если граф является адекватной моделью системы в смысле полноты и правильности отображения информации, полностью характеризующей систему, задача установления идентичности систем сводится к определению изоморфизма их моделей.

  2. In-text reference with the coordinate start=15377
    Prefix
    Результат работы алгоритма – вектор Code кодов корней деревьев кратчайших цепей размером n. Схема алгоритма показана на рис. 5. Наука и образование. МГТУ им. Н.Э. Баумана 113 1 Начало xt Î X XF:=[xt] XB:=
    Exact
    [1]
    Suffix
    nt:=1 Tree[nt].num:=xt |XF|<n XUr:=Î , XUrr:=Î xi Î XB Sx:=F1(xi.num)\XF xd Î Sx 2 2.1 2.2 2.3 2.4 2.5 Нет Да 2.5.1 2.5.2 2.5.2.1 2.5.2.2 Tree[xi].kson:=0 2.5.2.3 2.5.2.3.1 2.5.2.3.2 2.5.2.3.3 nt:=nt+1 Tree[xi].kson:=Tree[xi].kson+1 Tree[xi].

  3. In-text reference with the coordinate start=15722
    Prefix
    :=1 Tree[nt].num:=xt |XF|<n XUr:=Î , XUrr:=Î xi Î XB Sx:=F1(xi.num)\XF xd Î Sx 2 2.1 2.2 2.3 2.4 2.5 Нет Да 2.5.1 2.5.2 2.5.2.1 2.5.2.2 Tree[xi].kson:=0 2.5.2.3 2.5.2.3.1 2.5.2.3.2 2.5.2.3.3 nt:=nt+1 Tree[xi].kson:=Tree[xi].kson+1 Tree[xi].S[Tree[xi].kson]:=nt 2.5.2.3.4 Tree[nt].num:=xd ДаНет 2.5.2.3.5 xd Î XUr 2.5.2.3.6 XUr:=XUr.xd 2.5.2.3.7 XUrr:=XUrr.nt 2.5.3 2.5.4 XF:=XF.XUr XB:=XUrr Tree
    Exact
    [1]
    Suffix
    .code:=CODE(1) Конец 2.6 3 Рис. 5. Схема алгоритма получения кодов корней деревьев кратчайших цепей Наука и образование. МГТУ им. Н.Э. Баумана 114 Условные обозначения, используемые в описании алгоритма: XF – множество вершин графа G, к которым уже найдены кратчайшие пути; XB – множество вершин графа G, из которых будут строиться ветви на очередном шаге декомпозиции в ширину; XUr – множес

2
Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 288 с. Наука и образование. МГТУ им. Н.Э. Баумана 117
Total in-text references: 2
  1. In-text reference with the coordinate start=2587
    Prefix
    Наука и образование. МГТУ им. Н.Э. Баумана 106 Широко известны алгоритмы распознавания изоморфизма графов, основанные на использовании локальных характеристик вершин и реализующие метод поиска в глубину с возвращением
    Exact
    [2–6]
    Suffix
    . В последние годы появились эвристические алгоритмы, использующие комбинации локальных инвариантов [7–9]. Все эти алгоритмы не накладывают ограничений на структуру графа и имеют невысокую емкостную сложность.

  2. In-text reference with the coordinate start=10854
    Prefix
    В общем случае графы G~(X, U) и G~(Y, V) будут изоморфными, если существует взаимно однозначное соответствие X  Y, U  V, такое, что если вершины xi, xj  X соответствуют вершинам yk, yl  Y, то для всех ребер, соединяющих вершины xi, xj, существуют ребра, соединяющие вершины yk, yl
    Exact
    [2]
    Suffix
    :   . (2) Поскольку множество деревьев всех кратчайших цепей сохраняет отношения инцидентности вершин и ребер, следовательно, и смежности вершин графа, для графов G ~ (X, U) и G ~ (Y, V) с учетом справедливости (1) условие (2) будет выполняться.

3
Овчинников В.А. Вычислительная сложность алгоритмических моделей задач идентификации и покрытия схем ЭВМ // Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 1992. No 2. С. 31-42.
Total in-text references: 1
  1. In-text reference with the coordinate start=2587
    Prefix
    Наука и образование. МГТУ им. Н.Э. Баумана 106 Широко известны алгоритмы распознавания изоморфизма графов, основанные на использовании локальных характеристик вершин и реализующие метод поиска в глубину с возвращением
    Exact
    [2–6]
    Suffix
    . В последние годы появились эвристические алгоритмы, использующие комбинации локальных инвариантов [7–9]. Все эти алгоритмы не накладывают ограничений на структуру графа и имеют невысокую емкостную сложность.

4
Ullmann J.R. An Algorithm for Subgraph Isomorphism // Journal of the Association for Computing Machinery (JACM). 1976. Vol. 23, no. 1. P. 31-42. DOI: 10.1145/321921.321925
Total in-text references: 1
  1. In-text reference with the coordinate start=2587
    Prefix
    Наука и образование. МГТУ им. Н.Э. Баумана 106 Широко известны алгоритмы распознавания изоморфизма графов, основанные на использовании локальных характеристик вершин и реализующие метод поиска в глубину с возвращением
    Exact
    [2–6]
    Suffix
    . В последние годы появились эвристические алгоритмы, использующие комбинации локальных инвариантов [7–9]. Все эти алгоритмы не накладывают ограничений на структуру графа и имеют невысокую емкостную сложность.

5
Cordella L.P., Foggia P., Sansone C., Vento M. A (sub)graph isomorphism algorithm for matching large graphs // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2004. Vol. 26, no. 10. P. 1367-1372. DOI: 10.1109/TPAMI.2004.75
Total in-text references: 1
  1. In-text reference with the coordinate start=2587
    Prefix
    Наука и образование. МГТУ им. Н.Э. Баумана 106 Широко известны алгоритмы распознавания изоморфизма графов, основанные на использовании локальных характеристик вершин и реализующие метод поиска в глубину с возвращением
    Exact
    [2–6]
    Suffix
    . В последние годы появились эвристические алгоритмы, использующие комбинации локальных инвариантов [7–9]. Все эти алгоритмы не накладывают ограничений на структуру графа и имеют невысокую емкостную сложность.

6
Cordella L.P., Foggia P., Sansone C., Vento M. An Improved Algorithm for Matching Large Graphs // Proc. of the 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Cuen, 2001. P. 149-159.
Total in-text references: 1
  1. In-text reference with the coordinate start=2587
    Prefix
    Наука и образование. МГТУ им. Н.Э. Баумана 106 Широко известны алгоритмы распознавания изоморфизма графов, основанные на использовании локальных характеристик вершин и реализующие метод поиска в глубину с возвращением
    Exact
    [2–6]
    Suffix
    . В последние годы появились эвристические алгоритмы, использующие комбинации локальных инвариантов [7–9]. Все эти алгоритмы не накладывают ограничений на структуру графа и имеют невысокую емкостную сложность.

7
Dehmer M., Grabner M., Mowshowitz A., Emmert-Streib F. An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants // Advances in Computational Mathematics. 2013. Vol. 39, no. 2. P. 311-325. DOI: 10.1007/s10444-012-9281-0
Total in-text references: 1
  1. In-text reference with the coordinate start=2693
    Prefix
    Баумана 106 Широко известны алгоритмы распознавания изоморфизма графов, основанные на использовании локальных характеристик вершин и реализующие метод поиска в глубину с возвращением [2–6]. В последние годы появились эвристические алгоритмы, использующие комбинации локальных инвариантов
    Exact
    [7–9]
    Suffix
    . Все эти алгоритмы не накладывают ограничений на структуру графа и имеют невысокую емкостную сложность. Однако, чем больше кратность характеристик вершин графов, тем больше число вариантов возможных подстановок вершин при распознавании изоморфизма таких графов.

8
McKay B.D., Piperno A. Practical graph isomorphism, II // Journal of Symbolic Computation. 2014. Vol. 60. P. 94-112. DOI: 10.1016/j.jsc.2013.09.003
Total in-text references: 1
  1. In-text reference with the coordinate start=2693
    Prefix
    Баумана 106 Широко известны алгоритмы распознавания изоморфизма графов, основанные на использовании локальных характеристик вершин и реализующие метод поиска в глубину с возвращением [2–6]. В последние годы появились эвристические алгоритмы, использующие комбинации локальных инвариантов
    Exact
    [7–9]
    Suffix
    . Все эти алгоритмы не накладывают ограничений на структуру графа и имеют невысокую емкостную сложность. Однако, чем больше кратность характеристик вершин графов, тем больше число вариантов возможных подстановок вершин при распознавании изоморфизма таких графов.

9
Попов А.Ю. Реализация алгоритмов обхода графов в вычислительной системе с многими потоками команд и одним потоком данных // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2015. No 10. С. 453-472. DOI: 10.7463/1015.0820736
Total in-text references: 1
  1. In-text reference with the coordinate start=2693
    Prefix
    Баумана 106 Широко известны алгоритмы распознавания изоморфизма графов, основанные на использовании локальных характеристик вершин и реализующие метод поиска в глубину с возвращением [2–6]. В последние годы появились эвристические алгоритмы, использующие комбинации локальных инвариантов
    Exact
    [7–9]
    Suffix
    . Все эти алгоритмы не накладывают ограничений на структуру графа и имеют невысокую емкостную сложность. Однако, чем больше кратность характеристик вершин графов, тем больше число вариантов возможных подстановок вершин при распознавании изоморфизма таких графов.

10
Luks E.M. Isomorphism of graphs of bounded valence can be tested in polynomial time // Proc. of the 21st IEEE FOCS Symp. 1980. P. 42-49.
Total in-text references: 1
  1. In-text reference with the coordinate start=3221
    Prefix
    В связи с этим вычислительная сложность этих алгоритмов может меняться от полиномиальной до экспоненциальной в зависимости от числа вершин с одинаковыми характеристиками. Известно, что задача изоморфизма полиномиально разрешима для некоторых классов графов
    Exact
    [10–12]
    Suffix
    . В частности для планарных графов, графов с ограниченной степенью вершин, графов с ограниченной кратностью собственных значений из спектра матрицы смежности построены эффективные алгоритмы решения этой задачи.

11
Hoffmann C.M. Group-Theoretic Algorithms and Graph Isomorphism // Lecture Notes in Computer Science. 1982. Chap. V. P. 127-138.
Total in-text references: 1
  1. In-text reference with the coordinate start=3221
    Prefix
    В связи с этим вычислительная сложность этих алгоритмов может меняться от полиномиальной до экспоненциальной в зависимости от числа вершин с одинаковыми характеристиками. Известно, что задача изоморфизма полиномиально разрешима для некоторых классов графов
    Exact
    [10–12]
    Suffix
    . В частности для планарных графов, графов с ограниченной степенью вершин, графов с ограниченной кратностью собственных значений из спектра матрицы смежности построены эффективные алгоритмы решения этой задачи.

12
Babai L., Grigoryev D.Yu., Mount D.M. Isomorphism of graphs with bounded eigenvalue multiplicity // Proceedings of the 14 th annual ACM symposium on Theory of computing (STOC '82). 1982. P. 310-324. DOI: 10.1145/800070.802206
Total in-text references: 1
  1. In-text reference with the coordinate start=3221
    Prefix
    В связи с этим вычислительная сложность этих алгоритмов может меняться от полиномиальной до экспоненциальной в зависимости от числа вершин с одинаковыми характеристиками. Известно, что задача изоморфизма полиномиально разрешима для некоторых классов графов
    Exact
    [10–12]
    Suffix
    . В частности для планарных графов, графов с ограниченной степенью вершин, графов с ограниченной кратностью собственных значений из спектра матрицы смежности построены эффективные алгоритмы решения этой задачи.

13
Faizullin R.T., Prolubnikov A.V. An Algorithm of the Spectral Splitting for the Double Permutation Cipher // Pattern Recognition and Image Analysis. 2002. Vol. 12, no. 4. P. 365375. Режим доступа: http://www.omgtu.ru/general_information/faculties/radio_engineering_department/departme nt_of_quot_integrated_protection_of_information_quot/files/theses/publications/Prolubniko vFaizullinPattern.pdf (дата обращения 01.03.2016).
Total in-text references: 1
  1. In-text reference with the coordinate start=3610
    Prefix
    В частности для планарных графов, графов с ограниченной степенью вершин, графов с ограниченной кратностью собственных значений из спектра матрицы смежности построены эффективные алгоритмы решения этой задачи. Поскольку эти алгоритмы используют специфические структурные характеристики графов, область их эффективного применения ограничена указанными классами графов. В работах
    Exact
    [13, 14]
    Suffix
    предлагается алгоритм распознавания изоморфизма ОС2-графов полиномиальный как по времени, так и по памяти. Этот алгоритм работает со спектральными характеристиками графов и имеет вычислительную сложность не хуже O(n4).

14
Пролубников А.В. Прямой алгоритм проверки изоморфизма графов // Компьютерная оптика. 2007. Т. 31, No 3. С. 86-92.
Total in-text references: 1
  1. In-text reference with the coordinate start=3610
    Prefix
    В частности для планарных графов, графов с ограниченной степенью вершин, графов с ограниченной кратностью собственных значений из спектра матрицы смежности построены эффективные алгоритмы решения этой задачи. Поскольку эти алгоритмы используют специфические структурные характеристики графов, область их эффективного применения ограничена указанными классами графов. В работах
    Exact
    [13, 14]
    Suffix
    предлагается алгоритм распознавания изоморфизма ОС2-графов полиномиальный как по времени, так и по памяти. Этот алгоритм работает со спектральными характеристиками графов и имеет вычислительную сложность не хуже O(n4).

15
Погребной В.К. Алгоритм решения задачи определения изоморфизма гиперграфов // Известия Томского политехнического университета. 2010. Т. 317, No 5. С. 16-21. РеНаука и образование. МГТУ им. Н.Э. Баумана 118 жим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2010/v317/i5/03.pdf (дата обращения 01.03.2016).
Total in-text references: 1
  1. In-text reference with the coordinate start=4137
    Prefix
    Алгоритм использует инвариант, представляющий собой кортеж произведений собственных значений модифицированной матрицы смежности графа и собственных значений матриц подграфов, полученных из исходного удалением i-ой вершины. Алгоритм относится к классу алгоритмов ограниченного применения. В работах
    Exact
    [15–20]
    Suffix
    предложен метод интеграции структурных различий – вычисления для каждой вершины графа уникальной структурной характеристики. Интегральный описатель структуры графа в виде вектора кодовых чисел вершин используется в качестве его полного инварианта.

16
Погребной В.К. Метод интеграции структурных различий в графовых моделях и его применение для описания структур // Известия Томского политехнического университета. 2011. Т. 318, No 5. С. 10-16. Режим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2011/v318/i5/02.pdf (дата обращения 01.03.2016).
Total in-text references: 1
  1. In-text reference with the coordinate start=4137
    Prefix
    Алгоритм использует инвариант, представляющий собой кортеж произведений собственных значений модифицированной матрицы смежности графа и собственных значений матриц подграфов, полученных из исходного удалением i-ой вершины. Алгоритм относится к классу алгоритмов ограниченного применения. В работах
    Exact
    [15–20]
    Suffix
    предложен метод интеграции структурных различий – вычисления для каждой вершины графа уникальной структурной характеристики. Интегральный описатель структуры графа в виде вектора кодовых чисел вершин используется в качестве его полного инварианта.

17
Погребной В.К. Решение задачи определения изоморфизма графов, представленных атрибутными матрицами // Известия Томского политехнического университета. 2012. Т. 321, No 5. С. 52-56. Режим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2012/v321/i5/11.pdf (дата обращения 01.03.2016).
Total in-text references: 1
  1. In-text reference with the coordinate start=4137
    Prefix
    Алгоритм использует инвариант, представляющий собой кортеж произведений собственных значений модифицированной матрицы смежности графа и собственных значений матриц подграфов, полученных из исходного удалением i-ой вершины. Алгоритм относится к классу алгоритмов ограниченного применения. В работах
    Exact
    [15–20]
    Suffix
    предложен метод интеграции структурных различий – вычисления для каждой вершины графа уникальной структурной характеристики. Интегральный описатель структуры графа в виде вектора кодовых чисел вершин используется в качестве его полного инварианта.

18
Погребной В.К., Погребной А.В. Полиномиальный алгоритм вычисления полного инварианта графа на основе интегрального описателя структуры // Известия Томского политехнического университета. 2013. Т. 323, No 5. С. 152-159. Режим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2013/v323/i5/25.pdf (дата обращения 01.03.2016).
Total in-text references: 1
  1. In-text reference with the coordinate start=4137
    Prefix
    Алгоритм использует инвариант, представляющий собой кортеж произведений собственных значений модифицированной матрицы смежности графа и собственных значений матриц подграфов, полученных из исходного удалением i-ой вершины. Алгоритм относится к классу алгоритмов ограниченного применения. В работах
    Exact
    [15–20]
    Suffix
    предложен метод интеграции структурных различий – вычисления для каждой вершины графа уникальной структурной характеристики. Интегральный описатель структуры графа в виде вектора кодовых чисел вершин используется в качестве его полного инварианта.

19
Погребной А.В. Полный инвариант графа и алгоритм его вычисления // Известия Томского политехнического университета. Информационные технологии. 2014. Т. 325, No 5. С. 110-122. Режим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2014/v325/i5/14.pdf (дата обращения 01.03.2016).
Total in-text references: 2
  1. In-text reference with the coordinate start=4137
    Prefix
    Алгоритм использует инвариант, представляющий собой кортеж произведений собственных значений модифицированной матрицы смежности графа и собственных значений матриц подграфов, полученных из исходного удалением i-ой вершины. Алгоритм относится к классу алгоритмов ограниченного применения. В работах
    Exact
    [15–20]
    Suffix
    предложен метод интеграции структурных различий – вычисления для каждой вершины графа уникальной структурной характеристики. Интегральный описатель структуры графа в виде вектора кодовых чисел вершин используется в качестве его полного инварианта.

  2. In-text reference with the coordinate start=4632
    Prefix
    Разработаны полиномиальные алгоритмы распознавания изоморфизма неориентированных графов и гиперграфов. Указанные работы внесли существенный вклад в развитие методов инвариантного представления графов и анализа их структур. В работе
    Exact
    [19]
    Suffix
    приведена предельная оценка суммарного объема вычислений при определении полного инварианта неориентированного графа с n вершинами и m ребрами в виде L(G)  (n, m) n 2 , где (n, m) – объем вычислений, затрачиваемый для выполнения одного шага интеграции.

20
Погребной В.К., Погребной А.В. Исследование полиномиальности метода вычисления интегрального описателя структуры графа // Известия Томского политехнического университета. 2013. Т. 323, No 5. С. 146-151. Режим доступа: http://www.lib.tpu.ru/fulltext/v/Bulletin_TPU/2013/v323/i5/24.pdf (дата обращения 01.03.2016).
Total in-text references: 1
  1. In-text reference with the coordinate start=4137
    Prefix
    Алгоритм использует инвариант, представляющий собой кортеж произведений собственных значений модифицированной матрицы смежности графа и собственных значений матриц подграфов, полученных из исходного удалением i-ой вершины. Алгоритм относится к классу алгоритмов ограниченного применения. В работах
    Exact
    [15–20]
    Suffix
    предложен метод интеграции структурных различий – вычисления для каждой вершины графа уникальной структурной характеристики. Интегральный описатель структуры графа в виде вектора кодовых чисел вершин используется в качестве его полного инварианта.

21
Babai L. Graph Isomorphism in Quasipolynomial Time // ArXiv.org: website. Режим доступа: http://arxiv.org/abs/1512.03547 (дата обращения 15.02.2016).
Total in-text references: 1
  1. In-text reference with the coordinate start=5120
    Prefix
    Если один шаг интеграции без учета упорядочивания вектора кодовых чисел требует n2 операций, то асимптотическая оценка вычислительной сложности алгоритма вычисления полного инварианта неориентированного графа равна O(n4). В работе
    Exact
    [21]
    Suffix
    предложен метод определения изоморфизма графов с квазиполиномиальной оценкой вычислительной сложности, где степень n является функцией log n. Цель настоящей работы – предложить и обосновать такую характеристику графа, которая определяла бы его структуру с точностью до изоморфизма, и разработать алгоритм ее получения, имеющий вычислительную сложность меньше O(n 4 ).

22
Ахо А.B., Хопкрофт Д.Э., Ульман Д.Д. Построение и анализ вычислительных алгоритмов: пер. с англ. М.: Мир, 1979. 536 с.
Total in-text references: 5
  1. In-text reference with the coordinate start=6371
    Prefix
    характеристики неориентированного графа Обоснованием полной характеристики структуры неориентированного графа являются изложенная ниже теорема о возможности сведения задачи установления изоморфизма неориентированных графов к задаче определения изоморфизма их расщепления на деревья всех кратчайших, в смысле числа ребер, цепей из каждой вершины в остальные и способ кодирования структуры дерева
    Exact
    [22]
    Suffix
    . Начнем с предположения, что полной характеристикой графа, определяющей его структуру с точностью до изоморфизма, является совокупность кратчайших, в смысле числа ребер, цепей из каждой вершины во все остальные.

  2. In-text reference with the coordinate start=12944
    Prefix
    x7 x1 x5 x1 x1 x5 No1 x3 No5 x4 x2 x6 x2 x7 x6 x3 x2 x7 x3 x1x1x1 xxx5x5x454 No6 x6 x2 x1 No2 x3 x5 x6 x2x5 x3 x7 xx41x3 x7 xx54 x7 x7 x7x7 x3 x1 No3 x2x4x5 x6 x1 No7 x4x5 x3 x7 x2 x6 x2 xx66 x6x1 Рис. 3. Граф, все деревья кратчайших цепей которого имеют различную структуру 2. Кодирование структуры деревьев Кодирование дерева использует идею приписывания вершинам дерева кодов, изложенную в
    Exact
    [22]
    Suffix
    . Код корня описывает структуру дерева и является его полным инвариантом – деревья изоморфны тогда и только тогда, когда коды их корней совпадают. Коды корней строятся, начиная с листьев дерева. Каждому листу дерева присваивается код, состоящий из открывающей и закрывающей скобок «()».

  3. In-text reference with the coordinate start=13783
    Prefix
    Баумана 112 x1 x2 No1 x3 x4 x6 ((( ),( )),(( )) ,( )) 1 ( ) ( ) (( ),( )) ( )( ) (( )) 234 x5 x5 567 Рис. 4. Пример кодирования вершин дерева В вершинах дерева указаны их номера в порядке получения, справа от вершин указаны их коды. На основании доказанной выше теоремы и положений работы
    Exact
    [22]
    Suffix
    в качестве интегральной характеристики графа предлагается множество кодов корней деревьев всех кратчайших цепей из каждой вершины в остальные. 3. Алгоритм определения кодов корней деревьев кратчайших цепей Определение кодов корней деревьев кратчайших цепей выполняется в два этапа: сначала строится дерево, а потом получается код его корня.

  4. In-text reference with the coordinate start=16327
    Prefix
    которым уже найдены кратчайшие пути; XB – множество вершин графа G, из которых будут строиться ветви на очередном шаге декомпозиции в ширину; XUr – множество вершин графа G, найденных на рассматриваемом уровне; Ur – номер текущего уровня дерева декомпозиции в ширину; Sx – множество сыновей вершины; CODE(xt) – функция, рекурсивно вычисляющая коды вершин дерева по алгоритму, предложенному в
    Exact
    [22]
    Suffix
    .В ходе работы алгоритма выполняется лексикографическая сортировка кодов вершин деревьев, обеспечивающая независимость кодов от порядка нумерации вершин деревьев. Согласно [22] вычислительная сложность получения кода – кортежа корня дерева не превышает O(nT), т. е.

  5. In-text reference with the coordinate start=16504
    Prefix
    найденных на рассматриваемом уровне; Ur – номер текущего уровня дерева декомпозиции в ширину; Sx – множество сыновей вершины; CODE(xt) – функция, рекурсивно вычисляющая коды вершин дерева по алгоритму, предложенному в [22].В ходе работы алгоритма выполняется лексикографическая сортировка кодов вершин деревьев, обеспечивающая независимость кодов от порядка нумерации вершин деревьев. Согласно
    Exact
    [22]
    Suffix
    вычислительная сложность получения кода – кортежа корня дерева не превышает O(nT), т. е. O(n2). Таким образом, вычислительная сложность построения деревьев кратчайших цепей и получения кодов их корней для всех вершин графа не превышает O(n3). 4.

23
Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ: пер. с англ. М.: МЦНМО, 2000. 960 с. Наука и образование. МГТУ им. Н.Э. Баумана 119
Total in-text references: 1
  1. In-text reference with the coordinate start=7068
    Prefix
    Отсюда следует, что деревья двух сопоставленных друг другу вершин изоморфных графов должны иметь одинаковую структуру, не зависящую от порядка записи вершин в их образах относительно предиката смежности F1(X, X). Нетрудно убедиться в том, что предположение ошибочно, рассмотрев рис. 1. Деревья No1 и No2 получены процедурой BFS просмотра графа в ширину
    Exact
    [23]
    Suffix
    при указанных порядках записи вершин в образе F1x1 (напомним, что при построении деревьев кратчайших цепей этой процедурой вершины в дереве не повторяются). Порядок записи вершин в образах остальных вершин графа одинаковый.