Теория ресурсных сетей

Л.Ю. Жилякова, О.П. Кузнецов

ТЕОРИЯ 
ТЕОРИЯ 

РЕСУРСНЫХ  СЕТЕЙ
РЕСУРСНЫХ  СЕТЕЙ

Москва
РИОР
ИНФРА-М

УДК 519.711.74
ББК 22.18
         Ж72

Жилякова Л.Ю., Кузнецов О.П. 

Теория ресурсных сетей : монография / Л.Ю. Жилякова, О.П. Кузне
цов. — М. : РИОР : ИНФРА-М, 2020. — 283 с. — (Научная мысль). — 
https://doi.org/10.12737/21451

ISBN 978-5-369-01645-9 (РИОР)
ISBN 978-5-16-012512-1 (ИНФРА-М, print)
ISBN 978-5-16-102327-3 (ИНФРА-М, online)

Излагается разработанная авторами теория ресурсных сетей — сетей, в кото
рых узлы соединены каналами с ограниченными пропускными способностями. 
По каналам в дискретном времени происходит обмен однородным ресурсом с 
выполнением закона сохранения. Узлы отдают ресурс в зависимости от его количества по одному из двух правил с пороговым переключением. Дается классификация сетей по топологии и пропускным способностям. Исследуются динамика 
и асимптотика состояний и потоков для всех классов сетей. Представлен обширный обзор неклассических сетевых моделей.

Книга предназначена специалистам по теории графов и исследованию опе
раций, студентам, магистрантам и аспирантам, обучающимся по различным математическим, компьютерным и информационным направлениям подготовки.

УДК 519.711.74
ББК 22.18

ISBN 978-5-369-01645-9 (РИОР)
ISBN 978-5-16-012512-1 (ИНФРА-М, print)
ISBN 978-5-16-102327-3 (ИНФРА-М, online)

©  Жилякова Л.Ю., 
     Кузнецов О.П. 

Ж72

А в т о р ы :
Жилякова Л.Ю. — д-р физ.-мат. наук, ведущий научный сотрудник, Институт 

проблем управления им. В.А. Трапезникова РАН (Москва). Автор более 130 работ 
по проблемам искусственного интеллекта и интеллектуальных систем, динамической теории графов;

Кузнецов О.П. — д-р техн. наук, профессор, заведующий лабораторией, Ин
ститут проблем управления им. В.А. Трапезникова РАН (Москва). Автор более 
150 работ, в том числе двух монографий, по проблемам искусственного интеллекта и интеллектуальных систем, когнитивного анализа ситуаций, логического управления, динамической теории графов

Р е ц е н з е н т ы :
Чеботарев П.Ю. — д-р физ.-мат. наук, заведующий лабораторией, Институт 

проблем управления им. В.А. Трапезникова РАН (Москва);

Дмитриев М.Г. — д-р физ.-мат. наук, профессор факультета компьютерных 

наук, Национальный исследовательский университет «Высшая школа экономики» 
(Москва)

ФЗ 
№ 436-ФЗ
Издание не подлежит маркировке 
в соответствии с п. 1 ч. 2 ст. 1

Цветные иллюстрации доступны в электронной версии

книги в электронно-библиотечной системе ZNANIUM

по адресу http://znanium.com.

Ссылку для доступа вы можете получить

при сканировании QR-кода, размещенного на обложке

Moscow
RIOR
INFRA-M

L.Yu. Zhilyakova, O.P. Kuznetsov

RESOURCE  NETWORK 
RESOURCE  NETWORK 

THEORY
THEORY

Zhilyakova, L.Yu., Kuznetsov, O.P.
Resource network theory: monograph. — Мoscow: RIOR: INFRA-M, 2020. — 
283 p. — (Science). — https://doi.org/10.12737/21451

ISBN 978-5-369-01645-9 (RIOR)
ISBN 978-5-16-012512-1 (INFRA-M, print)
ISBN 978-5-16-102327-3 (INFRA-M, online)

Resource network is a dynamic model of redistributing resource among the nodes 

of directed weighted graph. Nonnegative weights of edges denote their capacities. The 
nodes can contain unlimited amount of resource. The network operates in discrete 
time: nodes exchange with their resources along incident edges, keeping the conservation 
law of total network recourse. A classification of networks is developed. Dynamics and 
asymptotic behavior of states and flows in networks of every class are described and 
analyzed. An extensive review of non-classical network models is presented.

