Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

прос об определении

алгоритма по существу равносилен

вопросу

об определении вычислимой

функции.

В данном случае

понятие

стандартной записи означает

фикси­

ной

системе счисления.

В настоящее время понятие алгоритмически вычислимой функ­

ции

идентифицируется с понятием частично-рекурсивной функ­

ции

[43].

Алгоритм задается при помощи предписания,

указывающего

способ

перехода

от некоторого

состояния

5 процесса вычислений

к следующему состоянию S*,

т. е. при помощи оператора

Qr(S) =

=S*.

В классе

G ( T ) = {S}

возможных

состояний

выделяются

класс

исходных

состояний И(Г),

представляющих

собой

записи

может

развиваться

одним из

следующих

трех

способов:

1. При

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

процесс

приводит

к

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

состоянию

S*e=C(r),

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

состояния

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

шение

Р.

_

2.

При

каком-либо 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, так что

граф

G

можно

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

в

виде

С=(Х,

U).

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

вершинами

дуги

м,

если

х—начало

дуги,

у — конец

дуги.

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

смежны, если

они различны

и существует

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

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

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

концом

и,

и что

дуга

заходит

в х,

если

х

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

и.

В обоих

случаях

дуга

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

вершина

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

дуге

и.

х, является

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

степенью

вершины х

и

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

Р

(х).

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

полустепени

захода

и

полустепени

исхода.

Р+ (х)

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

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

вершины

дуг,

захо­

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

исхода

Р~

(х)

вершины

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

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

из

данной

вершины.

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

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

=

l:

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

+Р-(х4)

= 2 + 1 = 3.

Вершина

х

называется

входом,

если

/>+ (х)

= 0 ,

а

Р-(х)¥=0,

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

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

Р~(х)

= 6.

Путем

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

назы­

вается

такая

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

дуг

(«1, и2,...,

ип),

в которой

ко­

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

падает

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

Путь

называется

простым,

когда

в

нем

никакая

дуга

не

встречается

дважды,

и

состав­

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

из

дуг

Рис.

1.

Пример графа

встречается

более одного

раза.

Путь, в котором никакая

вершина не встречается

дважды,—

элементарный путь.

Длина пути — число

дуг

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

Контур — конечный

путь,

начинающийся

и заканчивающийся

в одной и той же вершине. Контур единичной

длины

называется

петлей.

Так же, как и путь, контур может

быть простым, если в нем ни

одна дуга не встречается дважды,

сложным — в противном слу­

чае; элементарным, если все

его вершины различны (за исключе­

ко по одному разу.

Графы можно рассматривать с учетом

или без учета

ориента­

ции его дуг. В зависимости от этого различают три вида

графов:

1. Ориентированные графы, в которых

вершины соединяются

нены только

двумя противоположно

ориентированными

дугами,

называется

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

Для симметрического графа справедливо условие:

если (хи

х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), в

М, в которое входят элементы

множества

Мх и недостающие эле­

менты множества М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

•

0(Х,Г)

= 01(ХиГ1)

Л

С2(Х2,Г2),

где Gx(Xh

Гх) и

G2(X2,

Г2)

— исходные графы;

G(X,

Г)—пересечение

исходных

графов.

G(X,r):

Правила, по которым определяется пересечение графов

1. Вершинами

графа

G(X, Г)

является

пересечение

вершин

исходных

графов

GX(XU

Гх)

и G2(X2,

Г2),

т. е.