|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[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. Любая дуга итеранта парна некоторой дуге некоторого итеранта. Доказательство. Предположим, что некоторая дуга п некоторого итеранта об-разует пары только с дугами, не входящими в итеранты, т.е. линейными. Но тогда и дуга п линейна, вопреки определению итеранта □ |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||