ВУЗ:
Составители:
Рубрика:
Пусть C = ||c
ij
||, D = ||d
ij
|| — мат ри цы раз мер но сти (m´n), то гда F =
= || f
ij
|| = C*D — есть бу ле ва (m´n)-мат ри ца,у ко то рой
( )
f V c d
ij
r
k
ir rj
=
=1
&
;
i = 1,2 ... m, j = 1,2, ... n.
в) Вве дем опе ра цию (sign) пе ре хо да от про из воль ной (m´n)-мат -
ри цы D = ||d
ij
|| с не от ри ца тель ны ми эле мен та ми к бу ле вой (m´n)-мат ри -
це C = ||c
ij
|| = sign D, у ко то рой c
ij
= sign d
ij
; i = 1,2 ... m, j = 1,2 ... m, где для
лю бо го чиcла t ³ 0:
sign
если
если
t
t
t
=
>
=
ì
í
î
1 0
0 0
,
,
.
Для лю бых мат риц D
1
, D
2
(под хо дя щих раз мер но стей) с не от ри ца -
тель ны ми эле мен та ми вы пол ня ют ся равенства:
sign (D
1
+ D
2
) = sign D
1
Ú sign D
2
;
sign (D
1
D
2
) = sign D
1
* sign D
2
.
6) Объ е ди не ни ем гра фов G
1
= (V
1
; X
1
) и G
2
= (V
2
; X
2
) на зы ва ет ся граф
G
1
È G
2
= (V
1
ÈV
2
; X
1
ÈX
2
).
Пе ре се че ни ем G
1
= (V
1
; X
1
) и G
2
= (V
2
; X
2
) на зы ва ет ся граф: G
1
ÇG
2
=
= (V
1
ÇV
2
; X
1
ÇX
2
); при этом V
1
ÇV
2
¹ Æ.
Под гра фом гра фа G на зы ва ет ся граф, все вер ши ны ко то ро го со -
дер жат ся сре ди вер шин и ре бер гра фа G. Под граф на зы ва ет ся соб ст вен -
ным, ес ли он отличен от самого графа.
7) Под гра фом гра фа G = (V; X), по ро ж ден ным под мно же ст вом
V
1
ÌV, где V
1
¹ Æ, на зы ва ет ся граф G
1
= (V
1
; X
1
) , мно же ст во X
1
ре бер ко -
то ро го со сто ит из тех и толь ко тех ре бер гра фа G, оба кон ца ко то ро го
ле жат в V
1
.
Все при ве ден ные оп ре де ле ния вер ны и для орг ра фов.
Тео ре ма. Пусть G = (V,X) — не ко то рый граф, а G
1 —
под граф гра фа
G, по ро ж ден ный мно же ст вом V
1
(V
1
Ì V; V
1
¹ Æ). То гда A(G
1
) яв ля ет ся
под мат ри цей мат ри цы A(G), на хо дя щей ся на пе ре се че нии строк и
столб цов, со от вет ст вую щих вер ши нам из V
1
.
8) Го во рят, что вер ши на w орг ра фа D дос ти жи ма из вер ши ны v,
ес ли ли бо w = v, ли бо су ще ст ву ет путь из v в w.
23
Пусть C = ||cij||, D = ||dij|| — матрицы размерности (m´n), тогда F =
k
= || fij || = C*D — есть булева (m´n)-матрица,у которой f ij = V (c ir & drj );
r =1
i = 1,2 ... m, j = 1,2, ... n.
в) Введем операцию (sign) перехода от произвольной (m´n)-мат-
рицы D = ||dij|| с неотрицательными элементами к булевой (m´n)-матри-
це C = ||cij|| = sign D, у которой cij = sign dij; i = 1,2 ... m, j = 1,2 ... m, где для
любого чиcла t ³ 0:
ì 1, если t > 0
sign t = í .
î0, если t = 0
Для любых матриц D1, D2 (подходящих размерностей) с неотрица-
тельными элементами выполняются равенства:
sign (D1 + D2) = sign D1 Ú sign D2;
sign (D1D2) = sign D1 * sign D2.
6) Объединением графов G1 = (V1; X1) и G2 = (V2; X2) называется граф
G1 È G2 = (V1ÈV2; X1ÈX2).
Пересечением G1 = (V1; X1) и G2 = (V2; X2) называется граф: G1ÇG2 =
= (V1ÇV2; X1ÇX2); при этом V1ÇV2 ¹ Æ.
Подграфом графа G называется граф, все вершины которого со-
держатся среди вершин и ребер графа G. Подграф называется собствен-
ным, если он отличен от самого графа.
7) Подграфом графа G = (V; X), порожденным подмножеством
V1ÌV, где V1 ¹ Æ, называется граф G1 = (V1; X1) , множество X1 ребер ко-
торого состоит из тех и только тех ребер графа G, оба конца которого
лежат в V1.
Все приведенные определения верны и для орграфов.
Теорема. Пусть G = (V,X) — некоторый граф, а G1 — подграф графа
G, порожденный множеством V1(V1 Ì V; V1 ¹ Æ). Тогда A(G1) является
подматрицей матрицы A(G), находящейся на пересечении строк и
столбцов, соответствующих вершинам из V1.
8) Говорят, что вершина w орграфа D достижима из вершины v,
если либо w = v, либо существует путь из v в w.
23
Страницы
- « первая
- ‹ предыдущая
- …
- 21
- 22
- 23
- 24
- 25
- …
- следующая ›
- последняя »
