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

UptoLike

ВУЗ: 

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

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

Рубрика: 

зависит от направленности дуг.
Количественно отношение инцидентности для вершины и выражается числом
ρ
+
(и) заходящих в нее дуг и числом ρ
–
(и) исходящих из нее дуг, называемых
соответственно полустепенями захода и исхода. Их сумма образует степень ρ(и) или
deg(u) вершины и:
ρ(и)=ρ
+
(и)+ρ
–
(и).
Вершине и смежна вершина v, если существует дуга (u, v).Отношение смежности
зависит от направленности дуг.
Число дуг, инцидентных двум вершинам и и v, характеризует их кратность ρ (и,
v):
⎪
⎩
⎪
⎨
⎧
>
=
.),(,...,v)дуг(u, несколько есть если,1
v)(u, дуга одна есть если,1
v),(u, дуги нет если0,
),(
i j
vu
vu
ρ
Примеры степени вершины и кратности дуги изображены на рис. 17.
Имеют место два особых случая для элементов графа:
1) вершина u c ρ(u)=0 называется изолированной;
2) дуга (и, u) называется петлей.
2.3. Матрица инцидентности
Матрица инцидентности A
И
представляет отношение Е
×
V и имеет размерность
m
×
n. Строкам матрицы A
И
соответствуют дуги графа, а столбцам – вершины. В
транспонированной матрице
Т
И
А они меняются местами: V
×
E, n
×
m. Матрица
инцидентности A
И
строится по следующему правилу:
(
)
(
)
(
)
() ()()
()()
()
⎪
⎪
⎩
⎪
⎪
⎨
⎧
−≠
−
=
.0
;1,0,1,,,,
,,,,
,,,,
случаяхостальныхв
vvvпарыдля
vvvпарыдляvv
vvvпарыдляvv
a
iji
jjiji
ijiji
ij
αα
ρ
ρ
В каждой строке матрицы A
И
отличны от 0 только два элемента, соответствующие
началу и концу дуги (дуг). Минусом будем помечать начало дуги. Случай
α
имеет место
для петли в вершине v
i
.
Примеры.
а) Матрица инцидентности для схемы Красноярской железной дороги
имеет вид
u v
ρ(u)=5
ρ
(u, v)=3
ρ
+
(u)=3
ρ
-
(u)=2
0 0
0→ 0
0 0
a) б)
Рис. 17

Страницы