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

2.

Отображения

для каждой

вершины графа 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

•

2.

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

каждой

вершины

графа

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~отображение

вершины

xt

графа

Gi(Xu

Г,);

Г2{Л*;}

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

G2 для Л*<.

2*

19

Например, рассматривается отображение для вершины

х{

про­

изведения графов

G(X,

Г). Отображениями

вершины Х\

в

графе

G\

являются

х2

и

х3 ,

т. е.

Г1JC1 =

{л:2, Хз}.

В этом случае

необходимо рассмотреть

отображения

вершин

х2

и х3 в графе

G2(X2,

Г2). Пусть

этими отображениями

в

графе

G2

являются

хх

и лс4

соответственно, т. е.

А * 2 = ф ' 1 }

и

Г2х3={хА}.

Следовательно, отображениями вершины хх в графе

G(X, Г)

будут вершины

хх

и

xit т. е.

Гхх = {хх,

х4}.

1

2

3

4

1

1

1

1

1

4

2

0

0

0

0

0

3

0

1

0

1

2

4

0

0

1

0

1

1

2

2

2

полустепень

исхода вершины ж,-

численно

равна сумме

элементов

i-й

строки

матрицы

P-(Xi)

= 2 а *

а

полустепень захода — сумме элементов

/-го столбца

при / = i

P+(Xi)

= 2 я* (* =

/ ) .

Две

матрицы

смежности A = (af)

и В = (Ь^),

соответствующие

графам

Gi(X,

U)

и G2(X,

V),

могут

быть

просуммированы,

если

они одного и того же размера, т. е. имеют

одинаковое

количество

строк

и

столбцов.

Сумма двух 'матриц смежности А + В определяется

следующи­

ми правилами:

1. Число элементов суммы матриц

равно

числу элементов

ис­

ходных матриц, т. е. ПА+В =

ПА =

ПВ.

2. Каждый элемент суммы матриц

получается

суммированием

соответствующих

элементов исходных

матриц, т. е.

Ci5 —cii5

+bi з

•

Так, для

двух

графов

G{(X,

U)

и

G2(X,

V),

представленных

матрицами

смежности

1

2

3

1

2

3

Л =

•

1

0

2

0

В=

1

0

0

0

2

0

0

0

2

1

0

1

3

1

1

0

3

0

0

1

сумма

этих

матриц

смежности

будет иметь вид:

1

2

3

А+В

=

1

0

2

0

2

I

0

1

3

1

1

1

2)

Гх^ич

U

V*i •

Указанный

граф

G(X,

Г) может

быть

построен по отображени­

ям исходных

графов:

Г х , = [/х,

U Vxi = {xl,x2}

U { 0 } =

{*1Л};

Гх2=их2

у

Vx2={0}

U {хих3}

= {хих3} ;

Гх3=

Ux3

(J

Vx3=

{хих2}

у

{х3}

=

{хих2,Хг}.

C=A+B—*-.G

= Gi U G2 •

Две

матрицы

смежности А = (а^)

и В = (Ь^), соответствующие

графам

Gi(X, U)

и G2(X, V),

могут

быть перемножены в том слу­

При этом матрица-произведение С=АхВ

имеет

то же

количе­

ство строк, что и Л, и то же количество столбцов, что и

В.

Полезно напомнить, что элемент С,-* матрицы-произведения

по­

лучается

суммированием

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

всех

элементов

i

(строки

матрицы Л) на

соответствующие

элементы

к (столбцы

матри­

цы

В), т.

е.

, j

r

\

Ct

=

2

а,'Ь}

•

Г

""Si

j = l

Рассмотрим произведение матриц на следующем примере. Да­

ны

графы

G\(X,

U),

G2(X,

V)

и

соответствующие

им

матрицы

смежности А и В:

1

2

3

4

1

2

3

4

1

0

1

1

0

1 "

0

0

0

0

Л--

2

0

0

0

0

В=

2

0

0

1

1

3

0

0

0

1

3

1

1

0

1

4

0

1

0

0

4

0

1

0

0

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

данных

матриц

смежности

имеет

вид:

1

2

3

4

1

1

1

1

2

2

0

0

0

0

3

0

1

0

0

4

0

0

1

1