Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

книги из ГПНТБ / Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов

.pdf

Скачиваний:

Добавлен:

20.10.2023

Размер:

8.54 Mб

Скачать

☆

<<< < Предыдущая 12 / 222 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 > Следующая >>>

Транспонированной по отношению к А назовем матрицу

			/	а\\	a,2i • • • ami			\
		„,	I	«12	а22 • • •ат2			\
				din	&2п	' ' '
получаемую из А заменой строк						столбцами.
Две матрицы равны в том и только							в том		случае, если	равны
их соответствующие		элементы. Очевидно,						что	размерности	тип
строк и столбцов равных матриц должны								совпадать.
Квадратная	матрица		называется			треугольной, если ее элемен
ты ац для всех	i>j	(или для			всех i<lj)		равны		нулю.
Матрица

является

треугольной.

Матрица

А называется симметрической,

если

А=А',

т. е.

ац = ан

при любых i, j .

Если А——А',

т. е. ац = —ац,

матрица А

называется

кососимметрической.

Из

определения

вытекает,

что

все

элементы главной

диагонали

кососимметрической

матрицы

равны

нулю.

Все

элементы так называемой нулевой матрицы,

обозначаемой

0 = ( 0 ) ,

равны нулю.

Определим теперь операции сложения матриц и умножения

матриц

на

скаляр. Пусть даны некоторый

скаляр а

произволь

ная

матрица

А. Их произведение аА определяется как

аА

Сумма

Л + В = С матриц А я В,

каждая

из

которых

содержит

строк

п столбцов, определяется

как

1.0

Операции умножения скаляра на матрицу								и сложения	мат
риц	обладают	следующими			свойствами:
а)	(А +В) + С=А		+ (В + С)		(ассоциативный			закон);
б)	А+В = В+А.		(коммутативный			закон);
в)	( а + р ) Л =	а Л + р Л ,		а{А-\-В)—аА-\-аВ			(дистрибутивный		за
кон) ;
г)	Л + 0 = Л .
Здесь матрицы А, В и				С имеют		размерности		т-п, а а и	р —

скаляры.

Произведение двух матриц А и В определяется только при ус

ловии, что число столбцов матрицы А равно		числу строк матрицы
В. При этом условии элементы произведения		АВ = С определяют
ся следующим	образом.
Элемент г'-й строки и /-го столбца матрицы С равен сумме про
изведений элементов г'-й строки матрицы А		на соответствующие
элементы у'-го столбца матрицы В.
Например,	\	)

где сц = ац	Ь^ + щ2 b2j + ai3		b3j.			матрицу В
Произведением		матрицы	А размерности т-п на
размерности	n-q	является матрица		размерности	m-q.	Произведе
ние матриц некоммутативно, т. е.				АВфВА.
Произведение		матриц обладает		следующими	свойствами:

a)(АВ)С=А(ВС) (ассоциативный закон);

б)	(А + В)С=АС + ВС, С(А + В) = СА + СВ	(дистрибутивный
закон);
b)	а(АВ) = (аА)В=А(аВ);	*• :
г)	АЕ=ЕА=А;

здесь матрицы А, В, С		и Е	имеют соответствующие		размерности и
а — скаляр.	Отметим,	что	(АВ)' —	В/-А'.
Матрица	В называется		обратной	по отношению	к квадратной
матрице А,	если АВ = Е. Матрица, обратная матрице А, обознача

ется через А-1.	Для каждой неособенной		матрицы А	существует
единственная	матрица А~1,	такая, что
§ 1. 3. ОБЩЕЕ ПОНЯТИЕ АЛГОРИТМА
Алгоритмами в современной математике принято				называть
конструктивно	задаваемые	соответствия	между словами в абст

рактных алфавитах.

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

Алфавит, как любое множество, задается перечислением его элементов, т. е. символов

	A = {a,b,c,d},		В={х,у}-
Под словом	или строкой	алфавита будем		понимать	любую
конечную упорядоченную последовательность				символов.	Число
символов в слове называется длиной этого слова.
Алфавитным	оператором	или	алфавитным	отображением на

зывается всякое соответствие, сопоставляющее словам некоторого алфавита слова того же самого или какого-то другого фиксирован

