Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 20 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

Ему со от вет ст ву ет мат ри ца смеж но сти:
v
1
v
2
v
3
v
1
0 1 0
v
2
1 0 1
v
3
1 0 0
2) Мат ри цей ин ци дент но сти орг ра фа D на зы ва ет ся (n´m) — мат -
ри ца B(D) = || b
ij
||, у ко то рой мат рич ные эле мен ты рав ны:
b
v x
v
ij
i j
i
= -
1
1
, если являет ся к онцом
, åñ ëè ÿâëÿåòñÿ íà÷àëîì
0, åñëè íå èíöèíäåíòíà
x
v x
j
i j
ì
í
ï
î
ï
.
При мер. Рас смот рим орг раф D, изо бра жен ный на ри сун ке 1.4.8.
Ему со от вет ст ву ет мат ри ца инцидентности:
x
1
x
2
x
3
x
4
v
1
–1 0 1 1
v
2
1 –1 0 –1
v
3
0 1 –1 0
Ана ло гич но вво дят ся мат ри цы смеж но сти и ин ци дент но сти для
не ори ен ти ро ван ных графов.
3) Мат ри цей смеж но сти гра фа G на зы ва ет ся квад рат ная мат ри ца
A(G)= || a
ij
|| по ряд ка n, у ко то рой мат рич ные эле мен ты рав ны:
a
v v X
v v X
ij
i j
i j
=
Î
Ï
ì
í
î
1
0
, { , }
, { , }
если
если
.
20
     Ему соответствует матрица смежности:

                                    v1        v2        v3
                          v1        0         1         0
                          v2        1         0         1
                          v3        1         0         0


     2) Матрицей инцидентности орграфа D называется (n´m) — мат-
рица B(D) = || bij ||, у которой матричные элементы равны:


                     ì 1, если v i является концом x j
                     ï
               bij = í -1, åñëè v i ÿâëÿåòñÿ íà÷àëîì x j .
                     ï
                     î 0, åñëè v i íå èíöèíäåíòíà x j


     Пример. Рассмотрим орграф D, изображенный на рисунке 1.4.8.
Ему соответствует матрица инцидентности:

                               x1        x2        x3        x4
                     v1     –1           0         1         1
                     v2        1         –1        0         –1
                     v3        0         1         –1        0

     Аналогично вводятся матрицы смежности и инцидентности для
неориентированных графов.


     3) Матрицей смежности графа G называется квадратная матрица
A(G)= || aij || порядка n, у которой матричные элементы равны:


                            ì1, если { v i , v j } Î X
                      aij = í                          .
                            î0, если { v i , v j } Ï X
20

Страницы