The book is intended for specialists in graph theory and operations research, 

students, masters and post-graduate students of various mathematical, computer and 
information specialities.

A u t h o r s :
Zhilyakova, L.Yu. — Doctor of Physics and Mathematics, leading researcher, 

Institute of Control Sciences of RAS (Moscow). Author of more than 130 papers 
on artificial intelligence, intellectual systems, and dynamic graph theory;

Kuznetsov, O.P. — Doctor of Engineering, professor, head of laboratory, 

Institute of Control Sciences of RAS (Moscow). Author of more than 150 works, 
including two monographs, on artificial intelligence and intelligent system 
challenges, cognitive situation analysis, logic control, dynamic graph theory

R e v i e w e r s :
Chebotarev, P.Yu. — Doctor of Physics and Mathematics, head of laboratory, 

Institute of Control Sciences of RAS (Moscow);

Dmitriev, M.G. — Doctor of Physics and Mathematics, professor of Faculty 

of Computer Science, Higher School of Economics (Moscow)

©  Zhilyakova, L.Yu.,
      Kuznetsov, O.P.

Color pictures can be found at http://znanium.com.

Get the direct link scanning the QR-code on the cover of this book

............................................................................ 9 

1. ........................................................................... 12 
1.1.  ....................................................................... 14 
1.1.1.  .............................................. 14 
1.1.2.  ................... 20 
1.1.3.  , ........ 25 
1.1.4.  . (flows over time) .... 26 
1.2.  .......................... 27 
1.2.1.  ................................................................. 28 
1.2.2.   ......................... 29 
1.2.3.  .............................. 32 
1.2.4.  ............................ 34 
1.2.5.  .................................................... 36 
1.3.  ............................................ 37 
1.3.1.  Chip-firing game ........................................................................... 37 
1.3.2. .................................................................... 40
1.3.3. chip-firing game ............................. 42 
1.3.4. «»..................................................... 45 
1.3.5. «» chip-firing game .... 46 
1 ......................................................................... 46 

2. – 
........................ 48 
2.1.  ............................................................... 48 
2.2.  ......................................... 50 
2.3.  ....................... 63 
2.4.  .................................................... 65 
2 ......................................................................... 69 

3. – 
. ...................................... 72 
3.1.  ............................................................... 73 
3.2.  .... 75 

3.3.  .................... 77 
3.4.  .................................................................. 86 
3.5.  .......................................... 87 
3.6.  ............................................... 89 
3.6.1.  ............................... 89 
3.6.2.  ...................................................... 96 
3.6.3.  .......................................... 96 
3 ....................................................................... 101 

4. ... 103 
4.1.  ............................................................................. 103 
4.1.1.  ....................................................... 104 
4.1.2.  ................................................... 104 
4.2.  , ....................................................................................... 115 
4.2.1.  -......................................... 117 
4.2.2.  -........................................ 118 
4.2.3.  -.......................................... 120 
4.3.  Q1* ......................................... 122 
4.4.  ....... 123 
4.5.  R R' ........................................ 127 
4.6.  ............. 130 
4.7.  ....... 131 
4 ....................................................................... 133 

5. .......... 135 
5.1.  ............................................................. 136 
5.2.  ........................................................ 137 
5.3.  ......................................................................... 139 
5.4.  .................... 142 
5.5.  ....... 143 
5.5.1.  Z+(t) ........ 143 
5.5.2.  . ........ 147 
5.5.3.  m
C~
 – Z–(0) ................................................................................. 149 

5.5.4.  m
C~  – Z+(t) .................................................................................... 155 

5.5.5.  m
C~  – .................. 159 
5 ....................................................................... 169 

6. .................................................. 171 
6.1.  ........................................ 174 
6.2.  ................................................................... 190 
6.2.1.  ............................................................ 190 
6.2.2.  d-............... 195 
6.2.3.  .. 199 
6.3.  .............................. 204 
6.3.1.  ............................................................... 204 
6.3.2.  ...... 207 
6.3.3.  ..................................................................................... 208 
6 ....................................................................... 211 

7. .......................... 214 
7.1.  .............................. 214 
7.2.  ............................................................ 218 
7.3.  . ..... 222 
7.4.  ....................... 225 
7.4.1.  R'∞ ........................................................ 225 
7.4.2.  ...................... 229 
7.4.3.  .............. 232 
7 ....................................................................... 236 

