Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[32]

Ографов, нужно считать определенными и для их лоскутов. Например, можно говорить об итеранте лоскута и т.пр.

Заметим, что Ограф, взятый целиком, можно считать его лоскутом

(D,E(D), V, (Po},F).

Линии, маршруты в некотором смысле простейшего вида, служат частями выражения E(D). Кроме того, линии в графе, который является подграфом рассматриваемого О графа и допускает в себе выделение подчиненных графов, предо ставляют алгоритму выделения "отправные точки".

Следующее определение вводит характеристику маршрута, аналогичную поня -тию заряда маршрута магазинного автомата.

Пусть Т - маршрут. Результат ц(Т) примененения к нему Оотображения назовем зарядом маршрута Т.

Если /х(Т) = Л, то будем называть маршрут Т нейтральным.

Ясно, что заряд является цепочкой из Right(V)*Left(V)* и, если не пуст, со -стоит из дуг, не имеющих пары в данном маршруте.

Пусть Т - маршрут, Closure(T) = (TiТТ2\Т1ТТ2 - нейтральный маршрут; результат удаления из Т1 или Т2 некоторого непустого участка либо не является маршрутом, либо не нейтрален }. Пусть p = ((п1,п2) е V\3T е Closure(T) (п1 и п2 образуют гнездо в Т)}. Тогда будем говорить, что Т есть маршрут в p. Будем использовать для p обозначение V(Т).

Пусть P и Q - вершины, w - заряд, p С V. Обозначим через

Computations(p, P, Q, vj)

множество всех маршрутов в p с парой концов (P, Q) и зарядом w. Если Т - маршрут с парой концов (P, Q) и зарядом w, то будем считать запись "Computations)" синонимом данного обозначения.

Таким же образом будем сокращать и некоторые далее определяемые обозна чения, например, Lines (p, P,Q,w).

Элемент множества Lines(p, P,Q,w) = (Т е Computations(p, P,Q,w)\reduction(T) = Т} будем называть (p,P,Q,w)-линией (или, просто, линией, если p,P,Q,w либо подразумеваются, либо не существенны в данный момент).

Как видим, линия не содержит вставок, другими словами, не является произ водным маршрутом.

3.2.2. Итеранты и их сцепленность

Определим итеранты - связные компоненты О графа, которые наряду с ли ниями играют ключевую роль в рассматриваемом построении. Для этого введем несколько вспомогательных понятий.

Далее нетривиальная, т.е. имеющая дуги, сильно связная компонента называ ется кратко сильно связной компонентой.

Пусть D - некоторый Ограф. Дадим рекурсивное определение понятия линейная (в D) дуга:


1)дуга, которая не является дугой никакой сильно связной компоненты Эграфа D, называется линейной в нем;

2)пусть дуга п такова, что каждая парная ей дуга удовлетворяет пункту 1 данного определения; тогда п называется линейной в D;

3)пусть дуга п линейна в графе descendant(D), получаемом из D удалением его дуг, удовлетворяющих пунктам 1,2 данного определения; тогда п считается линейной ив D.

Пример 6. В Эграфе D

-о-о-о-о-о-о-

о -15 о

с Эмножеством

{(1,10), (2, 3), (4, 5), (4,11), (12, 5), (7, 8), (6, 9), (13,14), (15,16)}

дуги 1,2,7,8 и 10 линейны согласно первому пункту последнего определения, дуга 3 удовлетворяет второму пункту. Линейность дуг 4,5,11 и 12 обнаруживается в результате удаления дуг 1,2,3,7,8,10. В графе

descendant (descendant (D))

первому пункту определения линейной дуги удовлетворяет дуга 13, второму - 14, третьему - 15 и 16.

Из определения видно, что линейная дуга Эграфа участвует в линии, его собственной или некоторого "потомка", чем и объясняется выбор термина. Сле -дующая лемма означает, что линейная дуга никогда не участвует в нейтральных циклах и циклах, образующих гнезда.

Лемма 18. Если дуга входит в нейтральный цикл или в какойнибудь из двух парных друг другу циклов, то она не является линейной.

Доказательство. Пусть п - линейная дуга в Эграфе D. Тогда существуют целое k > 0 и последовательность графов D0,...,Dk, такие, что D0 = D, Djt = descendant(Di-1) для 0 < i < k и дуга п удовлетворяет в Dk пункту 1 или 2 определения линейной дуги. Докажем лемму индукцией по k.

Заметим предварительно, что если некоторая дуга п1 удовлетворяет в некотором графе пунктам 1,2 определения линейной дуги, то она сама или любая парная ей дуга п2 не принадлежит никакой сильно связной компоненте этого графа. Согласно определениям гнезда и нейтрального цикла каждая дуга одного из двух парных циклов имеет парную в нем самом или в парном ему цикле, а каждая дуга


нейтрального цикла имеет парную в нем самом. Но это означает, что элемент D-множества, образованный дугами п1 и п2, не может участвовать в нейтральных и парных циклах рассматриваемого графа.

Из установленного следует, что маршруты графа Di, 0 < i < k, не содержат нейтральных или парных циклов, в которых участвовали бы дуги, удовлетворяющие в нем пунктам 1,2 определения линейной дуги. Таким образом, утверждение справедливо при k = 0.

Пусть k > 0. Допустим, что дуги графа Dk, удовлетворяющие в нем пунктам 1,2 определения линейной дуги, входят в нейтральные или парные циклы объемлющего графа. Тогда согласно установленному выше в этих циклах обязаны участвовать дуги, отсутствующие в Dk. Но участие этих дуг в нейтральных или парных циклах противоречит предположению индукции □

Пусть сильно связная компонента G Dграфа D имеет дуги, которые не являются линейными в D. Пусть ее подграф C определяется множеством всех таких дуг и их вершинами. Тогда назовем C итерантом.

Заметим, что сильно связная компонента может содержать как линейные дуги, так и дуги, не являющиеся линейными. Так, в D графе

-о-о-о-о-о-о-

с D множеством

{(1,4), (2, 3), (5,10), (6, 9), (7, 8)}

дуги 3,4, 5 линейны, а дуга 6 образует итерант. Второй итерант данного Dграфа состоит из дуги 9.

Может случиться, что все дуги сильно связной компоненты линейны, как в сле -дующем примере. Таким образом, сильно связной компоненте D графа отвечает не больше одного итеранта.

Пример 7. Следующий Dграф с Dмножеством {(1,2)} не имеет итерантов, хотя у него есть нетривиальная сильно связная компонента.

- о -2 о -

Лемма 19. Итерант сильно связен.

Доказательство. Противное означало бы, что среди дуг итеранта есть линейные в D дуги, вопреки определению итеранта □

Следующий факт подготавливает, по существу, осознание возможности важной взаимозависимости различных итерантов.

Лемма 20. Любая дуга итеранта парна некоторой дуге некоторого итеранта.

Доказательство. Предположим, что некоторая дуга п некоторого итеранта об-разует пары только с дугами, не входящими в итеранты, т.е. линейными. Но тогда и дуга п линейна, вопреки определению итеранта □



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49]