Elektronika_i_skhemotekhnika

Приведѐм критерии Гурвица2 для систем, описываемых уравнениями до 5-го порядка:

для n 5

4Г

z z

2

z z

z z

4

z

z z z

4

z z 2

0,

1

0 3

3

2 5

1

0 5

'

3.22а

2Г

z z

2

z

z

0,

z

z

4

z

z 0,

z 0, i 1,5 ;

1

0 3

2Г

3

2 5

i

для n 4

3Г z3 z1z2 z0 z3 z12 z4 0,

3.22б

zi 0, i 0,4 ;

для n 3

3.22в

2Г z1z2 z0 z3 0, zi 0,

i 0,3 ;

для n 0,2

z0 0, z1 0,

z2 0 .

3.22г

При синтезе функции D(Z,s) критерии (3.22) обязательно выполняются. Однако при физической реализации эти коэффициенты zi состоят из сумм произведений параметров элементов системы и образуют соответствующие коэффициенты ai, значение которых всегда будут отличаться от zi , так как реальные элементы всегда имеют допуски на погрешность изготовления соответствующего параметра. Следовательно, с ростом порядка n увеличивается не только число перемножаемых коэффициентов, но и число перемножаемых параметров элементов входящих в них, а поэтому отклонение zi от расчѐтного значения может привести к изменению знака неравенств (3.22а) – (3.22в) и возбуждению системы.

На втором шаге в рамках критерия Гурвица выводятся критериибезусловной устойчивости (см.) []. Идея получения критериев достаточно проста: необходимо синтезировать структуру системы такой, чтобы для неѐ неравенства (3.22) выполнялись при любых значениях параметров элементов, формирующих коэффициенты ai. Это можно выполнить при единственном условии: среди всех положительных слагаемых (3.22) (например

2 В литературе обычно критерии Гурвица приводятся в эквивалентной, с точки зрения математики, форме: коэффициенты при старшей степени оператора s имеют индекс ноль, а не n, как это принято в настоящей работе. Такое обозначение было принято в связи с физической реализацией коэффициентов snan, гдеnуказывает на минимальное число реактивных элементов, формирующих коэффициент an при однородной записи числителя и знаменателя функции K(s).

для n=3: a2a1), должны содержаться слагаемые тождественно равные отрицательным (a0a3) и ещѐ должно остаться какое-то число положительных

слагаемых. Для синтезируемой функции																					K s B s			A s из условий (3.22)
получаем
	для			ai , i 0, n
			ai 0																							3.23a
	для n 3
			a a		A3	A3			,	A3	0,		A3 a a ;													3.23б
			1	2	1	2				1				2			0		3
	для n 4
			a a a A4 A4							A4 ,			A4 0,					A4		a a2			, A4 a a2		;	3.23в
			1	2	3	1			2		3		1						2		0	3	3	4 1
	для n 5
a a		2	A	3 A3 ,		A 3 0, A 3					a	0	a	3	; a	3	a	4	A 5		A5		, A5 0,
1			1		2	1				2										1		2	1
A 52 a 2a 5;					A31A51 A53 A54 ,						A 54 a1a 4 a 0a 5 2 ,											A 53 0;				3.23г
	где A13, A14 , A15 -- остатки многочленов a1a2, a1a2a3																								и a3a4 ,		полученные
после выделения из них соответственно многочленов																								A3, A4		, A4	и A5 ;	A5
																								2	2	3	2	3
многочлен оставшийся от											A15 A13				после выделения из него многочлена A45 .

Критерий структурной устойчивости для систем с n 2 согласно (3.22а) будет выполнен, если все коэффициенты просто положительны. Для систем, описываемых уравнениями с n>5, можно воспользоваться рекуррентной формулой, приведѐнной в справочнике [31], для установления тождеств, подобных (3.23).

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

усиления Ku 104 106 . Если в системе содержится два или большее число ОУ, охваченных контуром отрицательной обратной связи, то небольшое число

возможных структур оказывается просто устойчивыми, а ещѐ меньшее число структур будет безусловно устойчивыми.

Как уже отмечалось, структурная устойчивость системы частично реализуется на этапе принципов построения, если отказаться от применения обратных связей, охватывающей несколько компонент системы и, не применяя еѐ внутри компонента. Однако это не всегда оказывается возможным практически и оправданным с экономической точки зрения.

Тождества и неравенства (3.23) определяют способы построения систем с контурами обратной связи, обеспечивающими высокое качество систем за счѐт особенностей их структуры, описываемых соотношениями (3.23).

Таким образом, критерии (3.23) должны использоваться в качестве свѐртки векторного критерия качества Opi при формировании функции выбора. Причѐм, критерии безусловной устойчивости должны занимать в функции выбора первые места, чтобы при лексикографическом сравнении3 разных структур можно было отсеять на самых ранних стадиях проектирования структуры, не удовлетворяющие ТЭТ.