ного алфавита. При этом первый алфавит	называется		входным,
второй — выходным алфавитом данного оператора.
Алфавитный оператор, сопоставляющий	слову	а из	входного
алфавита А слово р из выходного алфавита	В,	запишется как
Га = р.

В случае совпадения входного и выходного алфавитов говорят,

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

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

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

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

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

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

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

Таким образом, алгоритм — алфавитный оператор вместе с правилами, определяющими его действие.

Два алфавитных оператора считаются равными, если они име ют одну и ту же область определения и сопоставляют любому

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

такого рода любому входному слову сопоставляет только одно вы

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

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

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

Теперь эквивалентность алгоритмов может быть определена следующим образом: два алгоритма эквивалентны, если совпадают их области применимости и результаты переработки любого слова

из	этой области.
	В общем случае различают еще случайные и самоизменяющие
ся	алгоритмы.

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

Алгоритм называется самоизменяющимся, если он, перерабаты вая входные слова, сам изменяется в процессе такой переработки.

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

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

Всякий общий способ задания алгоритмов называется алгорит мической системой.

Примерами алгоритмических систем могут служить машины Тьюринга, нормальные алгоритмы Маркова, операторные алгорит мы Ляпунова, блок-схемный способ алгоритмизации, алгоритми ческие языки.

Приведенное выше определение алгоритма связано с алгорит мической системой А. А. Маркова.

Самое общее понятие алгоритма при современном состоянии науки связывается с понятием частично-рекурсивной функции. Под алгоритмом понимается система вычислений, которая для некото рого класса задач из записи условий задачи У позволяет получить запись решения задачи Р при помощи однозначно определенной последовательности операций.

Во всех интересующих математиков случаях доступные пере работке данным алгоритмом записи условий У легко включаются в занумерованную неотрицательными целыми числами последова тельность

Уо, УьУ 2 , --- ,Уп, --- , а записи решений Р — в последовательность

Ро, Р±, Рг, - • - ,Рп,- • •,

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

Уп *~Рт,

однозначно определяется заданной на G числовой функцией

