Атомы с более чем одной уникурсальной компонентой (847336), страница 2
Текст из файла (страница 2)
Цикл, являющийся объединением l1 и l2 , будемназывать двуугольником для пары (u, v).Для каждой пары различных смешанных вершин существует 4 двуугольника.Обозначим M множество циклов в Γ, образованных полуокружностями для каждойвершины S1 (т.е. циклами в Γ, все ребра которых принадлежат S1 ), полуокружностямидля каждой вершины S2 и двуугольниками для каждой пары смешанных вершин.Если некоторой вершине X цикла (пути) γ в Γ идцидентно 2 полуребра и они неявляются противоположными, скажем, что цикл (путь) γ поворачивает в X.Теорема 5.
H1 (Γ, Z2 ) порождается множеством M .Доказательство. Рассмотрим произвольный цикл γ на графе Γ (над Z2 ) и связнуюкомпоненту τ в γ. Выберем произвольный порядок обхода цикла τ и разделим τ напути l1 , ..., l2k таким образом, чтобы все ребра в l2i−1 принадлежали S1 , все ребра в l2iпринадлежали S2 , 1 6 i 6 k, и конец пути lj совпадал с началом пути lj+1 , 1 6 j 6 2k(считаем, что l2k+1 = l1 ). В частном случае, когда цикл τ содержит только ребра из S1или S2 , получим один путь.Обозначим начало и конец пути l2i через ei и fi соответственно (возможно, ei совпадает с fi ).
Вершина ei принадлежит также пути l2i−1 , а вершина fi – пути l2i+1 для01 6 i 6 k − 1 и пути l1 для i = k. Значит, существует путь l2iв S1 , начинающийся вei , заканчивающийся в fi и в каждой не смешанной вершине на S1 проходящий черезпротивоположные ребра (если ei 6= fi , таких путей 2, тогда выберем любой из них).Далее, в каждой смешанной вершине путь l2i проходит через противоположные ребра Γ; в некоторых вершинах из S2 , возможно, поворачивает. Для каждой такой вершиныX (пусть ей инцидентны полуребра a, b, c и d, ребро a противоположно ребру c, реброb противоположно ребру d, и l2i проходит через полуребра a и b), добавим в l2i полуокружность для X, проходящую через c и d.
Заметим, что каждый раз мы прибавлялик l2i элемент из M .Выполнив эту процедуру во всем l2i , получим путь ¯l2i в S2 с началом в вершине ei иконцом в вершине fi , в каждой внутренней вершине проходящий через противоположные полуребра.0Отметим, что цикл ¯l2i l2iпринадлежит M .0Рассмотрим путь l2i−1 l2i. Его начало и конец совпадают с началом и концом соот0ветственно в l2i−1 l2i , кроме того, все ребра l2i−1 l2iпринадлежат S1 .0Проделав аналогичные замены для всех 1 6 i 6 k, получим цикл s = l1 l10 ...l2k l2k, всеребра которого принадлежат S1 .В каждой смешанной вершине цикл s проходит через противоположные ребра Γ;в некоторых вершинах из S1 , возможно, поворачивает.
Добавлением к s элементов изM можно получить цикл s0 в S1 , каждой вершине проходящий через пары противоположных ребер (аналогично построению цикла ¯l2i ). Цикл s0 также является суммойэлементов из M .Рассуждения для остальных связных компонент в γ аналогичны.Теорема 6. Пусть в атоме (P, Γ) уникурсальные компоненты S1 и S2 пересекаютсяв нечетном количестве точек. Тогда (P, Γ) неориентируем.4Доказательство. Предположим, что (P, Γ) ориентируем. Рассмотрим произвольнуювершину X компоненты S1 . Т.к.
на S1 нечетное число смешанных точек, то на однойиз полуокружностей s для X в S1 их количество также нечетно.Из вложимости графа Γ в P следует, что подграф Γ0 , вершинами которого являются вершины компоненты S1 , а ребрами — дуги в S1 между соседними вершинами,также вложим в P . Значит, согласно Теореме 2, вершина X в Γ0 четная, т.е. на каждойполуокружности для X в Γ0 количество точек четно.Вершины компоненты S1 , лежащие на s – это в точности вершины одной из полуокружностей для X в Γ0 .Таким образом, на полуокружности s нечетное число вершин графа Γ. Несложнопроверить, что в вершине X нарушается условие источник-сток.Как мы видели выше, для атомов, остов которых состоит из одной уникурсальнойкомпоненты, можно определить четность вершин.
Оказывается, в случае двух уникурсальных компонент также можно ввести понятие четности.Пусть S1 и S2 пересекаются в четном числе точек. Тогда следующие два определениякорректны:Определение 9. Для v – вершины в S1 (соответственно, в S2 ) определим четностькак четность количества вершин в полуокружности для v в S1 (соответственно, в S2 ).Определение 10. Скажем, что две смешанные вершины u и v остова атома с двумя уникурсальными компонентами имеют одинаковую относительную четность, есликоличество вершин в двуугольнике (u, v) четно.Докажем главный результат этой работы – теоремы, дающие критерии ориентируемости атомов, остов которых представляет собой граф с двумя, тремя и четырьмяуникурсальными компонентами.Теорема 7.
Атом с двумя уникурсальными компонентами ориентируем ⇔ выполнены следующие условия:1. на каждой компоненте S1 и S2 все вершины четные,2. каждая пара смешанных вершин имеет одинаковую относительную четность.Доказательство. Согласно теореме 5, каждый цикл l в Γ является суммой циклов изM . Каждый цикл из M проходит через противоположные ребра в четном количествевершин. Значит, l также проходит через противоположные ребра в четном количествевершин. Это условие в силу Теоремы 4 равносильно ориентируемости l. Т.к.
l изначально предполагался произвольным, то из Теоремы 3 получаем ориентируемость (P, Γ).Рассмотрим теперь атомы с тремя уникурсальными компонентами S1 , S2 , S3 . Аналогично случаю двух уникурсальных компонент можно разделить вершины остова навершины компоненты Si (i = 1, 2, 3) и смешанные вершины. Множество смешанныхвершин, для которых пары противоположных полуребер принадлежат компонентам S1и S2 , обозначим V12 .
Аналогично определим множества V23 и V13 .Для каждой тройки смешанных вершин v12 , v23 и v13 (vij ∈ Vij ) можно рассмотретьпути l1 в S1 , l2 в S2 и l3 в S3 , соединяющие пары точек и в каждой внутренней вершинепроходящие через противоположные полуребра остова. Цикл, являющийся объединением l1 , l2 и l3 , будем называть треугольником для тройки (v12 , v23 , v13 ).Определение 11. Скажем, что тройка смешанных вершин v12 , v23 и v13 имеет одинаковую относительную четность, если количество вершин в треугольнике(v12 , v23 , v13 ) четно.Теорема 8. Атом с тремя попарно пересекающимися уникурсальными компонентами ориентируем ⇔ выполнены следующие условия:51.
на каждой компоненте S1 , S2 и S3 все вершины четные,2. каждая пара смешанных вершин имеет одинаковую относительную четность,3. каждая тройка смешанных вершин (v12 , v23 , v13 ) имеет одинаковую относительнуючетность.Доказательство. Доказательство того, что H1 (Γ, Z2 ) порождается множеством циклов,состоящим из полуокружностей для каждой вершины Si , двуугольников для каждойпары смешанных вершин и всевозможных треугольников, проводится аналогично доказательству Теоремы 5.Далее, четность переходов через противоположные в вершине полуребра для произвольного цикла l в Γ доказывается так же, как в Теореме 7.Можно показать, что третье условие равносильно существованию для каждой пары вершин (v12 , v23 ) одной вершины v13 такой, что тройка вершин (v12 , v23 , v13 ) имеетодинаковую относительную четность (vij ∈ Vij ).Кроме того, третье условие не следует из первых двух, см.
рис. 2.Несложно показать, что случай, когда в атоме с четырьмя уникурсальными компонентами не все компоненты попарно пересекаются, сводится к уже рассмотренным.Теорема 9. Атом с четырьмя попарно пересекающимися уникурсальными компонентами ориентируем ⇔ выполнены следующие условия:1. на каждой компоненте S1 , S2 , S3 и S4 все вершины четные,2. каждая пара смешанных вершин имеет одинаковую относительную четность,3. все тройки вершин (v12 , v23 , v13 ) (v13 , v34 , v14 ) и (v23 , v24 , v34 ) имеют одинаковуюотносительную четность.Доказательство.
Необходимость условий теоремы очевидна.Докажем достаточность. Обозначим через M множество циклов, указанных в условиях 1–3.Покажем, что при выполнении условий 1–3 каждая тройка вершин (v12 , v24 , v14 )(vij ∈ Vij ) также имеет одинаковую относительную четность (то, что относительнаячетность корректно определена, следует из условий 1-2).Рассмотрим произвольный треугольник для (v12 , v24 , v14 ), состоящий из путей k1 , k2и k4 , kj ∈ Sj (здесь и далее все рассматриваемые пути в каждой внутренней вершинепроходят через противоположные полуребра остова).Так как все уникурсальные компоненты в Γ попарно пересекаются, найдется вершина M13 , в которой пары противоположных полуребер принадлежат компонентам S1и S3 . Рассмотрим путь m1 в S1 , соединяющий вершины v12 и M13 .
Аналогично выберем вершины M23 , L23 , L24 , N24 , N13 и пути m2 , m3 , l2 , l3 , l4 , n1 , n3 , n4 , p1 , p2 , p4 (см. рис.3; индекс у каждого пути совпадает с номером компоненты).Тройки вершин (v12 , L13 , L23 ), (v24 , M23 , M34 ) и (v14 , N13 , N34 ) по условию имеютодинаковую относительную четность, значит, количество вершин в каждом из цикловm1 m2 m3 , l2 l3 l4 и n1 n3 n4 четно.Рассмотрим цикл s = k1 n1 p1 m1 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