По векторному критерию качества i-го этапа

Opi Opi1, ,Opi , ,Opi

сравнивают λ синтезированных структур. Считают, что структура Wk не хуже структуры Wt (Wk >: Wt ) , если выполнено

ih ( k )		(	t )
Op W Ј Op	ih	W ; h = 1,l			,

и структуры эквивалентны (Wk : Wt ) в смысле критерия Opi , если

Opih (Wk )= Opih (Wt ).

Частные критерии не все равноценны, поэтому ранжируют их по важности, объединив равноценные в комплексы. В этом случае можно добиваться приращения более важного критерия за счѐт потерь по всем остальным менее важным критериям. Отыскание в указанном смысле эффективных структур можно осуществить, решив лексикографическую задачу оптимизации [32]

3Сравнение двух лексикографически упорядоченных векторов осуществляют по принципу первого различия (как слова упорядочены в словаре). Например,

x1, , xn , y1, , yn , , если для некоторого k выполняется xk yk и xi yi для всех i k [40].

W ОWg

l exinf F	Op		(W )
	Opi (	i	)
W ОWg			(3.24)

где Wγ – множество всех возможных структур.

В соответствии с лексикографическим отношением предпочтения

структур W	lex W ,		которое будет справедливо,						если выполняется одно из λ
k >		t
условий
	i1(	k )		i1(	t )		i1( k )		i1( t )
1) Op W < Op W ; 2 ) Op W = Op W										,
i2	( k )		i2	( t )
Op	W	< Op		W	; K ;						(3.25)
	il (	k )		il	( t )			il ( k )		il ( t )
l ) Op W = Op W						, k = 1,l - 1; Op W < Op W					.

Когда лексикографически эффективные структуры существуют, то задачу (3.24) решают так: найти

						(3.26)
lex min F	Op		(W ) , i = 1,6 .
	Opi (	i	)

Итак, наиболее важным критериям высокого качества системы придают наименьшие номера η критериев Opiη и все структуры им не удовлетворяющие из дальнейшей процедуры синтеза исключаются. Однако в базе знаний(см.) отвергнутые структуры остаются для решения других задач с иными заданиями, а также для того, чтобы не повторять при подобных технических условиях все процедуры синтеза заново.

3.6.Основные положения теории графов Знаменитую задачу семи Кѐнигсбергских мостов, соединявших два

острова на реке Преголь с сушей и между собой, Эйлер решилв 1736 г. В ней было необходимо найти маршрут, который бы прошѐл по четырѐм частям суши, ровно один раз по каждому мосту. Причѐм, начало и конец маршрута должны находится на одном и том же острове. Для доказательства невозможности такого маршрута Эйлером и был построен граф4. Это решение

иположило начало теории графов.

В1847 г. Кирхгоф разработал теорию деревьев на графах для составления независимой системы уравнений при расчѐте электрических цепей. Именно на

4На самом деле это был мультиграф, а не граф.

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

3.6.1. Типы графов и их элементы

Для интуитивного уяснения понятия графа рассмотрим рис. 3.1,а , на котором изображена схема электрической цепи, а на рис. 3.1, б представлена диаграмма, содержащая столько кружочков, сколько узлов в электрической схеме, и столько линий (со стрелками или без), сколько элементов в цепи. Ясно, что рис. 3.1, б отражает некоторые свойства электрической схемы, а именно еѐ структурные свойства. Кружки v1, v2, v3, v4, v5 называют вершинами, линии –

ребрами, если на них нет стрелок, и дугами (ориентированным ребром), если на линии имеется стрелка. Дуга соединяет вершину v5 с вершиной v1, но не соединяет вершину v1 с v5 (и вообще не соединяет никакую другую пару вершин). Ребро, например h, в отличие от дуги соединяет вершины v4, v5 и v5,v4. Говорят, что вершине v4 инцидентны рѐбраg, d, e, h , а каждому из них инцидентна вершина v4 . Дуга выходит из вершина v5 и заходит в вершину v1.

Рассмотренный граф является смешанным, так как он содержит дуги и ребра. Если удалить дугу из графа, то получим граф, называемый обыкновенным, а если заменить дугу ребром, то образуется несколько параллельных (кратных) ребер и такой граф называют мультиграфом. Граф, содержащий только дуги, называют направленным или орграфом. При исследовании систем автоматического управления широко используют структурные схемы. Они фактически являются орграфами, у которых дуги имеют вес, равный передаточной функции звена, регулятора, объекта регулирования. Алгоритмы обработки информации также нагляднее описывать с помощью орграфов, так как с их помощью легко обнаруживаются контуры (циклы) положительной обратной связи.