т — (р(п).

Таким образом, произвольный алгоритм сводится к алгоритму вычисления значений некоторой числовой функции.

Обратно, если для функции ф существует алгоритм, который, будучи применен к стандартной записи значения аргумента п из области определения функции q>, приводит к стандартной записи значения функции т=«р (п), то функция ср называется алгоритми чески вычислимой или просто вычислимой функцией. Поэтому во

прос об определении	алгоритма по существу равносилен		вопросу
об определении вычислимой		функции.
В данном случае	понятие	стандартной записи означает	фикси

рованный стандартный способ записи чисел, например, в десятич

ной	системе счисления.
	В настоящее время понятие алгоритмически вычислимой функ
ции	идентифицируется с понятием частично-рекурсивной функ
ции	[43].


Алгоритм задается при помощи предписания,						указывающего
способ	перехода	от некоторого		состояния	5 процесса вычислений
к следующему состоянию S*,			т. е. при помощи оператора				Qr(S) =
=S*.	В классе	G ( T ) = {S}	возможных		состояний	выделяются
класс	исходных	состояний И(Г),		представляющих		собой	записи

условий задач, и класс заключительных состояний С(Г). При по лучении состояния из класса С (Г) алгоритмический процесс за канчивается. Область D(T) = G(T), на которой оператор Q опре делен, естественно считать непересекающейся с С(Г). Класс со стояний, не входящих ни в С(Г), ни в £>(Т), обозначим R (Г).

Алгоритмический процесс

S°=Y(=H(r);

Si = Qr(S°);

может

развиваться

одним из

следующих

трех

способов:

1. При

каком-либо t = t

процесс

приводит

заключительному

состоянию

S*e=C(r),

после чего из этого заключительного

состояния

извлекается ре

шение

Р.

При

каком-либо t = t

процесс

заканчивается безрезультатно.

3. Процесс продолжается неограниченно, не приводя к резуль

тату.

С(Г)

Класс

тех

У ^ # ( Т ) ,

которые

приводят

первому типу

течения процессов, называется областью применимости

алгоритма.

Все сказанное о рекурсивных функциях полностью

относится и

ко всем

алгоритмическим

системам.

§ I. 4. ПОНЯТИЕ ТЕОРИИ ГРАФОВ

Пусть

А и

В—-некоторые

множества.

Тогда

а е Л означает,

что а

принадлежит

множеству

А;

а не принадлежит А;

Ас^В—

любой

элемент

из

принадлежит

В;

А —В,

если AczB

и ВаА,

и АФВ

— в противном

случае;

А П В — пересечение множеств Л и Б, т. е. множество

элементов,

принадлежащих

В;

Л (J В — объединение множеств

Л и В,

т. е. множество элемен

тов, принадлежащих

или

А,

или

В,

или

[\В;

Л \ Б — разность множеств Л и Б, т. е. множество элементов из

А,	не	принадлежащих	В;
Ах В—декартово		произведение	множества Л и В, т. е. множе
ство всех map (а, Ь), где а е Л , Ь^В;
И \| —означает число элементов			конечного множества Л;
0 — пустое множество.
Пусть X и	Y — непустые множества,			т. е. ХФ0	и	Уф0.	Ото
бражение Г множества X в множество				Y есть закон,		по которому
каждому элементу из X ставится			в соответствие		некоторое		под
множество Гх	элементов из У. Отображение Г называется						одно-

значным, если

каждому элементу

из X

ставится

соответствие

ровно один элемент из У.

элементу

Обозначим

через

Г - 1 закон, по

которому

каждому

у из У ставится в соответствие подмножество

ГУ~1^Х,

представ-

ляющее собой

совокупность

таких

элементов

x e l ,

для

которых

у<=Гх, т. е.

Гу~1 =

{х/у^Гх}.

G — (X, Г),

если задано

Говорят, что задан граф

G, и пишут

непустое множество X и отображение Г множества X в X.

Элементы

множества X

изображают

точками

на

плоскости и

точку х соединяют с точкой

непрерывной

линией

со

стрелкой,

направленной

от х к

у, если у е Г ж . Получившуюся

картину

назы

вают изображением

графа

на плоскости. Элементы множества X

называют вершинами

(или

точками) графа G, а пары (х, у),

для

которых у^.Гх,—

дугами графа

G. Множество

дуг графа

обознача

ют через U, так что

граф

можно

записать также

виде

С=(Х,

U).

Две вершины х и у являются граничными

вершинами

дуги

м,

если

х—начало

дуги,

у — конец

дуги.

Две вершины х и у

смежны, если

они различны

и существует

дуга, идущая от одной из них к другой.

Говорят, что дуга и исходит из вершины х, если х является на

чалом, но не является

концом

и,

и что

дуга

заходит

в х,

если

является концом, но не является началом

и.

В обоих

случаях

дуга

и называется инцидентной вершине х, а

вершина

х — инцидентной

дуге

и.

х, является

Общее число дуг, инцидентных вершине

степенью

вершины х

обозначается

(х).

Для каждой вершины вводится понятие

полустепени

захода

полустепени

исхода.

Р+ (х)

х — количество

Полустепень захода

вершины

дуг,

захо

дящих в данную вершину. Полустепень

исхода

Р~

(х)

вершины

х — количество

дуг, исходящих

из

данной

вершины.

Для графа, изображенного на рис. 1,

/>+(л-4 )=2; P-(Xi)

Р{хА) =Р+(х4)

+Р-(х4)

= 2 + 1 = 3.

Вершина

называется

входом,

если

/>+ (х)

= 0 ,

Р-(х)¥=0,

и называется выходом,

если Р+(х)Ф0,

Р~(х)

= 6.

Путем

в графе G(X,U)

назы

вается

такая

последовательность

дуг

(«1, и2,...,

ип),

в которой

ко

нец каждой предыдущей дуги сов

падает

с началом следующей.

Путь

называется

простым,

когда

нем

никакая

дуга

не

встречается

дважды,

состав

ным, если какая-либо

из

дуг

Рис.

Пример графа

встречается

более одного

раза.

Путь, в котором никакая		вершина не встречается			дважды,—
элементарный путь.
Длина пути — число	дуг	последовательности.
Контур — конечный	путь,	начинающийся		и заканчивающийся
в одной и той же вершине. Контур единичной				длины	называется
петлей.
Так же, как и путь, контур может			быть простым, если в нем ни
одна дуга не встречается дважды,			сложным — в противном слу
чае; элементарным, если все		его вершины различны (за исключе

нием начальной и конечной, которые совпадают); гамильтоновым, если контур проходит через все вершины графа, притом только по одному разу (за исключением начальной и конечной вершин); эйлеровым ,если он проходит через все дуги графа и притом толь

ко по одному разу.
Графы можно рассматривать с учетом	или без учета	ориента
ции его дуг. В зависимости от этого различают три вида		графов:
1. Ориентированные графы, в которых	вершины соединяются

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

2.Неориентированные графы, в которых вершины соединяются линиями без указания ориентации. Такие линии называют реб рами.

3.Смешанные графы, состоящие из дуг и ребер.

Граф G(X, U), состоящий только из изолированных вершин, называется нуль-графом. Для него справедливо соотношение

P+{Xi)=P-(xt)=0,

где Xi^X.

Если степени всех вершин графа одинаковы, то граф называет ся однородным.

Нуль-граф всегда однороден, так как степени всех его вершин равны нулю.

Граф G(X, U), в котором любые две смежные вершины соеди

нены только		двумя противоположно						ориентированными		дугами,
называется		симметрическим.
Для симметрического графа справедливо условие:
если (хи	х2)	то и (х2, X\)^U,				т. е. принадлежность			дуги		(хих2)
к множеству		U влечет		за	собой		принадлежность		к U	и	дуги
(х2, Xi).	G(X,U)		без петель, в котором каждая пара						смежных вер
Граф
шин соединена только в одном направлении, называется										антисим
метрическим. Для него справедливо условие:
если	(х\,	x2)^U,	то	(х2,	х{)	не	принадлежит U.				оди
Граф	G(X, U),		в котором любая					пара вершин соединена

наковым числом дуг, называется полным. Наиболее простой при

мер полного	графа — многоугольник с п			вершинами, у	которого
проведены	все	диагонали.
Подграфом		графа	G(X, Г) называется	гдяф_(?(71. ГА),	опреде
ляемый следующим			образом:	[ Н л у ^ ~ ^ ~	-
2. Заказ 4230.				/ R/f;'.'-'"	- H R f l

С О Р

1. Вершинами А	подграфа G		(А,	ГА)	является некоторое				под
множество вершин	графа	й(Х,Г),		т. е.	АаХ.	Г	(А,	ГА) являет
2. Отображением	каждой вершины подграфа
ся пересечение отображения той же				вершины в		графе		6(Х,Г)	со
всем подмножеством	вершин А подграфа G (А, ГА),						т. е.
	ГА(х)	= Гх	П А.
Частичным графом для		G(X,	Г)	называется			граф	G(X,	F), в

котором содержатся все вершины и некоторое подмножество дуг исходного графа, т. е. Fat.

Рассмотрим некоторые операции теории графов.

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

М, в которое входят элементы						множества			Мх и недостающие эле
менты множества М2.
Операция		объединения графов записывается в виде:
		G(X, J T)=G 1 (X 1 ,A) U						02(Х2,Г2),
где G i f X ^ )		и G2(X2r2)		— исходные				графы;
G(X,	Г)—объединение				исходных			графов.
Ниже	приводятся правила,					по	которым		определяется	объеди
нение графов		G(X,	Г):	G(X,	Г)
1. Вершинами графа							является		объединение	вершин
исходных	графов		Gx(Xh	Гх)	и	G2(X2T2),			т. е.
				х^Хг			и х2	•
2. Отображения			для каждой			вершины графа G(X, Г)				получа

ются путем объединения отображений той же вершины для исход

ных графов Gl(Xl, Гх)	и G2(X2,	Г2),	т. е.
Гхг	= ГхХ1 U	F2Xi	•

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

Пересечение графов записывается в виде:


		0(Х,Г)	= 01(ХиГ1)		Л	С2(Х2,Г2),
где Gx(Xh	Гх) и	G2(X2,	Г2)	— исходные графы;
G(X,	Г)—пересечение			исходных		графов.		G(X,r):
Правила, по которым определяется пересечение графов								G(X,r):
1. Вершинами		графа	G(X, Г)		является		пересечение	вершин
исходных	графов	GX(XU	Гх)	и G2(X2,		Г2),	т. е.

Х = ХХ [)Х2 •

Другими словами, вершинами графа G(X, Г) будут только об щие вершины исходных графов.

Отображения

для каждой

вершины графа G(X, Г) получа

ются

пересечением

отображений

для

той же вершины

исходных

графов

GX(XU

Гх)

и G2(X2,

Г2),

т. е.

ГXi = TxXi

П r2Xi

•

Другими

словами, отображениями

для

каждой

вершины

ново

го графа

G(X, Г) являются

отображения,

общие

для тех же

вер

шин в исходных графах.

Разность

графов.

При

определении

данной операции

использу

ется

понятие

разности из

теории

множеств,

которое заключается

в следующем: если даны два

множества

М\

я М2,

то

разностью

этих множеств является новое множество М, содержащее элемен

ты первого множества Ми

за исключением

тех элементов,

которые

являются общими для множеств Mi и М2.

Разность

графов записывается в виде:

G(X,r)=Gl(Xur1)/G2(X2,r2),

где Gl(Xu

Г})

и G2(X2,

Г2)—исходные

графы;

G(X, Г)— разность исходных графов.

G(X,

Г)

Правила

определения

разности

графов

заключаются

следующем:

G(X,

Г)

1. Вершинами графа

являются

вершины

графа

G\(XU

Г\),

за

исключением вершин,

общих

для

исходных

графов,

т.

е.

X = XJX2

•

Отображением для

каждой

вершины

графа

G(X,

Г)

являет

ся разность между всем множеством вершин этого графа и отобра

жением рассматриваемой

вершины в графе Gx(Xb

Гх),

т. е.

Гх% = Х/Г\Xi

•

Произведение

графов.

Произведение

графов

записывается в

виде

G(X,r)

= Gi{Xurl)xG2(X2,

Г2),

где

G\(Xh

Л ) и

G2(X2,

Г2)

— исходные

графы;

G(X,

Г)—произведение

графов.

G(X, Г)

Правила определения

произведения

графов

состоят

в следующем:

G(X, Г)

1. Вершинами

графа

является

объединение

вершин

исходных графов

Gi(Xu

Гх)

и G2(X2,

Г2),

т. е.

Х=ХХ

и Х2 •

2. Отображения для каждой вершины

графа G(X,

Г)

определя

ются

как

Г.гг = Г2 {Г1^},

где

Гхг — отображение вершины Xi графа

G(X,

Г);

F\Xi~отображение

вершины

графа

Gi(Xu

Г,);

Г2{Л*;}

— отображение вершины графа

G2 для Л*<.

2*	19

<<< < Предыдущая 12 / 222 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ

#
19.10.20234.23 Mб13Алмазов, В. Б. Методы пассивной радиолокации учебное пособие.pdf
#
19.10.20231.86 Mб11Алтунджи, К. С. Механизация и автоматизация при бестарном хранении и внутризаводской транспортировке сахарного песка в кондитерской промышленности (обзор).pdf
#
30.10.202316.73 Mб36Алтухов В.А. Основы аэродинамики летательных аппаратов.pdf
#
22.10.202311.7 Mб6Алферов, С. А. Динамика зерноуборочного комбайна.pdf
#
23.10.20238.65 Mб30Алферова З.В. Теория алгоритмов учеб. пособие.pdf
#
20.10.20238.54 Mб20Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf
#
29.10.20232.9 Mб14Алферьевская О.Л. Контактный нагрев.pdf
#
29.10.2023976.17 Кб12Алыбаев Б. Хранение сельскохозяйственных машин.pdf
#
21.10.20239.8 Mб10Альбедо нейтронов..pdf
#
27.10.202322.03 Mб23Альбов М.Н. Рудничная геология.pdf
#
29.10.20232.04 Mб12Альбов С.В. Минеральные источники.pdf