, . , , , . 12 . 12 ; , E:
- E F , [E], B, D.
- B: B F A [E, B].
- D: D F C [E, D].
- C: C F A [E, D, C]
A? , , . . , , , , . , , ( , ). , E B, A . .

,
- .
- , .
- , .
- , .
. , . , . .
, .
:
- E F B [E] 100.
- B F A [E, B] 100.
- E F D [E] 100.
- D F C [E, D] 100.
- C F A [E, D, C] 100.
A , , , , , , . A [E, B]. A , , C, C , 100, [E, B, A], [E, D, C]. , C . , , . , C, F . , , :
- E F B [E] 100.
- B F A [E, B] 100.
- E F D [E] 50.
- D F C [E, D] 50.
- C F A [E, D, C] 50.
A : 100, 50.
:
- A , [E, B], C
- C , [E, B, A], D.
- D , [E, B, A, C], E.
- E , E .
, () , .
, , , , , . , , , , , ( ), . , - , . ?
, , ( ) , - , , P. , P, , () . NP- , NP-, , . , .
NP-complete, , , , , , .
, , . , , , , , , jitter , . . , , , .
, , (QoS) , . , , (LFA / rLFA). , :
, ( ), (, )?
, (, , ) .
- , , () (). :
- ; .
- , - .
. 13 , .

A X F:
- [X, A, B, E, F] [X, C, F]
- [X, A, B, F] [X, C, F]
B G L: [G, K, L] [G, H, L]. Z , . F G , . [F, G] . , 13, X Z.
1974 . , , SPF- . SPF , , SPT, SPF . , , , SPT. 14-18.
14 SPF SPT. . , SPT , , . F X, , .

( ) SPT , ( ), SPT, . . 14 , - .
15.
15 ; , SPT ( , ), , , , SPT (, , ), . , ; . :
- u, v. , .
- v u v.
- u.

s: d[sp](u,v) = d(u,v) ? d(s,v) + d(s,u)
, 0, , [B, E]:
- B - u, E - v, A - s
- d(u,v) = 2, d(s,v) = 3, d(s,u) = 1
- 2 ? 3 + 1 = 0
, , ( ) . 15:
[B, A] ( [A, B] ):
- B - u, A - v, A - s
- d(u,v) = 0, d(s,v) = 0, d(s,u) = 1
- 0 ? 0 + 1 = 1
[E,B]:
- E u, B v, A - s
- d(u,v) = 2, d(s,v) = 1, d(s,u) = 3
- 2 ? 1 + 3 = 4
[C,A]:
- C u, A v, A s
- d(u,v) = 2, d(s,v) = 0, d(s,u) = 2
- 2 ? 0 + 2 = 4
[F,D]:
- F u, D v, A s
- d(u,v) = 1, d(s,v) = 4, d(s,u) = 5
- 1 ? 4 + 5 = 2
[D,B]:
- D u, B v, A s
- d(u,v) = 1, d(s,v) = 1, d(s,u) = 2
- 1 ? 1 + 2 = 2
, 16, , , , SPT ( Z), () , SPF , SPT .
SPT, X Z [A,B,D,F]. , ( ), , , . [A, B,D,F] . , [A,B] A B, B A. - SPF , , . 17.
17 , . [B,D], . X Z:
- [A,B,D,F]
- [A,C,D,B,E,F]


, , , , , ; : [A->B, B->E, E->F, A->C, C->D, D->F]
- , [B-> D] [D-> B]. : [A, B, E, F] [A, C, D, F].
, , , .
(Maximally Redundant Trees-MRT). MRT - Depth First Search (DFS), DFS. 18 .

18 . - , DFS. , DFS, , , :
01 main { 02 dfs_number = 1 03 root.number = dfs_number 04 recurse_dfs(root) 05 } 06 recurse_dfs(current) { 07 for each neighbor of current { 08 child = left most neighbor (not visited) 09 if child.number == 0 { 10 dfs_number++ 11 child.number = dfs_number 12 if child.children > 0 { 13 recurse_dfs(child) 14 } 15 } 16 } 17 }
- , , . 18:
- recurse_dfs A root.
- recurse_dfs, A B.
- B , if 09 .
- B DFS ( 11).
- B ( 12), recurse_dfs B .
- ( ) recurse_dfs, B, E.
- E DFS, if 09 .
- E DFS (3)
- E , .
- F B, , .
- F , if 09 .
- F DFS (4).
- B , for 07 , recurse_dfs .
- recurse_dfs - , 14. A.
- C - A, , C.
18 :
- A , D, [A, C,G,D].
- D DFS, A, [D, A].
- .
, DFS: , , , . , MRT . DFS , . - , ( Minimum Spanning Tree MST), DFS. , MRT , , . 19 .
MRT ( SPF ). A, [A, B, C, D]. , , . [A, D, C, B] , , . .
. , [A, D, F, E, B], - [A, B, E, F, D]. : , - ? DFS.

, - . . DFS , , , .
, , DFS. , , . , B , C, [A, B, C, D] . , B C, , B C, . . , , MRT .
( ) . - . , . , , . , .
. . , , , , - , . , , . , .
, , - .
:
- , , , - , , .
- . , . .
- , . , , ( ) , .