Следует обратить внимание на то обстоятельство, что форма и длина рѐбер графа не имеют значения (см. рис.3.1, в), пересечение линий

рѐбер не образует вершину (рис.3.1, б), а является особенностью рисунка. При большом числе вершин для описания графа используется матрица (см. ниже), а не рисунок.

Теперь дадим формальное определение обыкновенного графа Г (для упрощения изложения в дальнейшем слово «обыкновенный» будем

Рис.3.1 на рис.в надо поменять номера вершин и ввести в рис.б) дугу

опускать)
различных			вершин из V,			называемых		ребрами.	Вершины
vi , vk V	смежны		(будем обозначать			это	так vi adj vk ),	если они соединены
ребром vi , vk ,			и	несмежны	, если не		соединены vi , vk .		У графа на
рис.3.1, б смежны вершины: v3 adj v4 , v3 adj v2 ; v1 adj v5								, v1 adj v2	, v1 adj v4 ; и
т.д.
Обычно в компьютер вводят граф,							задавая его ребра		vi adj vk и

формируя квадратную ( v v ) симметрическую матрицу смежностей с нулевой диагональю

D = (dij ), dij{0, 1}: dij 1 (i, j) .

Существуют два вида противоположных графа: безребѐрный граф с n

вершинами, не соединѐнных ни одним ребром ; и полный граф с тем же числом вершин, каждая из которых соединена ребром с каждой (число ребер в таком графе p v v 1 2). В графе рис.3.1, б вершины v4 и v2 удовлетворяют требованиям полного графа, а оставшиеся – нет. Если соединить рѐбрами вершины v1 и v3, v5 и v3 , то получится полный граф.

Иногда в графе образуется петля5, т.е. ребро, идущее из вершины vi в

вершину vi, а если ребро является дугой – то называют еѐ контуром (рис.3.2).

Рис. 3.2

рис.3.3

Маршрутом называют конечную последовательность рѐбер вида:

v0,v1 , v1,v2 , , vm 1,vm ,

где vi – i-я вершина графа, i 0,m .

Маршрут, у которого все вершины различны, называют путем, если он состоит из дуг, направленных в одну сторону. Если в маршруте нет дуг, то его называют простой цепью.

Замкнутая простая цепь (т.е. v0 = vm) называется циклом, а в орграфе –

контуром. Смешанный граф может содержать цикл и контур (рис.3.3). Понятия путь, контур, цикл, простая цепь широко используются при анализе систем и алгоритмов, которые отображают соответствующие графы.

3.6.2. Изоморфизм графов

При синтезе сложных структур (с числом вершин больше 10), возникает проблема синтеза не одинаковых структур. Даже одна и та же структура, начерченная разными людьми, не сразу распознаѐтся (сравните графы рис. 3.1, в и г), хотя эти рисунки содержат одинаковое число узлов и элементов, одинаковый состав элементов, но могут отличаться только связями. Следующее определение [34] позволяет однозначно определять одинаковые структуры.

Два графа Г и G изоморфны, если между множествами V и V их вершин существует взаимно однозначное соответствие , сохраняющее отношение

смежности вершин, т.е. такое, что для любых						vi , vk V и соответствующих им
вершин vi' , vk'	V '	vi vi' , vk vk'			имеет место
	'	'	'	,		(3.27)
vivk V vivk V

при этом само соответствие называется изоморфизмом графов.

5Граф с петлѐй называют уже мультиграфом.

Этот формализм означает, что две вершины соединены ребром в одном графе тогда и только тогда, когда в другом графе соответствующие вершины соединены друг с другом.

Пример изоморфных графов приведен на рис.3.1, в и г. При удалении дуги из графа рис.3.1, б получится граф, изоморфный предыдущим. Очевидно, что изоморфные графы должны иметь одинаковое число вершин и ребер. В противном случае они будут различными. Однако наличие равенств

	V			V '	v,					'	q не означает изоморфизма двух графов. Например, если

в графе рис.3.1, г отсоединить ребро r v5, v2 от вершины v2 и присоединить его к вершине v3, то изменѐнный граф с ребром r v5, v3 не будет изоморфен

исходному, так как исчезнет вершина, к которой в исходном графе подходило только два ребра. В этих двух графах отношение смежности вершин не сохраняется.

Инвариант графаG - это число, связанное с G, которое принимает одно и тоже значение на любом графе, изоморфном G. Число вершин v и число ребер q являются инвариантами графа. В связи с вышеизложенным, для вершин vi введѐм дополнительную характеристику.

Степенью deg , vi вершиныvi графа Γ=(V, ) называется число ребер

инцидентных этой вершине. В изоморфных графах и G степени

соответствующих	вершин	v v'		должны	быть	равными
		i	j
deg , vi deg G,v'j . В		предыдущем		примере степени всех		вершин

