Дискретная математика. Никищенков С.А - 13 стр.

UptoLike

ВУЗ: 

СамГУПС | Самара

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

Рубрика: 

V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 V13
V1 1 1 1
V2 1 1 1
V3 1 1
V4 1 1 1
V5 1 1 1
V6 1
V7 1 1 1
V8 1 1 1
V9 1 1 1
V10 1 1
V11 1
V12 1
V13 1
б) Матрица инцидентности A
И
для графа G, изображенного справа от нее, имеет
вид:
2.4. Понятие полноты
Для графа понятие полноты определяется относительно множества дуг E.
1. Нуль или нулевая полнота имеет место при Е=∅. Ей соответствует нуль-граф
(рис. 19,а) или нуль-отношение R
⊂
X
×
X=∅, (x 0 y). Оно интерпретируется как "быть
несравнимым".
2. Единица или единичное отношение Δ (быть равным) представляется
диагональю двумерного множества Е: Δ={(v
i
, v
j
)⎜v
i
∈
V}. Ему соответствует граф, все
вершины которого изолированы и имеют петли (рис. 19,б).
3. Универсальное или полное отношение Х
×
X=X
2
– это декартово произведение
множества Х на себя. Оно выражается полным графом. Различают следующие виды
универсального отношения:
а) полное Х
×
Х (с единицей) или полный граф G
p
с петлями и двунаправленными
v
1
v
2
v
4
v
3
v
1
v
2
v
4
v
3
а) б)
Рис. 19
v
1
v
2
v
3
v
4
(v
1
, v
2
) –1 1 0 0
(v
2
, v
3
) 0 –1 1 0
(v
3
, v
4
) 0 0 –1 1
(v
4
, v
1
) 1 0 0 –1
A
И
=
v
1
v
2
v
3
v
4
Рис. 18

Страницы