8. ........................................................................ 237 
8.1.  , , 
δW................................................ 239 
8.2.  δW ................................................................................. 251 

8.3.  , δW .......................................................... 254 
8.4.  fsum(t) ≥ T .............................. 256 
8.5.  , ........................ 258 
8.6.  δW ................................................................. 260 
8 ....................................................................... 264
 

... 265
 

ИИТОГИ .......................................................... 268 

................................................................... 272 

...................................... 281 

................. 282 
 
 

, , , , , , , : 
, ; , , , , , , , , , – , , , .  
. , «, !» 
 
60 , -[59]. , ; , , – , . : , 
, , 
(chip-firing game) .  
– – . – , . ; . . W . t 10 

Q(t). t : vi , , «, », .. 
; , . , .  
: «» () «» .  
. 1 , . 2 
, : (, – , ). : , .. , . . : () (t → ∞) , , . 
. .   
, , , . : , , .  
. .  

, , 2008–2016 ., [25–37, 41–43, 97, 98]. 
: 
.. .. ; 
.. ; 
.. , .. , .. , .. , ; 
.. .. . 

1. , 

: 
• . 
• : –, , , , .  
• , , .  
• .  
• chip-firing game .  
• «». chip-firing game. 
 
 
. , , , , . – , , , 
, , . , : , , , ad hoc (ad hoc – , , «») . , .  
, , , 13 

. , , (, ). , , . , .  
, «» (, .) . , . (., , [72]), ; «» [120], «» , ; ,  [39, 40]. 
, : 
1) ; 
2) ; 
3) . 
. , , , . . , , . , (., , [78] ), , . , , 
. «» (chipfirimg-game) . . , – , – .  

, . «» «» , , , , . 
 
1.1. 1.1.1. , 
[6, 59, 60], c 
[9, 10, 16–24, 44, 50, 51, 57] (, , ). , . , 
, , , , , . , , – , (, ), [46, 48, 54, 56].  
, , . (– ), [92], 
, [56, 65]. 
 
[59]. [6, 65]. . G(V, E) – ; V – , ⏐V⏐= n; E ⊆ V ×V – , 
e = (u, v); ⏐⏐= m.  
Hf(e) = f(u, v), u, v ∈ V. 
f(e) v .  

div f(v) = )
,
(
)
,
(
v
u
v
u
f
− )
,
(
)
,
(
u
v
u
v
f
. 

 
, : 
 
∈V
v
v
f
)
(
div
= 0. 

 
– s-t-(1-1-) 
–(s-t-) : . .  
f(e) . . 
1. : s () t (). ; div f(v) = 0.  
2. f() : 
 
0 ≤ f() ≤ ();  
 
() .  
. 1 , div f(t) = −div f(s). 
M(f) = div f(t) = −div f(s) .  
div f(t) = div f(s) = 0, . 
vj div f(vj) = 0 , =

n

i
ijf
1
= =

n

i
ji
f
1
 

 
– : 
M(λf + μg) = λM(f )+ μM(g). 
 
– ϕL ϕC . . 

. f : 
 
f = L
ϕ + C
ϕ . 
 
= (X, Y) G , s ∈ X, t ∈ Y.  
U+(A) – , X Y; U−(A) – , Y X.  
c(A) = +
∈U
e
e
c
)
(
 – .  

div f(A) = ∈X
v
v
f
)
(
div
 – f .  

, M(f): div f(A) = M(f).  
M(f) = div f(A) = +
∈U
e
e
f
)
(
− −
∈U
e
e
f
)
(
 ≤ +
∈U
e
e
c
)
(
 = c(A), 

 
.. .  
s t – . 
–.  
1. ∈ () – , ().  
2.  : M(f) = 
A
min ().  

–. 
1.1. . 1.1. 
, , . 
() –, 17 

. 
 

 
. 1.1. . k s1, …, sk l t1, …, tl. . 
(k-l-) 1-1-: – s t (. 1.2). 
 

 

. 1.2. k-l-1-1-2 

1 

4 
c 

t 

2 

 3 
3 
s 

a 

b 

 
 
 
 
s1 

s2 

sk

t1

t2

tl

. . . 
.. . 

t
s