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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

При мер. Рас смот рим граф G, и изо бра жен ный на ри сун ке 1.4.9
Ему со от вет ст ву ет мат ри ца смеж но сти:
A(G)=
v
1
v
2
v
3
v
1
0 1 1
v
2
1 0 0
v
3
1 0 0
4) Мат ри цей ин ци дент но сти гра фа G на зы ва ет ся (n´m) мат ри ца
B(G) = || b
ij
||, у ко то рой мат рич ные эле мен ты рав ны:
b
v x
v x
ij
i j
i j
=
ì
í
î
1
0
,
,
если инцидентна
если не инцидентна
.
При мер. Рас смот рим граф G, изо бра жен ный на ри сун ке 1.4.9. Ему
со от вет ст ву ет мат ри ца ин ци дент но сти:
B(G)=
x
1
x
2
v
1
1 1
v
2
1 0
v
3
0 1
Мат ри цу смеж но сти мож но оп ре де лить и для псев до гра фов. То гда
a
ij
=k, где k крат ность ду ги или реб ра в этом псев до гра фе.
21
Рис. 1.4.9
     Пример. Рассмотрим граф G, и изображенный на рисунке 1.4.9




                                 Рис. 1.4.9

     Ему соответствует матрица смежности:

                                     v1        v2    v3
                           v1        0         1     1
                 A(G)=
                           v2        1         0     0
                           v3        1         0     0

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

                       ì1, если v i инцидентна x j
                 bij = í                              .
                       î0, если v i не инцидентна x j

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

                                          x1        x2
                                v1        1         1
                   B(G)=
                                v2        1         0
                                v3        0         1

       Матрицу смежности можно определить и для псевдографов. Тогда
aij=k, где k кратность дуги или ребра в этом псевдографе.
                                                                  21

Страницы