Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 11 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Матрица инциденций представляет собой прямоугольную матрицу
размером n*m, где n- количество вершин графа, а m - количество дуг графа.
Обозначается матрица инциденций B={ b
ij
},i=1,2,...,n, j=1,2,...,m.
Каждый элемент матрицы определяется следующим образом:
b
ij
=1, если x
i
является начальной вершиной дуги a
j
,
b
ij
=-1, если x
i
является конечной вершиной дуги a
j
,
b
ij
=0, если x
i
не является концевой вершиной дуги a
j
или если a
j
является
петлей.
На рис.5,а ,б приведен граф и его матрица смежности, по которой можно
найти характеристики вершин. Так сумма элементов i-ой строки матрицы дает
полустепень исхода вершины x
i
, а сумма элементов i-го столбца дает
полустепень захода вершины x
i
. По матрице смежности можно найти прямые и
обратные отображения. Рассмотрим i-ю строку матрицы. Если элемент a
ij
=1,
то элемент графа x
j
входит в отображение Г(x
i
). Например, в 2-й строке
матрицы А (рис.5,б) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х
2
)={
x
2
, x
5
}.
Для графа на рис.5,а матрица инциденций приведена на рис.5,в. Поскольку
каждая дуга инцидентна двум различным вершинам, за исключением того случая,
x
6
x
1
x
2
x
3
x
4
x
5
a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
a
9
a
10
а)
Рис. 5. Орграф и его матричное представление:
а) - орграф; б)- матрица смежности;
в) - матрица инциденций.
x
1
x
2
x
3
x
4
x
5
x
6
x
1
0 1 1 0 1 0
x
2
0 1 0 0 1 0
A = x
3
0 0 0 0 0 0
x
4
0 0 1 0 0 0
x
5
0 0 0 1 0 0
x
6
1 0 0 0 1 1
б
)
a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
a
9
a
10
x
1
1 1 0 0 0 0 0 1 -1 0
x
2
-1 0 0 1 0 0 0 0 0 0
B= x
3
0 -1 0 0 -1 0 0 0 0 0
x
4
0 0 0 0 1 -1 0 0 0 0
x
5
0 0 0 -1 0 1 -1 -1 0 0
x
6
0 0 0 0 0 0 1 0 1 0
в) 
                             x1 a 1                a3
                                             x2                                  x1   x2    x3    x4   x5   x6
                   a9                                                       x1   0    1     1     0    1    0
                                                  a2                        x2   0    1     0     0    1    0
             x6         a8                              x3        A=        x3   0    0     0     0    0    0
      a10                              a4                                   x4   0    0     1     0    0    0
                  a7                                                        x5   0    0     0     1    0    0
                                                  a5                        x6   1    0     0     0    1    1
                                  a6
                         x5                 x4
                                                                       б)


                                  а)


                             a1   a2        a3     a4        a5   a6    a7       a8    a9        a10
                  x1          1   1         0       0        0    0     0         1    -1         0
                  x2         -1   0         0       1        0    0     0        0     0          0
            B=    x3          0   -1        0       0        -1   0     0        0     0          0
                  x4          0   0         0       0        1    -1    0        0     0          0
                  x5          0    0        0      -1         0    1    -1       -1    0          0
                  x6          0   0         0       0        0    0     1         0    1          0
                                                        в)


                       Рис. 5. Орграф и его матричное представление:
                       а) - орграф; б)- матрица смежности;
                        в) - матрица инциденций.



         Матрица инциденций            представляет собой прямоугольную матрицу
размером n*m, где n- количество вершин графа, а m - количество дуг графа.
Обозначается матрица инциденций B={ bij },i=1,2,...,n, j=1,2,...,m.
         Каждый элемент матрицы определяется следующим образом:
         bij=1, если xi является начальной вершиной дуги aj,
         bij=-1, если xi является конечной вершиной дуги aj,
         bij=0, если xi не является концевой вершиной дуги aj или если aj является
петлей.
         На рис.5,а ,б приведен граф и его матрица смежности, по которой можно
найти характеристики вершин. Так сумма элементов i-ой строки матрицы дает
полустепень исхода вершины xi, а сумма элементов i-го столбца дает
полустепень захода вершины xi. По матрице смежности можно найти прямые и
обратные отображения. Рассмотрим i-ю строку матрицы. Если элемент aij=1,
то элемент графа xj входит в отображение Г(xi). Например, в 2-й строке
матрицы А (рис.5,б) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х2)={
x2, x5}.
         Для графа на рис.5,а матрица инциденций приведена на рис.5,в. Поскольку
каждая дуга инцидентна двум различным вершинам, за исключением того случая,

Страницы