изменѐнного графа G такие: 4,3,3,3,3. Степени вершин исходного графа Г – 4,4,3,3,2 существенно отличаются от степеней вершин графа G, но сумма degvi в обоих графах одинакова и равна 2q, потому что число рѐбер у них одинаково, а каждое из них инцидентно двум вершинам. Это свойство графов было установлено Эйлером и является, по-видимому, первым утверждением теории графов:

2q deg vi ,
	i 1, v .			(3.28)
i

В произвольном графе, содержащем v вершин и q рѐбер - (v, q)-графе для любой вершины vi справедливо неравенство

0 deg vi v 1.

(3.29)

Граф, у которого имеются вершины со степенью deg vi = 0 , состоит из нескольких компонент не связанных между собой рѐбрами, причѐм эти компоненты называют подграфами, вершины с указанной степенью называют изолированными, а сам граф – несвязным. Вершины с deg vi =1 называют

концевой или висячей. Граф со всеми вершинами одинаковой степени называют однородным. Набор степеней вершин подобно числу вершин и числу рѐбер является инвариантом графа.

В теории чисел разбиение целого неотрицательного числа определяют

как набор целых положительных чисел, сумма которых равна	.	Разбиение
графа – это представление числа 2q в виде (3.28). Разбиение	degvi		числа
	i

на v частей называют графическим, если существует граф со степенями deg vi . Упорядочим степени вершин неразделимого6 графа в порядке невозрастания. Тогда каждое разбиение

i p1, p2, , pv ,

pi deg vi ; v 1 p1 p2 pv l , l 2 , (3.30)

выделяет класс изоморфных связных графов [33].

Нижеследующий алгоритм построения всех возможных разбиений iбыл разработан Д.А. Скойбедо совместно с автором и опубликован в приложении П-2 учебника [1]. У первого разбиения 1 первое число p1 выбирается наибольшим, позволяющим выполнить неравенства из (3.30), но не превышающим v-1, т.е.

p min v 1,2q l v 1			,	(3.31)
1

а все остальные числа pi выбираются из следующего соотношения:

	i 1		3.32
pi min v 1, 2q l v	i pk .
	k 1
Разбиение 2 образуется из 1 путѐм уменьшения числа p1 на единицу и
добавления еѐ к p2 , если	p1 1 p2 1; или к p3, если		p2 p3 1 и так далее.
Остальные разбиения i	получаются аналогично постепенным уменьшением

чисел p1, p2, p3,… на единицу. Признаком формирования всех разбиений служит

6 Неразделимый граф – граф связный, непустой, не содержащий вершин сочленения . Вершина сочленения графа – вершина, удаление которой увеличивает число компонент графа. Мост – ребро графа с такими же свойствами.

невозможность дальнейшего вычитания единицы из любого piи добавления еѐ к числу pjc бóльшим номером без нарушения условий (3.32). Последнее разбиение часто имеет равными все числа pi.

Пример1. Образуем все i для графов Г(6,8). Сначала находим

p1=v-1=6-1=5. Затем определяем

p2 min 6 1, 2 8 2 6 2 5 min 5,3 3.

Оставшиеся степени равны pi=2. Таким образом, в качестве первого разбиения имеем 1=(5, 3, 2, 2, 2, 2). Следующее разбиение построим, уменьшив p1, т.е. 2=(4, 4, 2, 2, 2, 2). Уменьшая на единицу последовательно p2 и p1 и добавляя еѐ соответственно к p3 и p4 , получим 3=(4, 3, 3, 2, 2, 2) и 4 =(3, 3, 3, 2, 2, 2).

Рассмотренный алгоритм построения всех разбиений можно иначе представить как нахождение всех решений системы:

v
pi 2q;	l pi pi 1;	p1 v -1;	i 2, v			(3.33)
i 1

Ниже приводится одна из возможных процедур решения этой системы:

j0 : 1; S : 2q lv; y : min[v 1, 2q l v 1 ]; перейти к M ;

				v
	L : p	: p	1; S : 1		( p	l); j : i 1;
	i1	i1	i i1 1		i	0	1
						j0 1
						pk ,	pi
	y min v 1, 2q l v j0								;
						k 1	i
M : j1 : max j : j j0 1 y l S ;
p j ; y;	j j0 , j0 1, , j1;
pi 1 : S j1 j0 1 y l l;
1
pi : l; j j1 2, , v;			z : qv 1.
Если i1	не существует, т.е. i v,			pi pv 1, то решения системы (3.33)
исчерпаны, в противном случае – перейти на метку L.
Проблема изоморфизма			графов в	определѐнной			степени усугубляется

произвольным обозначением	его вершин. Так как разбиение включает в себя
инварианты, определяемые	числом вершин и ребер, то произведѐм