Топологическая сопряженность градиентно-подобных потоков на поверхностях и эффективные алгоритмы ее различения

Полный текст

ОГЛАВЛЕНИЕ Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468 1. Необходимые сведения из теории потоков на многообразиях . . . . . . . . . . . . . . . 468 1.1. Общие понятия непрерывных динамических систем . . . . . . . . . . . . . . . . . 468 1.2. Гиперболические неподвижные точки . . . . . . . . . . . . . . . . . . . . . . . . . . 469 1.3. Гиперболические периодические орбиты . . . . . . . . . . . . . . . . . . . . . . . . 469 1.4. Структурно устойчивые и Ω-устойчивые потоки . . . . . . . . . . . . . . . . . . . . 469 2. Топологическая сопряженность градиентно-подобных потоков на поверхностях . . . . 470 2.1. Динамика градиентно-подобных потоков . . . . . . . . . . . . . . . . . . . . . . . . 470 2.2. Отсутствие модулей топологической сопряженности . . . . . . . . . . . . . . . . . 471 3. Эффективные алгоритмы различения эквивалентности (сопряженности) градиентно- подобных потоков на поверхностях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 3.1. Необходимые сведения из теории графов и алгоритмов . . . . . . . . . . . . . . . 474 3.2. Граф Пейшото . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 3.3. Модифицированный граф Пейшото . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 3.4. Граф Вонга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480 3.5. Круговая схема Флейтас . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 3.6. Трехцветный граф Ошемкова-Шарко . . . . . . . . . . . . . . . . . . . . . . . . . 483 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 © Российский университет дружбы народов, 2022 This work is licensed under a Creative Commons Attribution 4.0 International License https://creativecommons.org/licenses/by-nc/4.0/legalcode 467 Введение Напомним, что потоки на многообразии M называются топологически эквивалентными, если существует гомеоморфизм h: M → M, отображающий траектории потока ft в траектории потока с сохранением направления движения по траекториям. Два потока называются топологически сопряженными, если выполняется условие; это означает, что h отображает траектории в траектории, сохраняя не только направление, но и время движения по траекториям. Первые результаты в этой области восходят к классической работе А.А. Андронова и Л.С. Понтрягина [1] 1937 года. Они рассмотрели систему дифференциальных уравнений, заданных в компактной части плоскости, ограниченной кривой без контакта. Для таких систем ими было введено понятие грубости, получен критерий грубости и доказана всюду плотность грубых систем среди всех систем в компактной части плоскости. Согласно критерию Андронова- Понтрягина система является грубой тогда и только тогда, когда ее неблуждающее множество состоит из конечного числа гиперболических неподвижных точек, конечного числа гиперболических периодических орбит, и не имеет связок. Основной трудностью в обобщении этого результата на случай произвольных ориентируемых поверхностей положительного рода является возможность нового типа движения - незамкнутая рекуррентная траектория. Отсутствие таких траекторий для грубых потоков без особенностей на 2-торе была доказана А.Г. Майером [4] в 1939 году. В работах [13, 14] М. Пейшото ввел эквивалентное грубости понятие структурной устойчивости, снимающее требование близости к тождественному гомеоморфизма, осуществляющего эквивалентность близких систем. Он доказал, что критерий грубости Андронова-Понтрягина дословно переносится на потоки, заданные на произвольных поверхностях. Выделенный класс векторных полей был назван классом векторных полей Морса-Смейла после того как в 1967 году С. Смейл [18] обобщил свойства грубых систем Андронова-Понтрягина на случай произвольной размерности. Напомним, что поток Морса-Смейла называется градиентно-подобным, если его неблуждающее множество не содержит периодических орбит. Такие потоки имеют наиболее простую динамику, что вдохновляло многих математиков на поиски инвариантов их топологической эквивалентности. В предположениях различной общности на рассматриваемый класс градиентно-подобных потоков были получены следующие инварианты: схема Леонтович-Майера (Е.А. Леонтович, А.Г. Майер) [2, 3], граф Пейшото (М. Пейшото) [15], оснащенный граф Пейшото (В.З. Гринес, О.В. Починка) [8], двуцветный граф (К. Вонг) [19], трехцветный граф (А. Ошемков, В. Шарко) [5], круговая схема (Г. Флейтас) [7]. Таким образом, проблема классификации градиентно-подобных потоков на поверхностях с точки зрения топологической эквивалентности решена исчерпывающим образом. В работах [10, 11] доказано, что для градиентно-подобных потоков классы топологической эквивалентности совпадают с классами топологической сопряженности. Полученный результат позволяет использовать для топологической сопряженности градиентно-подобных потоков любые инварианты их эквивалентности. В работе [11] также построены эффективные алгоритмы различения для перечисленных комбинаторных инвариантов градиентно-подобных потоков на поверхностях, т. е. алгоритмы, ограниченные некоторым полиномом от длины входной информации. Настоящее исследование является обзором результатов по топологической сопряженности градиентно-подобных потоков на поверхностях и эффективным алгоритмам ее различения. 1. Необходимые сведения из теории потоков на многообразиях 1.1. Общие понятия непрерывных динамических систем. Пусть M - гладкое замкнутое n-многообразие с метрикой d. Гладким потоком на M называется гладкое отображение φ: M × R → M с групповыми свойствами: 1) φ(x,0) = x ∀x ∈ M; 2) φ(φ(x,t),s) = φ(x,t + s) ∀x ∈ M, ∀s,t ∈ R. В дальнейшем будем использовать обозначение φt(x) = φ(x,t), x ∈ M, t ∈ R. Заметим, что при фиксированном t ∈ R отображение φt : M → M является диффеоморфизмом, поэтому поток еще называют однопараметрической группой диффеоморфизмов, действующих на многообразии M. Траекторией или орбитой точки x ∈ M называется множество Ox = {φt(x),t ∈ R}. Любая орбита потока либо состоит из одной точки, и в этом случае эта точка называется неподвижной, либо гомеоморфна окружности, и в этом случае любая точка орбиты называется периодической, либо является инъективно иммерсированной прямой. Полагают, что все траектории потока, отличные от неподвижной точки, ориентированы в соответствии с возрастанием параметра t. С каждым потоком φt : M → M связано касающееся траекторий потока векторное поле . Два потока называются топологически эквивалентными, если существует гомеоморфизм, переводящий траектории потока φt в траектории потока с сохранением ориентации. Если при этом гомеоморфизм h обладает свойством для любого t ∈ R, то потоки называются топологически сопряженными. 1.2. Гиперболические неподвижные точки. Пусть p ∈ M - неподвижная точка потока φt : M → M. Устойчивым и неустойчивым, соответственно, многообразием неподвижной точки p называются множества при t → +∞} и при t → -∞}. Устойчивой (неустойчивой) сепаратрисой неподвижной точки p называется компонента линейной связности множества Wps \ p(Wpu \ p). С неподвижной точкой потока помимо касательного векторного поля x˙ = F(x) связано линеаризованное векторное поле x˙ = A(x - p), где A - матрица частных производных отображения F(x) в точке p (матрица Якоби). Неподвижная точка p потока φt называется гиперболической, если собственные значения матрицы A не имеют нулевых действительных частей. Напомним, что неподвижная точка p диффеоморфизма f : M → M называется гиперболической, если матрица частных производных отображения f(x) в точке p (матрица Якоби) не имеет собственных значений по модулю равных единице. 1.3. Гиперболические периодические орбиты. Пусть c - замкнутая траектория потока φt : M → M. Устойчивым и неустойчивым, соответственно, многообразием замкнутой траектории c называются множества Wcs = {x ∈ M : minp∈c d(p,φt(x)) → 0 при t → +∞} и Wcu = {x ∈ M : minp∈c d(p,φt(x)) → 0 при t → -∞}. Пусть p ∈ c и Σp - (n - 1)-мерный диск, трансверсальный в точке p вектору, касательному к периодической траектории, называемый секущей Пуанкаре. Тогда в некоторой окрестности Vp ⊂ Σp точки p для каждой точки x ∈ Vp существует значение τx > 0 такое, что φτx(x) ∈ Σp и φt(x) ∈/ Σp для любого 0 < t < τx. Отображение f : Vp → Σp, определенное формулой f(x) = φτx(x), x ∈ Vp, называется отображением последования, или отображением Пуанкаре. Заметим, что точка p является неподвижной точкой отображения последования. Периодическая траектория c называется гиперболической, если точка p является гиперболической неподвижной точкой отображения Пуанкаре f : Vp → Fp(Vp). 1.4. Структурно устойчивые и Ω-устойчивые потоки. Точка x ∈ M называется блуждающей точкой потока φt : M → M, если существует открытая окрестность Ux точки x такая, что φt(Ux) ∩ Ux = ∅ для всех t > 1. В противном случае точка x называется неблуждающей. Множество всех неблуждающих точек потока φt называется его неблуждающим множеством и обозначается Ωφt. Поток φt : M → M называется Ω-устойчивым, если существует окрестность U(φt) потока φt в пространстве C1(S ×R,S) с C1-топологией такая, что если, то потоки топологически эквивалентны. Поток φt : M → M называется структурно устойчивым, если существует окрестность U(φt) потока φt в пространстве C1(S × R,S) с C1-топологией такая, что если, то потоки φt и топологически эквивалентны. Поток называется потоком Морса-Смейла, если его неблуждающее множество состоит конечного числа гиперболических неподвижных точек и конечного числа гиперболических периодических орбит, чьи устойчивые и неустойчивые многообразия пересекаются трансверсально. Поток Морса-Смейла без периодических орбит называется градиентно-подобным потоком. В силу результатов [1, 13, 14] поток на поверхности является структурно устойчивым тогда и только тогда, когда он является потоком Морса-Смейла. Условие трансверсальности на поверхности означает, что у потока отсутствуют связки - траектории, соединяющие седловые точки. Из критерия Ω-устойчивости [16] следует, что неблуждающее множество Ω-устойчивого потока на поверхности состоит из конечного числа гиперболических периодических орбит и неподвижных точек, при этом последние не образуют циклов (см. рис. 1), т. е. наборов неподвижных точек p1,...,pk,pk+1 = p1 со свойством Fig. 1. Examples of cycles 2. Топологическая сопряженность градиентно-подобных потоков на поверхностях 2.1. Динамика градиентно-подобных потоков. Пусть ft - градиентно-подобный поток, заданный на поверхности S. Следующее предложение является локальной классификацией гиперболических неподвижных точек потока на поверхности с точностью до топологической сопряженности. Предложение 2.1 (см. [6, теорема 5.1, гл. 2], [17, теорема 7.1, гл. 4] и [10, лемма 1]). Пусть p -неподвижная гиперболическая точка потока ft: S → S. Тогда существует окрестность up ⊂ S точки p и гомеоморфизм на образ ψp : up → R2 такой, что поток ft|up топологически сопряжен с одним из следующих потоков: , т. е. для любого t, не выводящего точки за пределы up. В случае сопряжения с потоком неподвижная точка p называется стоком, седлом, источником, соответственно (см. рис. 2). Будем обозначать через Ω0ft, Ω1ft, Ω2ft множества всех стоков, седел, источников потока ft, соответственно. Рис. 2. Классификация в окрестности гиперболических неподвижных точек: a) сток, b) седло, c) источник Fig. 2. Classification in the neighborhood of hyperbolic fixed points: a) sink, b) saddle, c) source Предложение 2.2 (см. [18, следствие 5.3]). Пусть ft: S → S -градиентно-подобный поток. Тогда: 1) ; f f 2) Wpu (Wps) является гладким подмногообразием многообразия S, диффеоморфным Ri (R2-i) для любой неподвижной точки p ∈ Ωift; 3) для любой неустойчивой (устойчивой) сепаратрисы lσu (lσs) седловой точки σ существует сток ω (источник α) такой, что cl(); 4) для любого стока ω (источника α) существует хотя бы одна седловая точка σ с неустойчивой (устойчивой) сепаратрисой такой, что cl( {σ,α}). 2.2. Отсутствие модулей топологической сопряженности. В этом разделе мы доказываем факт о совпадении классов эквивалентности и топологической сопряженности для градиентноподобных потоков на поверхности. Теорема 2.1 (см. [11, теорема 7]). Градиентно-подобные потоки на замкнутой поверхности топологически сопряжены тогда и только тогда, когда они топологически эквивалентны. Доказательство. Необходимость условий теоремы очевидна, докажем их достаточность. Пусть S -замкнутая поверхность и ft: S → S - градиентно-подобный поток. Согласно пункту 1 предложения 2.2, замыкание любой блуждающей орбиты потока ft состоит из двух различных неподвижных точек p, q: cl. Поэтому обозначим эту траекторию через p,q, предполагая, что она направлена от p к q. Пусть -градиентно-подобный поток, топологически эквивалентный потоку ft, т. е. существует гомеоморфизм h: S → S, переводящий траектории потока ft в траектории потока и сохраняющий ориентации траекторий. В том числе h переводит неподвижные точки потока ft в неподвижные точки потока, поэтому будем обозначать для. Тогда для каждой блуждающей траектории pq потока ft. В силу предложения 2.1 потоки в некоторых окрестностях точек , соответственно, топологически сопряжены посредством некоторого гомеоморфизма . Пусть Fig. 3. Neighborhood uσ of the saddle σ σ - седловая точка потока ft. Не уменьшая общности, будем полагать, что окрестность uσ выбрана так, что ее граница состоит из четырех отрезков траекторий и четырех отрезков секущих (см. рис. 3), и отображение h-1hσ сохраняет сепаратрисы седла σ. Для точки x ∈ S обозначим через траекторию потока , проходящую через точку x. Положим . Продолжим hσ до гомеоморфизма по следующему правилу (см. рис. 4). Во-первых, hVσ|uσ = hσ. Во-вторых, для точки z ∈ (intVσ\cl(uσ)) положим {z0} = Oz ∩ ∂uσ и ftz(z0) = z, дляztz ∈ R; для точки z ∈ ∂Vσ\∂uσ положим tz таким, что |tz| = min{t ∈ R | f-t(z) ∈ ∂uσ} и z0 = f-t (z); тогда |t| . Рис. 4. Построение сопрягающего гомеоморфизма Fig. 4. Construction of a conjugating homeomorphism Пусть - объединение всех - гомеоморфизм, составленный из гомеоморфизмов hVσ. Продолжим гомеоморфизм hV до объемлющего сопрягающего гомеоморфизма. Для этого заметим, что замыкание T любой компоненты связности множества S\(V ∪Ωft) принадлежит бассейну некоторого стока ω. Поскольку гомеоморфизм h-1hσ сохраняет сепаратрисы седел, то существует замыкание единственной компоненты связности множества такой, что . Продолжим hV на T посредством сопрягающего гомеоморфизма hT . В силу предложения 2.1 потокив некоторых окрестностях точек, соответственно, топологически сопряжены посредством некоторого гомеоморфизма. Пусть γ ⊂ uω - кривая, ограничивающая на uω диск, содержащий. Пусть JT = γ ∩ T и a0, a1 - концы дуги JT . Тогда существуют седловые точки σ0,σ1 (возможно, σ0 = σ1) такие, что ai ∈ (JT ∩Vσi),i = 0,1. Аналогично, дуга ограничена точками a˜0,a˜1, принадлежащими , соответственно. Пусть t0,t1 ∈ R так, что - гомеоморфизм такой, что ρ(a˜i) = i, i = 0,1. Пусть . Определим произвольный гомеоморфизм так, что hJ(ai) = hV (ai), i = 0,1. Тогда каждая точка z множества T единственным образом определена точкой z0 = Oz ∩JT и значением tz ∈ R таким, что ftz(z0) = z. Определим гомеоморфизм по формуле . Наконец, определим сопрягающий гомеоморфизм H: S → S так, что H|V = hV , H|T = hT , и H|Ωft = h|Ωft. Таким образом, для градиентно-подобных потоков на поверхностях классы топологической эквивалентности совпадают с классами топологической сопряженности, что позволяет использовать для топологической сопряженности градиентно-подобных потоков любые инварианты их эквивалентности. 3. Эффективные алгоритмы различения эквивалентности (сопряженности) градиентно-подобных потоков на поверхностях 3.1. Необходимые сведения из теории графов и алгоритмов. В данном разделе мы приводим общие сведения из теории графов и алгоритмов. Напомним, что конечным графом Γ называется упорядоченная пара (B,E), где • B - непустое множество вершин; • E - множество пар вершин, называемых ребрами. Каждую из вершин a, b ребра ab называют инцидентной ребру ab и говорят, что вершины a, b соединены ребром ab. Валентностью вершины называется число инцидентных ей ребер. Если ребра представляют из себя упорядоченные пары вершин, то граф называется ориентированным. Граф называется связным, если любые две его вершины b0, bk можно соединить путем, т. е. последовательностью b0,b0b1,b1,...,bk-1,bk-1bk,bk, при этом k - длина пути. Если начало и конец пути совпадают, то путь называют циклом. Если обе вершины ребра совпадают, то ребро называется петлей. Подграфом графа Γ называется пара (B,˜ E˜), где B˜ ⊂ B, E˜ ⊂ E. Назовем k-подразбиением ребра e = ab операцию, в ходе которой ребро e удаляется из графа, и на его место добавляются новые вершины c1,c2,...,ck с ребрами ac1,c1c2,...,ck-1ck,ckb. Назовем k∗-подразбиением ребра e = ab операцию, в ходе которой ребро e удаляется из графа, и на его место добавляются новые вершины c1,c2,...,ck,d с ребрами ac1,c1c2,...,ck-1ck,ckb,c1d. Конечным мультиграфом Γ называется граф, для которого множество ребер E допускает включение одного и того же элемента по несколько раз. Для краткости будем называть мультиграф также просто графом. Граф Γ называется n-цветным, если множество его ребер является объединением n подмножеств, каждое из которых состоит из ребер одного и того же определенного цвета. Граф называется простым, если он не содержит петель и кратных ребер. Граф называется планарным, если существует его вложение в плоскость. Если существует вложение графа в поверхность, то граф называется вложимым в поверхность. Граф называется двудольным или биграфом, если множество его вершин можно разбить на две части таким образом, что не существует ребра, соединяющего две вершины из одной и той же части. Два графа называются изоморфными, если существует отображение, переводящее вершины и ребра графа Γ в вершины и рёбра графа Γ, соответственно, с сохранением, при наличии, цветов и направлений. Алгоритмы, различающие изоморфность графов с помощью количества операций, полиномиально зависящего от числа входных данных, называются эффективными, или полиномиальными. Приведем несколько известных результатов о существовании эффективных алгоритмов проверки изоморфности графов. Предложение 3.1 (см. [9]). Изоморфность двух n-вершинных планарных простых графов можно проверить за время O(n). Предложение 3.2 (см. [12]). Изоморфность двух n-вершинных простых графов, вложимых в поверхность рода g, можно проверить за время O(nO(g)). 3.2. Граф Пейшото. Пусть ft: S → S - градиентно-подобный поток. В работе [15] для потока ft построен ориентированный граф Γft (граф Пейшото). Вершины графа Γft соответствуют неподвижным точкам потока ft, ребра соответствуют ориентированным седловым сепаратрисам (см. рис. 5). На рис. 6 изображен пример неэквивалентных градиентно-подобных потоков с изоморфными ориентированными графами. Отсюда следует, что класс изоморфности графа не является полным инвариантом потока. По этой причине граф Γft оснащается так называемыми различающими множествами, в результате чего получается граф Пейшото ΓPft, который является полным топологическим инвариантом. Рис. 5. Пример градиентно-подобного потока ft и его графа Пейшото Γft Fig. 5. An example of a gradient-like ft flow and its Peixoto graph Γft Рис. 6. Два потока с изоморфными ориентированными графами Fig. 6. Two flows ft and with isomorphic directed graphs Γft and Именно, рассмотрим множество . Замыкание любой его компоненты связности называется ячейкой. Согласно [15], все ячейки градиентно-подобных потоков могут быть только трех типов, изображенных на рис. 7. Рис. 7. Типы ячеек градиентно-подобного потока; α - источник, σ, σ1, σ2 - седла, ω - сток Fig. 7. Cell types of gradient-like flow; α is a source, σ, σ1, σ2 are saddles, ω is a sink Различающим множеством называется подграф, соответствующий границе ячейки. Следовательно, различающие множества могут быть трех типов, соответствующих типам ячеек (см. рис. 8). Два графа Пейшото градиентно-подобных потоков , соответственно, называются изоморфными, если существует изоморфизм графов , сохраняющий различающие множества. Предложение 3.3 (см. [15, предложение 4.4]). Два градиентно-подобных потока топологически эквивалентны тогда и только тогда, когда их графы Пейшото изоморфны. Основным результатом настоящего раздела является следующая теорема. Теорема 3.1 (см. [11, теорема 1]). Пусть -градиентно-подобные потоки, заданные на поверхности S рода-их оснащенные n-вершинные графы Пейшото. Тогда изоморфность графов можно проверить за время O(nO(g)) для g > 0 и за время O(n) для g = 0. Доказательство. Идея построения алгоритма, устанавливающего изоморфность графов ΓPft, , состоит в сведении этих графов к простым, вложимым в поверхность S, графам таким, что изоморфны тогда и только тогда, когда изоморфны . Более детально. Во-первых, добавим по две соседних вершины валентности один к каждой седловой вершине графа ΓPft. Во-вторых, для каждого его подграфа типа 1 добавим по новой вершине и по четыре ребра, соединяющих новую вершину с остальными вершинами подграфа. В-третьих, применим 2∗-подразбиение к каждому ребру графа ΓPft, соединяющему седловую и стоковую вершины, и 1-подразбиение к ребру, соединяющему источниковую и седловую вершины. Получим граф Γ˜ft (см. рис. 9). Очевидно, Γ˜ft единственным образом строится по ΓPft. Покажем, что ΓPft также может быть единственным образом восстановлен по Γ˜ft. Вершина графа Γ˜ft является седловой в ΓPft тогда и только тогда, когда она инцидентна двум вершинам валентности один. Следовательно, все седловые вершины могут быть определены единственным образом. Пусть s - седловая вершина графа ΓPft. В графе Γ˜ft она инцидентна единственной вершине x валентности 3 и единственной вершине y валентности 2. Вершина x инцидентна единственной вершине x валентности 2, которая, в свою очередь, инцидентна отличной от x вершине w. Вершина w соответствует стоку, а sw - ребро графа , соответствующее Рис. 8. Градиентно-подобный поток ft на сфере S и его граф Пейшото ΓPft с подграфами Fig. 8. Gradient-like flow ft on the sphere S and its Peixoto graph ΓPft with subgraphs Рис. 9. Граф Пейшото с подграфами и его простой граф Γ˜ft Fig. 9. The Peixoto graph ΓPft with subgraphs and its simple graph Γ˜ft неустойчивой сепаратрисе. Вершина y инцидентна вершине a, отличной от s. Вершина a соответствует источнику, а as - ребро графа ΓPft, соответствующее устойчивой седловой сепаратрисе. Отличив стоковую, седловую и источниковую вершины графа ΓPft, а также седловые сепаратрисы, можно восстановить все вершины валентности 1, соответствующие источникам и стокам. Каждый подграф типа 2 или 3 полностью определяется такой вершиной. Следовательно, все подграфы этих типов могут быть найдены единственным образом Подграфы типа 1 единственным образом восстанавливаются по вершинам валентности 4, инцидентным двум различным седловым вершинам. Таким образом, графы изоморфны тогда и только тогда, когда изоморфны графы . Построение графов по графам может быть осуществлено за время O(n). Кроме того, графы оба имеют O(n) вершин. Поскольку графы вложимы в поверхность S, а добавление новых вершин и ребер не дает пересечений ребер во внутренних точках, то графы также вложимы в поверхность S. Согласно предложениям 3.1 и 3.2, изоморфность графов , а следовательно, и можно проверить за время O(nO(g)) для g > 0 и за время O(n) для g = 0. 3.3. Модифицированный граф Пейшото. В 2011 году В.З. Гринес и О.В. Починка [8] модифицировали граф Пейшото[1]. Именно, вместо различающих множеств они оснастили ориентированный граф Пейшото Γft порядками ребер, инцидентных вершинам, соответствующим стокам, и получили таким образом модифицированный граф Пейшото ΓGPft , являющийся полным инвариантом. Более детально. Пусть ω - сток потока- множество сепаратрис, содержащих ω в своем замыкании. Из предложения 2.1 следует, что существует 2-диск такой, что каждая сепаратриса l ⊂ Lω пересекает ∂Bω в единственной точке. Для вершины w, соответствующей ω, пусть Ew - множество ребер графа Γft, инцидентных w. Пусть Nw - мощность множества Ew. Пронумеруем элементы Ew следующим образом. Возьмем 2-диск Bω в бассейне ω и множество cω = ∂Bω. Зададим ориентацию против часовой стрелки на cω по отношению к Bω. Пронумеруем все ребра e1,...,eNw из Ew в соответствии с порядком соответствующих сепаратрис на cω, начиная с некоторой точки на cω. Эта нумерация всех элементов Ew называется согласованной с вложением сепаратрис. Два модифицированных графа Пейшото потоковназываются изоморфными, если существует изоморфизм ξ между такой, что перестановка , где , индуцированная изоморфизмом ξ, является степенью циклической перестановки для каждой вершины w, соответствующей стоку. Так, на рис. 6 вершина графа соответствует стоку и вершина соответствует источнику . Перенумеруем сепаратрисы ) седловых точек, принадлежащих устойчивому многообразию точки в соответствии с положительной ориентацией замкнутой кривой вокруг ). Введем нумерацию на множестве ), согласованную с вложением сепаратрис. Как мы уже заметили, графы изоморфны. Существует в точности два изоморфизма этих графов: изоморфизм ξ1 наложения Γft на граф и изоморфизм ξ2, являющийся композицией наложения и отражения относительно оси. Непосредственно проверяется, что изоморфизм ξ1 индуцирует перестановку , а изоморфизм ξ2 индуцирует перестановку . Ни одна из этих перестановок не является степенью циклической перестановки, в силу чего модифицированные графы неизоморфны. Предложение 3.4 (см. [8, теорема 3.2.1]). Градиентно-подобные потоки топологически эквивалентны тогда и только тогда, когда их модифицированные графы ΓGPft и изоморфны. Теорема 3.2 (см. [11, теорема 2]). Пусть-градиентно-подобные потоки на поверхности S рода -их модифицированные n-вершинные графы с m ребрами. Тогда изоморфизм графов может быть проверен за время O(nO(g)), если g > 0, и за время O(n), если g = 0. Доказательство. Для доказательства также будем использовать идею сведения модифицированного графа ΓGPft к простому Γ¯ft. Для каждой стоковой вершины w графа ΓGPft рассмотрим циклически упорядоченное множество Ew всех ребер, инцидентных w. Удалим из графа ΓGPft вершину w и все ребра, инцидентные w, добавим циклы с Nw вершинами к получившемуся графу; их вершины пронумерованы 1,...,Nw. Для каждого добавим неориентированное ребро между i-ой вершиной цикла и вершиной, отличной от w и инцидентной i-му ребру в Ew. Далее, добавим по две вершины валентности 1 к каждой седловой вершине графа ΓGPft и применим 1-подразбиение к каждому ориентированному ребру (см. рис. 10). Fig. 10. Modified Peixoto graph ΓGPft and its simple graph Γ¯ft Очевидно, Γ¯ft единственным образом строится по ΓGPft . Покажем, что ΓGPft также может быть единственным образом восстановлен по Γ¯ft. Действительно, седловые вершины графа ΓGPft - это вершины, инцидентные двум вершинам валентности 1. Каждая седловая вершина s соединяется с единственной вершиной x валентности 3 и единственной вершиной y валентности 2. Вершина y инцидентна отличной от седловой вершине a - это источниковая вершина. Вершины типа x образуют циклы, соответствующие стоковым точкам. Циклический порядок множества Ew определяется при обходе циклов. Ребро sx графа Γ¯GPft соответствует неустойчивой седловой сепаратрисе, а ребро sa - устойчивой. Следовательно, имея граф Γ¯ft, можно единственным образом восстановить граф ΓGPft . Таким образом, графы изоморфны тогда и только тогда, когда простые графы Γ¯ft и изоморфны. Построение графов по графам осуществляется за время O(n). Кроме того, каждый из графов имеет O(n) вершин. Поскольку добавление циклов к графам сохраняет их вложимость в поверхность S, то графы также вложимы в S. По предложениям 3.1 и 3.2, изоморфизм графов , а следовательно, и , может быть проверен за время O(nO(g)), если g > 0, и за время O(n), если g = 0. 3.4. Граф Вонга. Пусть ft - градиентно-подобный поток, заданный на ориентируемой поверхности S. Граф Вонга для такого потока - это граф, дуальный к графу Пейшото: вершины графа Вонга ΓWft соответствуют ячейкам потока ft, его ребра соответствуют седловым сепаратрисам и соединяют вершины, соответствующие ячейкам, граничащим по соответствующим ребрам сепаратрисам. При этом, если какая-либо седловая сепаратриса лежит во внутренности замыкания некоторой ячейки, то этой ячейке и этой сепаратрисе соответствует вершина графа с петлей. То есть каждая вершина имеет валентность 4, если считать петлю за два условных ребра. Набор этих четырех ребер, включая условные, разбивается на пары, в каждую из которых входит одно ребро, соответствующее устойчивой сепаратрисе, и одно ребро, соответствующее неустойчивой сепаратрисе, примыкающие друг к другу на границе соответствующей вершине ячейки. Такие пары обозначаются дугой, пересекающей оба ребра пары (рис. 11). Рис. 11. Поток ft из G на поверхности S и его граф Вонга ΓWft Fig. 11. The flow ft from G onto a surface S and its Wong graph ΓWft Графы называются изоморфными, если существует изоморфизм между , сохраняющий парность ребер. Предложение 3.5 (см. [19]). Градиентно-подобные потоки на ориентируемой поверхности S топологически эквивалентны тогда и только тогда, когда их графы Вонга изоморфны. Теорема 3.3 (см. [11, теорема 3]). Пусть-градиентно-подобные потоки на ориентируемой поверхности S рода -их n-вершинные графы Вонга. Тогда изоморфизм графов проверяется за время[2] O(nO(g)), если, и за время O(n), если g = 0. Доказательство. По графу ΓWft построим простой граф Γ˘ft следующим образом. Для этого применим 1-подразбиение к каждой петле; новая вершина соединена двумя ребрами с изначальной вершиной петли. Разбив таким образом петлю на два ребра, отнесем каждое из них к своей паре. Затем применим 1∗-подразбиение к каждому ребру и соединим ребрами добавленные этой операцией вершины, находящиеся на исходных ребрах, принадлежащих некоторой паре. Таким образом получим граф (см. рис. 12). Рис. 12. Граф ΓWft и построенный по нему простой граф Γ˘ft Fig. 12. The graph ΓWft and the simple graph Γ˘ft constructed from it Заметим, что граф ΓWft единственным образом восстанавливается по графу Γ˘ft. Действительно, все вершины графа - это все вершины валентности 4 графа Γ˘ft. Петлям графа взаимно однозначно соответствуют простые циклы, содержащие вершину валентности 2 графа Γ˘ft. Наконец, ребра, соединяющие вершины, инцидентные вершине валентности 1 на графе Γ˘ft, лежат на парных ребрах графа ΓWft . Таким образом, графы изоморфны тогда и только тогда, когда графы изоморфны. Поскольку вершины графа ΓWft соответствуют ячейкам, а ребра - седловым сепаратрисам, можно изобразить этот граф, просто расположив вершины внутри ячеек потока ft, а ребра - соединив соответствующие вершины дугами, пересекающими соответствующие сепаратрисы. Поэтому граф ΓWft вкладывается в несущую поверхность потока ft. В пары мы объединяем ребра, соответствующие соседствующим в границе сепаратрисам, поэтому дуги, символизирующие принадлежность ребер к паре, также вкладывается в поверхность. При построении графа Γ˘ft добавленные ребра либо представляют из себя именно эти дуги, либо ребра, не создающие новых замкнутых контуров, поэтому эти новые ребра не влияют на вложимость графа в поверхность S. Построение графов по выполняется за линейное время от числа n. Тогда утверждение теоремы непосредственно следует из предложений 3.1, 3.2. 3.5. Круговая схема Флейтас. Градиентно-подобный поток ft: S → S называется полярным, если в его неблуждающем множестве содержится ровно один источник и ровно один сток. Граф Флейтас ΓFft для такого потока ft строится следующим образом. Выберем вокруг источника (единственного, в силу полярности потоков) окружность S, трансверсальную траекториям потока ft в бассейне источника. Обозначим через D диск, который эта окружность ограничивает в бассейне источника. Присвоим всем пересечениям окружности S с седловыми сепаратрисами метки так, чтобы пересечения с сепаратрисами одного и того же седла были с одинаковыми метками. Каждой паре точек с одинаковыми метками присвоим спин, т. е. знак +(-), если объединение диска D с трубчатой окрестностью устойчивого многообразия седловой точки, пересекающего окружность S по данной паре точек, является кольцом (пленкой Мебиуса) (см. рис. 13, 14). Два инварианта Флейтас полярных потоков, соответственно, называются изоморфными, если существует изоморфизм, переводящий окружности инварианта ΓFft в окружности инварианта и сохраняющий метки и спины. Предложение 3.6 (см. [7]). Два полярных потока ft и ft топологически эквивалентны тогда и только тогда, когда их инварианты Флейтас изоморфны. Рис. 13. Полярный поток ft и его инвариант Флейтас ΓFft Fig. 13. Polar flow ft and its Fleitas invariant Рис. 14. a) Инвариант Флейтас потока на рис. 13; b) Полярный поток в окрестности источника на неориентируемой поверхности и его инвариант Флейтас Fig. 14. a) Fleitas invariant of the flow in Fig. 13; b) Polar flow in the neighborhood of a source on a nonorientable surface and its Fleitas invariant Теорема 3.4 (см. [11, теорема 5]). Пусть-полярные потоки на поверхности S рода -их n-вершинные графы Флейтас. Тогда изоморфизм графов проверяется за время O(nO(g)), если g > 0, и за время O(n), если g = 0. Доказательство. Для инварианта Флейтас построим простой граф Γˆft следующим образом. Метки инварианта будут вершинами графа, а дуги окружности - ребрами. Соединим одинаковые метки ребрами. Применим 1-подразбиение к каждому ребру, соединяющему одинаковые метки со спином +, и 1∗-подразбиение к каждому ребру, соединяющему метки со спином - (см. рис. 15). Заметим, что графы единственным образом строятся по графам . Покажем, Рис. 15. Граф ΓFft и простой граф Γˆft Fig. 15. Graph ΓFft and simple graph Γˆft что обратное тоже верно. Изначальные метки инварианта ΓFft - это вершины графа Γˆft валентности 3, не имеющие соседних вершин валентности 1. Вершины графа Γˆft соответствуют одинаковым меткам, если их соединяет путь длины 2, не содержащий других вершин, соответствующих меткам. Если вершина в середине такого пути имеет валентность 2, то путь соединяет вершины, соответствующие меткам со спином +. Если вершина в середине пути имеет валентность 3 и соседнюю вершину валентности 1, то путь соединяет вершины, соответствующие меткам со спином -. Таким образом, графы изоморфны тогда и только тогда, когда изоморфны. Более того, графы строятся за линейное время от числа n и вложимы в поверхность S, на которой заданы. Следовательно, из предложений 3.1, 3.2 вытекает утверждение теоремы. 3.6. Трехцветный граф Ошемкова-Шарко. Пусть ft - градиентно-подобный поток, заданный на поверхности S. Назовем ячейкой J потока ft компоненту связности множества . Обозначим через Jft множество всех ячеек потока ft и выбеf f f f рем по одной траектории θJ (t-кривой) в каждой ячейке J ∈ Jft. Положим. Назовем u-кривыми неустойчивые седловые сепаратрисы и s-кривыми- устойчивые седловые сепаратрисы. Из работы [15] следует, что каждая компонента связности Δ множества S¯ является криволинейным треугольником, ограниченным одной s-, одной u- и одной t-кривой, вследствие чего мы будем называть Δ треугольной областью. Границу каждой треугольной области будем считать ориентированной соответственно движению по t-кривой от источника к стоку. Обозначим через Δft множество всех треугольных областей потока ft. Трехцветный граф ΓOSft Ошемкова-Шарко из работы [5], соответствующий градиентноподобному потоку ft, строится следующим образом (см. рис. 16): 1) вершины графа ΓOSft взаимно однозначно соответствуют треугольным областям потока; 2) две вершины графа инцидентны ребру цвета s, t, u, если соответствующие этим вершинам многоугольные области имеют общую s-, t-, u-кривую, а между этим ребром и s, t, u-кривой устанавливается взаимно однозначное соответствие. Рис. 16. Фазовый портрет некоторого градиентно-подобного потока и его трехцветный граф Fig. 16. Phase portrait of some gradient-like flow and its three-color graph Два трехцветных графа называются изоморфными, если существует изоморфизм графов, сохраняющий инцидентность и цветность. В силу конструкции, трехцветные графы, полученные по различным разбиениям на треугольные области (в зависимости от выбора t-кривых), изоморфны. Предложение 3.7 (см. [5, теорема 1.10]). Два градиентно-подобных потокатопологически эквивалентны тогда и только тогда, когда их графы изоморфны. Следующая теорема полностью повторяет теорему из работы [11], но мы приводим ее доказательство для полноты изложения. Теорема 3.5 (см. [11, теорема 4]). Пусть-градиентно-подобные потоки, заданные на поверхности рода g, -их n-вершинные трехцветные графы. Тогда изоморфизм графов проверяется за время O(nO(g)), если, и за время O(n), если g = 0. Доказательство. В работе [5] авторы предлагают алгоритм различения изоморфизма. Однако он не полиномиальный, и ниже мы предлагаем полиномиальный алгоритм различения. Построим граф Γˇft 1-подразбиением s-ребер, 2-подразбиением t-ребер и 3-подразбиением uребер графа ΓOSft (см. рис. 17). Заметим, что графы единственным образом строятся по графам . Покажем, что обратное тоже истинно. Вершины валентности 3 графа Γˇft - это в точности вершины валентности 3 графа ΓOSft . Цвет каждого ребра графа ΓOSft определяется длиной пути между конечными вершинами ребра графа Γˇft. Таким образом, графы изоморфны тогда и только тогда, когда изоморфны. Более того, графы строятся за линейное время от n и вложимы в поверхность S. Следовательно, по предложениям 3.1, 3.2, доказана настоящая теорема. Благодарности. Работа выполнена при финансовой поддержке Российского научного фонда (проект № 17-11-01041), за исключением теорем 3.1 и 3.2, которые выполнены при поддержке Лаборатории динамических систем и приложений НИУ ВШЭ (грант Министерства науки и высшего образования РФ, соглашение № 075-15-2019-1931). Рис. 17. Трехцветный граф ΓOSft и его простой граф Γˇft Fig. 17. The three-color graph ΓOSft and its simple graph Γˇft

Об авторах

В. Е. Круглов

НИУ ВШЭ

Автор, ответственный за переписку.
Email: kruglovslava21@mail.ru
Нижний Новгород, Россия

О. В. Починка

НИУ ВШЭ

Email: olga-pochinka@yandex.ru
Нижний Новгород, Россия

Список литературы