Rambler's Top100





4
1. РЁБЕРНЫЕ ФУНКЦИИ
Определение 1
Дан ориентированный граф
)E,V(G
,
VY,X
.
Множество всех дуг, ведущих из
Xx
в
Yy
, называют сечени-
ем графа G и обозначают символом
)Y,X(
,
E)y,x(,Yy,Xx:)y,x()Y,X(
Сечение назывют разрезом, если
V
XY
и обозначают
.
Пример
а
c
b
e
f
d
.)d,f(),b,e()X,Y(
,)e,d(),e,b(),e,a()Y,X(,f,eY,d,b,aX
.)d,c(),d,f(),b,e()X,X(
,)c,d(),e,d(),c,b(),e,b(),e,a()X,X(,c,f,eX
Определение 2
Дан ориентированный граф
)E,V(G
.
1) Отображение
RE:f
, где
R
неотрицательные вещест-
венные числа, называется рѐберной (или дуговой) функцией графа
G
.
2) Отображение
RV:m
называется вершинной функцией гра-
фа
G
.
Для любой дуговой функции f и вершинной функции m положим
Xx)Y,X()y,x(
)X(m)x(m,)Y,X(f)y,x(f
.