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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

При мер. Рас смот рим псев до граф, изо бра жен ный на ри сун ке
1.4.10.
Ему со от вет ст ву ет мат ри ца смеж но сти:
G =
v
1
v
2
v
3
v
1
1 2 0
v
2
0 0 0
v
3
2 3 2
Оп ре де ле ние мат ри цы ин ци дент но сти без из ме не ний пе ре но сит -
ся и на псев до гра фы и на муль ти гра фы. Не труд но ви деть, что мат ри ца
A(G) яв ля ет ся сим мет рич ной для лю бо го не ори ен ти ро ван но го гра фа G.
Мат ри ца A(D) в общем случае не является симметричной.
По мат ри це ин ци дент но сти мож но по лу чить пол ную ин фор ма -
цию о гра фе, в то вре мя как по мат ри це смеж но сти не воз мож но уз нать
но ме ра реб ра (ду ги). Мат ри цы удоб ны для за да ния графов и орграфов
на ЭВМ.
5) Бу ле вой мат ри цей на зы ва ет ся (m´n)-мат ри ца C =||c
ij
||, у ко то рой
c
ij
{0,1}, i = 1,2, ... m, j = 1,2 ... n. Над бу ле вы ми мат ри ца ми оди на ко вой
раз мер но сти мож но про из во дить обыч ные ло ги че ские опе ра ции.
а) Пусть C = ||c
ij
||; D = ||d
ij
||, то гда F = ||f
ij
|| = C Ú D есть бу ле ва (m´n)-
мат ри ца, у ко то рой f
ij
= c
ij
Ú d
ij
, i = 1,2 ... m, j = 1,2 ... n.
б) Вве дем опе ра цию ло ги че ско го ум но же ния бу ле вых мат риц (*):
22
Рис. 1.4.10
       Пример. Рассмотрим псевдограф, изображенный на рисунке
1.4.10.




                                       Рис. 1.4.10

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

                                           v1        v2   v3
                                  v1       1         2    0
                         G=
                                  v2       0         0    0
                                  v3       2         3    2

      Определение матрицы инцидентности без изменений переносит-
ся и на псевдографы и на мультиграфы. Не трудно видеть, что матрица
A(G) является симметричной для любого неориентированного графа G.
Матрица A(D) в общем случае не является симметричной.
      По матрице инцидентности можно получить полную информа-
цию о графе, в то время как по матрице смежности невозможно узнать
номера ребра (дуги). Матрицы удобны для задания графов и орграфов
на ЭВМ.

        5) Булевой матрицей называется (m´n)-матрица C =||cij||, у которой
cij {0,1}, i = 1,2, ... m, j = 1,2 ... n. Над булевыми матрицами одинаковой
размерности можно производить обычные логические операции.
        а) Пусть C = ||cij||; D = ||dij||, тогда F = ||fij|| = C Ú D есть булева (m´n)-
матрица, у которой fij = cij Ú dij, i = 1,2 ... m, j = 1,2 ... n.
        б) Введем операцию логического умножения булевых матриц (*):
22

Страницы