I n te r n ati o n al   Jo u r n al   o El e c tr i c a l   an d   C o m p u te r   En gi n e e r i n g   (I JEC E )   V o l .   10 ,   N o .   2 A p r i l   2020 ,   p p.   1632 ~ 164 0   IS S N :   2088 - 8708 D O I :   10. 1 1591 / i j e c e . v 10 i 2 . pp1632 - 1640             1632       Jou r n al   h o m e pa ge ht t p: / / i j e c e . i ae s c or e . c om / i nd e x . php / IJ E CE   E x t e n d e d   n e t w o r k   a n d   a l g o r i t h m   f i n d i n g   m a x i m a l   f l o w s       Tr an   N go c   V i e t 1 ,   L e   H o n D u n g 2   1 F a c ul t y   of   I n f o r m a t i o T e c hno l o gy ,   V a L a ng   U ni v e r s i t y ,   H C M   C i t y ,   V i e t n a m     2 F a c ul t y   of   I n f o r m a t i o T e c hno l o gy ,   C e nt r a l   T r a n s po r t   C o l l e g e   V ,   D a na ng   C i t y ,   V i e t n a m       A r ti c l e   I n fo     A B S TR A C T     Ar t i c l e   h i s t or y :   R e c e i v e d   A pr   30 ,   201 9   R e v i s e O c t   8 ,   20 19   A c c e pt e O c t   17 ,   2 019       G r a ph   i s   a   po w e r f u l   m a t h e m a t i c a l   t o o l   a pp l i e d   i n   m a ny   f i e l d s   a s   t r a ns po r t a t i o n,   c om m uni c a t i o n,   i nf o r m a t i c s ,   e c o no m y ,   i o r di na r y   g r a ph   t h e   w e i g ht s   o f   e dg e a nd  v e r t e xe s   a r e   c o ns i d e r e d   i nd e pe nde n t l y   w he r e   t he   l e ng t o f   a   pa t h   i s   t he   s um   o f   w e i g ht s   o f   t h e   e dg e s   a n d   t h e   v e r t e xe s   o n   t h i s   p a t h.   H o w e v e r ,   i n   m a ny   pr a c t i c a l   p r o bl e m s ,   w e i g ht s   a t   a   v e r t e a r e   no t   t h e   s a m e   f o r   a l l   p a t hs   pa s s i ng   t hi s   v e r t e x,   bu t   d e pe n d   o c o m i ng   a nd  l e a v i ng   e dg e s .   T he   pa pe r   d e v e l o ps   a   m o de l   o f   e x t e n de d   n e t w o r k   t ha t   c a n   b e   a pp l i e d   t o   m o de l l i ng   m a n y   pr a c t i c a l   pr o bl e m s   m o r e   e xa c t l y   a nd  e f f e c t i v e l y .   T he   m a i c o nt r i bu t i o o f   t h i s   pa pe r   i s   a l g o r i t hm   f i nd i ng   m a xi m a l   f l o w s   o e xt e nde ne t w o r ks .   Ke y w or d s :   A l go r i t h m   E xt e n de n e t w o r k   F l ow   G ra p h   M a xi m a l   f l o w   C opy r i gh t   ©   2020   I n s t i t ut e   o f   A dv anc e E ng i ne e r i ng   and   S c i e nc e   A l l   r i gh t s   r e s e r v e d .   Cor r e s pon di n g   Au t h or :   T r a N go c   V i e t   F a c ul t y   of   In f o r m a t i o n   T e c hn o l o g y ,     V a n   L a ng  U ni v e r s i t y ,     80/ 6 8   D uo n g   Q ua ng  H a m   S t r e e t ,   W a r d   5 ,   G o   V a D i s t r i c t ,   H o   C h i   M i nh  Ci t y ,   V i e t n a m .   E m a i l :   t ra nn go c v i e t @ v a n l a n gu ni . e du . v n       1.   I N TR O D U C TI O N     G ra p i s   a   po w e r f ul   m a t h e m a t i c a l   t o o l   a ppl i e i m a n y   f i e l ds   a s   t r a n s po r t a t i o n ,   c o m m u ni c a t i o n,   i n f o r m a t i c s ,   e c o n o m y ,   i n   o r d i na r y   gr a p h   t h e   w e i gh t s   o f   e dge s   a n v e r t e xe s   a r e   c o n s i de r e i n de pe nde nt l y   w h e r e   t h e   l e n g t o f   a   pa t i s   s i m pl y   t h e   s u m   o f   w e i gh t s   o f   t h e   e dge s   a nd   t h e   v e r t e xe s   o t hi s   pa t h.   H ow e v e r ,   i m a n y   pra c t i c a l   p r o b l e m s ,   w e i ght s   a t   a   v e rt e a r e   n o t   t h e   s a m e   f o r   a l l   p a t h s   pa s s i n g   t hi s   v e r t e x ,   b ut   de pe n d   o n   c o m i n g   a n d   l e a v i n g   e dge s .   T h e r e f o r e ,   a   m o r e   ge n e r a l   t y pe   of   w e i g ht e g ra p h s ,   c a l l e e xt e n de d   w e i ght e g ra p h,   i s   de f i n e i n   t h i s   w o r k.   T h e   pa pe r   de v e l o ps   a   m o de l   o f   e xt e n de n e t w o r t ha t   c a b e   a ppl i e t o   m o de l l i ng  m a n y   pra c t i c a l   p r o b l e m s   m o r e   e xa c t l y   a n d   e ff e c t i v e l y .   B a s e o n   t h e   r e s ul t s   o f   t h e   s t udy   of   t h e   p r o b l e m   r e g a r di ng  f i n di ng  t h e   m a x i m um   f l ow   [1 4,   6 - 8,   10 - 1 8,   20 - 2 1,   23 - 24 ]   a n d   e xt e n de g ra p h s   [ 2 - 3 ,   5,   9 ,   19,   2 2,   25 - 26 ]   t h e   m a i n   c o nt r i b ut i o o f   t hi s   p a pe r   i s   t h e   r e v i s e F o r d - F u l ke r s o a l go ri t hm   f i ndi n g   m a x i m a l   f l o w s   o n   e x t e n de d   n e t w o r ks .         2.   EX TEN D ED   N ET WO R K   A   n e t w o r i s   g ra p o f   t h e   t ra f f i c   G   =   (V ,   E ) ,   c i r c l e s   V   a n d   r o a ds   E .   R o a ds   c a b e   c l a s s i f i e a s   e i t h e r   di r e c t i o n   o r   n o n - di r e c t i o n .   T h e r e   a r e   m a n y   s o r t s   o f   m e a n s   o f   t r a n s po rt a t i o n   o t h e   n e t w o r k.   T h e   n o n - di r e c t i o s h o w s   t w o - w a y   r o a ds   w h i l e   t h e   d i r e c t i o s h o w s   o n e - w a y   r o a ds .   G i v e a   g r o up  o f   t h e   f un c t i o n s   o t h e   n e t w o r a s   f o l l ow s :   T h e   f un c t i o o f   t h e   r o ut e   c i r c ul a t i o po s s i b i l i t y   :     , ( )   t h e   r o ut e   c i rc ul a t i o n   po s s i b i l i t y   .   T h e   f un c t i o o f   t h e   c i r c l e   c i r c ul a t i o po s s i b i l i t y   :     , ( ) t h e   c i r c l e   c i rc ul a t i o n   po s s i b i l i t y   .       =   ( , , , ) :   e xt e n de n e t w o r k             (1)   Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J   E l e c   &   Co m E n g     IS S N :   2088 - 8708       E x t e nd e d   ne t w or k   and  a l gor i t hm   f i nd i ng   m ax i m al   f l ow s   ( T r a Ngo c   V i e t )   1633   3.   F LO O F   T H E   EX TEN D ED   N ETW O R K   G i v e n   a e xt e n de n e t w o r   =   ( , , , ) a   s o u r c e   po i nt   s   a n d   a   s i nk  po i nt   t .   S e t     {   ( , )   |   ( , )   }   i s   c a l l e t h e   f l o w   of   n e t w o r G   i f   t h e   r e qu i r e m e n t s   a r e   m e t :   a.   0       ( , )         ( , )     ( , )   b.   A n y   v a l ue   o f   p o i n t   i s   r e f e r r i ng  t o   n e i t h e a   s o ur s e   po i n t   n o a   s i nk  po i nt     E r v r v f ) , ( ,     E v r v r f ) , ( ,               (2)     c.   A n y   v a l ue   o f   p o i n t   i s   r e f e r r i ng  t o   n e i t h e a   s o ur s e   po i n t   n o a   s i nk  po i nt         E r v r v f ) , ( ,   ( )                   (3)       E xp r e s s i o n :   E v a v a f F v ) , ( , ) (   ,   i s   c a l l e d   t h e   v a l ue   o f   f l ow   F       (4)               3. 1 .    Th e   m ax i mu m   p r o b l e m     G i v e n   a e xt e nde n e t w o r k   = ( , , , ) ,   a   s o ur c e   po i nt   s   a n d   a   s i nk   po i nt   t .   T h e   t a s k   r e qu i r e by   t h e   p r o b l e m   i s   f i n di ng  t h e   f l ow   w h i c h a s   a   m a xi m u m   v a l ue .   T h e   f l ow   v a l ue   i s   l i m i t e b y   t h e   t o t a l   a m o u n t   of   t h e   c i r c ul a t i o po s s i b i l i t y   o n   t h e   r o a ds   s t a r t i n g   f r o m   s o ur c e   po i n t s .   A s   a   r e s ul t   o f   t h i s ,   t h e r e   c o ul b e   a   c o n f i r m a t i o n   o n   t h e   f o l l ow i n g   t h e o r e m .               3. 2 .     Th e o r e m   1       G i v e n   a e xt e n de n e t w o r = ( , , , ) ,   a   s o ur c e   po i nt   s   a nd  a   s i n po i nt   t ,   t h e n   e x i s t   i s   t h e   m a x i m a l   f l ow   [1].       4.   TH E   A LG O R I TH M   F I N D I N G   M A X I M A F L O WS   4. 1 .     S o u r c e   to w ar d   s i n k   al go r i th m     In p ut :   G i v e a e xt e n de n e t w o r = ( , , , ) ,   a   s o ur c e   po i nt   s   a nd  a   s i nk  po i n t   t .   T h e   po i n t s   i n   g ra p G   a r e   a rr a nge i a   c e rt a i o r de r   [ 3].   O ut put :   M a xi m a l   f l o w   = { ( , )   |   ( , ) } .   (1)  S t a r t :   T h e   de pa rt u r e   f l o w :   ( , ) 0 , ( , ) .   P o i n t s   f r o m   t h e   s o ur c e   po i nt s   w i l l   g ra du a l l y   b e   l a b e l l e L f o r   t h e   f i r s t   t i m e   i n c l ud i n g   5   c o m po n e n t s :   F o r m   f o r w a r d   l a b e l     1 ( )   =   [ ,  1 ( ) , 1 ( ) , 1 ( ) ,  1 ( ) ]   a n d   c a b e   l a b e l l e ( )   f o r   t h e   s e c o n t i m e   2 ( ) =   [ ,  2 ( ) , 2 ( ) , 2 ( ) ,  2 ( ) ] .     P ut   l a b e l i n ( )   f o r   s o ur c e   po i n t     L 1 ( s ) =   [ , , , , 1 ]     T h e   s e t   S   c o m pri s e s   t h e   po i n t s   w h i c ha v e   a l r e a dy   be e n   l a b e l l e ( )   b ut   a r e   n o t   us e d   t o   l a b e l   ( ) S’   i s   t h e   po i n t   s e t   l a b e l l e ( )   b a s e o n   t h e   po i nt s   o f   t h e   s e t   S   B e gi n         { } ,           (2)   F o r w a r l a b e l   ge n e r a t e :   (2. 1)   C h o o s e   f o r w a r l a b e l   po i n t :          :   Ch o o s e   t h e   po i nt       o f   a   m i n i m u m   v a l ue .   R e m o ve   t h e   u   f r o m   t h e   s e t   S ,   : =   \   { } .   A s s um i n g   t ha t   t h e   f o r w a rd  l a b e l   of  u   i s   [ ,  ( ) , ( ) , ( ) , ( ) ] , = 1      2 .   A   i s   t h e   s e t   o f   t h e   po i nt s   w hi c h   a r e   n o t   f o r w a r d   l a b e l   t i m e   a nd   a dj a c e nt   t o   t h e   f o r w a r d   l a b e l   po i n t   u   S t e (2. 2).     Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   Int   J   E l e c   &   Co m E n g ,   V o l .   10 ,   N o .   2 A p ri l   2020   :     1632   -   1640   1634      =          :     , : = .   R e t urn  t o   s t e (2. 1 ).      =        =   :   T h e   f l o w   F   i s   t h e   m a xi m u m .   E nd.     (2. 2 . F o r w a r d   l a b e l   t h e   po i n t s   w h i c a r e   n o t   f o r w a r l a b e l   a n d   a r e   a dj a c e nt   t o   t h e   f o r w a r d   l a b e l   po i n t s     Ca s e     =     R e t u rn   t o   S t e (2 . 1) .   Ca s e         C h o o s e       o f   a   m i ni m um   v a l ue .   R e m o ve   t h e   v   f r o m   t h e   s e t   , =   \   { } .   A s s i gn  f o r w a r d   l a b e l e po i n t   v :       If   1 ) ( ), , ( ) , ( , ) , ( u b i t v u c v u f E v u i E   put   f o r w a r d   l a b e l   po i n t   v      ( ) =   ;   ( ) : = { ( ) , ( , ) ( , ) } ,    ( ) = 0 ,   ( ) : = { ( ) , ( , ) ( , ) , ( ) } ,    ( )   >   0 ;   ( ) =   ( ) E v i v i f ) , ( , ;    ( ) : = 1 ,    ( )   >   0 ,    ( ) : = 0 ,    ( )   =   0 .       If     , ) , ( E u v ( , )   >   0 ,     put   f o r w a r d   l a b e l   po i nt   v      ( ) =   ;   ( ) : = { ( ) , ( , ) } ,   ( ) =   ( )   E v i v i f ) , ( , ;    ( ) : = 1 .     If   v   i s   n o t   f o r w a r l a b e l ,   t h e r e t u rn  t o   S t e ( 2. 2 ) .   If   v   i s   f o r w a r l a b e l   a n d   v   i s   b a c kw a r d   l a b e l ,   t h e n   m a ki ng  a dj us t m e n t s   i n   i n c r e a s e   o f   t h e   f l ow .     S t e (2. 3) .   If   v   i s   f o r w a r l a b e l   a nd  v   i s   n o t   b a c kw a r d   l a b e l ,   t h e a d v   t o   S’   =       { } ,   a n d   r e t u rn  t o   S t e (2. 2 ).     (3)  M a ki n g   a dj us t m e n t s   i i n c r e a s e   o f   t h e   f l o w :   S uppo s e   s   i s   f o r w a r l a b e l   [ ,  ( ) , ( ) , ( ) ,  ( ) ] :   (3. 1)   A dj us t m e n t   m a de   f r o m   v   b a c t o   s   a c c o r di n g   t o   f o r w a rd  l a b e l   (3. 1 . 1)   S t a rt     =   , =    1 ( ) , =   1 ( ) .       (3. 1 . 2 . M a ki ng  a dj us t m e n t s     ( i C a s e   ( , )   t h e   r o a s e c t i o w h o s e   di r e c t i o n   ru n s   f r o m   x   t o   y   put     ( , ) =   ( , )   +   . .     ( ii )   Ca s e   ( , )   t h e   r o a s e c t i o w h o s e   di r e c t i o n   ru n s   f r o m   y   t o   x :       put     ( , ) =   ( , )   . .     ( iii C a s e   ( , )   n o n - d i r e c t i o n   r o a ds :   If     ( , )     0        ( , )   =   0 ,   t h e n       put    f ( x , y : =   f ( x , y )   +   .     If     ( , )   >   0 ,   t h e n       put     ( , ) =   ( , )   .     (3. 1 . 3)   M o v i n     (i C a s e     =   . .   S t e p   (3. 2).             (i i )       ,    =        : = ,   i s   t h e   s e c o n c o m po n e nt   o f   t h e   f o r w a r l a b e l e po i n t   x.   T h e n   r e t u r t o   S t e (3 . 1. 2).   (3. 2 . R e m o v e   a l l   t h e   l a b e l s   of   t h e   n e t w o r po i n t s ,   e xc e pt   f o r   t h e   s o u r c e   po i n t   s .   R e t urn  t o   S t e (2) .       Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J   E l e c   &   Co m E n g     IS S N :   2088 - 8708       E x t e nd e d   ne t w or k   and  a l gor i t hm   f i nd i ng   m ax i m al   f l ow s   ( T r a Ngo c   V i e t )   1635   4. 2 .     S i n k   to w ar d   s o u r c e   al go r i th m   In p ut :   G i v e a e xt e nde n e t w o r = ( , , , ) ,   a   s o ur c e   po i n t   s   a n d   a   s i n k   po i nt   t .   T h e   po i nt s   i gra p G   a r e   a rra nge i a   c e rt a i n   o r de [3] .   O ut put :   M a xi m a l   f l o w   = { ( , )   |   ( , ) } .   (1)  S t a r t :   T h e   de pa rt u r e   f l o w :   ( , ) : =   0 , ( , ) .   P o i n t s   f r o m   t h e   s i n k   po i n t s   w i l l   g r a du a l l y   be   l a b e l l e L f o r   t h e   f i r s t   t i m e   i n c l ud i n g   c o m po n e n t s :   F o r m   b a c kw a r d   l a b e l       L1 ( v )   =   [ ,   pr e v 1 ( v ),   c 1 ( v ),   d 1 ( v ) ,   b i t 1 ( v )]   a n d   c a n   b e   l a b e l   ) (   f o r   t h e   s e c o n t i m e     L2 ( v )   ( v )   =   [ ,   pr e v 2 ( v ) ,   c 2 ( v ) ,   d 2 ( v ),   bi t 2 ( v )]     P ut   l a b e l i n g   ) (   f o r   s i nk  po i n t :       , 1 ] , , , [   ( t ) L   1   t h e   s e t   T c o m pri s e s   t h e   po i nt s   w hi c h   ha v e   a l r e a dy   be e n   l a b e l l e ) (   b ut   a r e   n o t   us e t o   l a b e l   ) ( T’   i s   t h e   po i nt   s e t   l a b e l l e ) (    b a s e o n   t h e   po i n t s   o f   t h e   s e t   T .   B e gi n       (2)  B a c kw a r d   l a b e l   ge n e r a t e :   (2. 1)   C h o o s e   b a c k w a r l a b e l   po i n t :   Ca s e   T   :   C h o o s e   t h e   po i nt         o f   a   m i ni m u m   v a l ue .   R e m ov e   t h e   v   f r o m   t h e   s e t   T ,   : =   \   { } .   A s s um i ng  t h a t   t h e   b a c kw a r d   l a b e l   o f   v   is     [ ,  ( ) , ( ) , ( ) ,  ( ) ] , = 1      2 .     B   i s   t h e   s e t   o f   t h e   po i nt s   w h i c a r e   n o t   b a c kw a r l a b e l   t i m e   a n d   a dj a c e n t   t o   t h e   b a c kw a r l a b e l   po i n t   v   S t e (2. 2).        T     ' T :     : '    , ' : T T T .   R e t urn  t o   s t e (2. 1 ).        =      = :   T h e   f l ow   F   i s   t h e   m a x i m u m .   E n d .     (2. 2)   B a c kw a r l a b e l   t h e   po i n t s   w h i c h   a r e   n o t   b a c kw a r d   l a b e l   a n a r e   a dj a c e n t   t o   t h e   b a c kw a r d   l a b e l   po i n t s   v   Ca s e   B   :   R e t u rn   t o   S t e (2 . 1) .   Ca s e   B :   C h o o s e         o f   a   m i n i m u m   v a l ue .   R e m o ve   t h e   t   f r o m   t h e   s e t   B ,   t B B \ :     A s s i gn  b a c kw a r d   l a b e l e po i n t   t :       If   1 ) ( ), , ( ) , ( , ) , ( v b i t v t c v t f E v t i E   put   b a c kw a r l a b e l   po i n t   t     pr e v _j   (t ) =   v ;    ( ) =   ;   ( ) : = { ( ) , ( , )     ( , ) } ,    ( ) = 0 ,   ( ) : = { ( ) , ( , )     ( , ) , ( ) } ,    ( )   >   0 ;   ( ) ( ) ( , ) ( , ) .      ( ) : = 1 ,    ( )   >   0 ,    ( ) : = 0 ,    ( )   =   0 .       If   0 ) , (    , ) , ( t v f E t v ,   pu t   b a c kw a r d   l a b e l   po i n t   t      ( ) =   ;   ( ) : = { ( ) , ( , ) } ,   ( ) ( ) ( , ) ( , ) ;  ( ) 1 .   If   t   i s   n o t   b a c kw a r d   l a b e l ,   t h e r e t u rn  t o   S t e p   (2. 2).   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   Int   J   E l e c   &   Co m E n g ,   V o l .   10 ,   N o .   2 A p ri l   2020   :     1632   -   1640   16 36   If   t   i s   b a c kw a r d   l a b e l   a n d   t   i s   f o r w a r d   l a b e l ,   t h e m a k i n g   a dj us t m e n t s   i i n c r e a s e   o f   t h e   f l o w .     S t e (3) .     If   t   i s   b a c kw a r l a b e l   a nd  t   i s   n o t   f o r w a r l a b e l ,   t h e n   a dd   t   t o   T’   T’ :=  T’   { t } ,   a n d   r e t u rn  t o   S t e (2 . 2) .     (3)  M a ki n g   a dj us t m e n t s   i i n c r e a s e   o f   t h e   f l o w :   S uppo s e   t   i s   b a c kw a r d   l a b e l   [ ,  ( ) , ( ) , ( ) ,  ( ) ]   (3. 1)   A dj us t m e n t   m a de   f r o m   v   t o   t   a c c o r di n g   t o   b a c kw a r l a b e l   (3. 1 . 1)   S t a rt         =   , =    1 ( ) , =   1 ( ) .     (3. 1 . 2)   M a k i n g   a dj us t m e nt s   (i C a s e   ( , )   t h e   r o a d   s e c t i o n   w h o s e   di r e c t i o r u n s   f r o m   x   t o   y   put   ( , ) =   ( , )   +   .   (i i )   Ca s e   ( , )   t h e   r o a s e c t i o w h o s e   di r e c t i o n   ru n s   f r o m   y   t o   x   put   ( , ) : =   ( , )   .   (i i i C a s e   ( , )   n o n - d i r e c t i o n   r o a ds :               If     ( , )   0        ( , ) =   0   t h e n     put   ( , ) =   ( , )   +   .               If     ( , )   >   0   t h e   put   ( , ) =   ( , )   .       (3. 1 . 3)   M o v i n g     (i C a s e     =   .   S t e (3 . 2) .     (i i )   Ca s e       ,    =        : = ,   i s   t h e   s e c o n c o m po n e n t   o f   t h e   b a c kw a r d   l a b e l e po i n t   x T h e r e t u rn  t o   s t e (3 . 1. 2).     (3. 2)   R e m ov e   a l l   t h e   l a b e l s   o f   t h e   n e t w o r po i nt s ,   e xc e pt   f o r   t h e   s i n k   po i n t   t .   R e t u rn  t o   S t e ( 2).     4. 3 .     Th e o r e m   2     If   t h e   v a l ue   o f   t h e   r o ut e   c i r c ul a t i o po s s i b i l i t y   a n d   t h e   c i r c l e   c i r c ul a t i o po s s i b i l i t y   a r e   i nt e ge r s ,   t h e a f t e r   a   l i m i t e n u m b e r   o f   s t e ps ,   t h e   p r o c e s s i n o f   t h e   m a xi m um   n e t w o r p r o b l e m   w i l l   e n d.     P r oof     A c c o r di n g   t o   t h e o r e m   1,   a f t e r   e a c t i m e   o f   m a ki ng  a dj us t m e nt   o f   t h e   f l o w ,   t h e   f l o w   w i l l   b e   i n c r e a s e w i t h   c e rt a i n   u ni t s   (due   t o   c E   i s   a   w h o l e   num b e r,   c V    i s   a   w ho l e   n um b e r,   a nd  δ   i s ,   t h e r e f o r e ,   a   po s i t i v e   w h o l e   n u m b e r ).   O n   t h e   o t h e h a nd,   t h e   v a l ue   o f   t h e   f l ow   i s   l i m i t e a b ov e   by   t h e   t o t a l   a m o unt   o f   t h e   c i r c ul a t i o po s s i b i l i t y   a t   r o a ds   l e a v i n t h e   s o ur c e   po i nt s .   S o ,   a f t e r   a   l i m i t e n u m b e r   o f   s t e ps ,   t h e   p r o c e s s i n o f   t h e   m a x i m u m   n e t w o r p r o b l e m   w i l l   e n d .     4. 4 .     Th e o r e m   3     G i v e n   a   =   { ( , )   |   ( , ) }   i s   t h e   f l o w   o n   e xt e n de d   n e t w o r G ,   a   s o ur c e   po i nt   s   a n d   a   s i nk  po i n t   t :     E t x E x s t x f x s f ) , ( ) , ( , ,               (5)     P r oof     T h e   po i n t s   o f   t h e   s e t   V .   If     x,   y   i s   n o t   p r e v i o us ,   a s s i g 0 ) , ( y x f        V y V x V y V x x y f y x f ) , ( ) , (   0 ) , ( ) , ( V y V x V x x y f y x f   E t x E x s E t x E x s t x f x s f t x f x s f ) , ( ) , ( ) , ( ) , ( , ,           0 , , .   Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J   E l e c   &   Co m E n g     IS S N :   2088 - 8708       E x t e nd e d   ne t w or k   and  a l gor i t hm   f i nd i ng   m ax i m al   f l ow s   ( T r a Ngo c   V i e t )   1637   4. 5 .       Th e   c o m p l e x i ty  o th e   al go r i th m   It   i s   a s s um e t ha t   t h e   r o a c i r c ul a t i o n   po s s i b i l i t y   a n t h e   po i n t   c i r c ul a t i o n   po s s i b i l i t y   a r e   w h o l e   i n t e ge r .   A f t e r   e a c r o und   s t e p,   t o   f i n d   t h e   r o a ds   t o   i n c r e a s e   t h e   a m o unt   o f   c i r c ul a t i o o t h e   f l o w ,   w e   h a v e   t o   a p p r o ve   t o   pa s s   E r o a ds   i m a xi m u m ,   a nd  i o r de r   t o   a dj us t   t h e   f l ow   w e   h a v e   t o   a pp r o v e   t o   pa s s   2 . V   r o a ds ,   i m a x i m u m .       A s   a   r e s ul t ,   t h e   c o m pl e xi t y   of   e a c h   t i m e   o f   i n c r e a s i n g   t h e   f l ow   i s   O ( E     +   2 . V )     M a r v i s   t h e   v a l ue   o f   t h e   m a xi m u m   f l o w .   S o   t h e   c o m pl e xi t y   of   t h e   a l go r i t h m   i s                                     O ( ( E     +   2 . V ) )                 (6)       5.   R ES U LT  O F   TH EX P ER I M EN T   5. 1 .     Ex am p l e   1     G i v e n   a e xt e n de d   n e t w o r g ra p F i gu r e   1 .   T h e   n e t w o r ha s   s i c i r c l e s ,   s i x   d i r e c t i o r o a ds   a n d   t hr e e   n o n - di r e c t i o n   r o a ds .   T h e   r o a c i r c u l a t i o po s s i b i l i t y   c E   a n d   t h e   c i r c l e   c i r c ul a t i o po s s i b i l i t y   c V .   T h e   s o ur c e   po i n t   i s   l ,   t h e   s i nk  po i nt   i s   6 .           F i gu r e   1 .   E xt e n d e n e t w o r k       R e s ul t   of   t h e   f i r s t   f o r w a r d   l a b e l :     S o ur c e   po i n t   i s   1 :   f o r w a r d   l a b e l     [ ,   1]   P o i n t   2 :   f o r w a r d   l a b e l     [ ,   1 ,   1 0,   10 ,   1 ]     P o i n t   3 :   f o r w a r d   l a b e l     [ ,   1 ,   9 ,   9,   1]   P o i n t   4 :   f o r w a r d   l a b e l     [ ,   3 ,   7 ,   10 ,   1]   P o i n t   5 :   f o r w a r d   l a b e l   [ ,   2,   7,   9 ,   1]   P o i n t   6 :   f o r w a r d   l a b e l   [ ,   4,   7,   ,   1]     R e s ul t   of   t h e   f l ow   i n c r e a s i ng  a dj us t m e n t   i n   F i gu r e   2   a nd  t h e   v a l ue   o f   t h e   i n c r e a s e   v ( F )   =   7 .           F i gu r e   2 .     T h e   v a l ue   o f   t h e   i n c r e a s e   v (F =   7     Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   Int   J   E l e c   &   Co m E n g ,   V o l .   10 ,   N o .   2 A p ri l   2020   :     1632   -   1640   1638   R e s ul t   of   t h e   s e c o n f o r w a r l a b e l :   S o ur c e   po i n t   i s   1 :   f o r w a r d   l a b e l     [ ,   1]   P o i n t   2 :   f o r w a r d   l a b e l     [ ,   1 ,   1 0,   10 ,   1 ]   P o i n t   3 :   f o r w a r d   l a b e l     [ ,   1 ,   2 ,   2,   1]   P o i n t   4   P o i n t   5 :   f o r w a r d   l a b e l   [ ,   2,   7,   9 ,   1]     P o i n t   6 :   f o r w a r d   l a b e l   [ ,   5,   7,   ,   1]   R e s ul t   of   t h e   f l ow   i n c r e a s i ng  a dj us t m e n t   i F i gu r e   3   a nd   t h e   v a l ue   o f   t h e   i n c r e a s e   v ( F )   =   14 .           F i g ur e   3.   T h e   v a l ue   o f   t h e   i n c r e a s e   v ( F =   14       R e s ul t   of   t h i r d   f o r w a r d   l a b e l :   S o ur c e   po i n t   i s   1 :   f o r w a r d   l a b e l     [ ,   1]   P o i n t   2 :   f o r w a r d   l a b e l     [ ,   1 ,   3 ,   3,   1]   P o i n t   3 :   f o r w a r d   l a b e l     [ ,   1 ,   2 ,   2,   1] ,   [ ,   2,   2 ,   2,   1]   P o i n t   4   P o i n t   5 :   f o r w a r d   l a b e l   [ ,   3,   2,   2 ,   1]   P o i n t   6 :   f o r w a r d   l a b e l   [ ,   5,   2,   ,   1]     R e s ul t   of   t h e   f l ow   i n c r e a s i ng  a dj us t m e n t   i F i gu r e   4   a nd  t h e   v a l ue   o f   t h e   i n c r e a s e   v ( F )   =   16 .             F i gu r e   4 .   T h e   v a l ue   o f   t h e   i n c r e a s e   v ( F =   16       T h i s   i s   t h e   m a x i m u m   f l ow ,   b e c a us e   i n   t h e   f o l l ow i n g   f o r w a r l a b e l   i s   n o t   l a b e l l e   S i n po i nt   i s   6 .           Evaluation Warning : The document was created with Spire.PDF for Python.
Int   J   E l e c   &   Co m E n g     IS S N :   2088 - 8708       E x t e nd e d   ne t w or k   and  a l gor i t hm   f i nd i ng   m ax i m al   f l ow s   ( T r a Ngo c   V i e t )   1639   5 .2 .       Ex am p l e   2   R e s ul t   of   t h e   f i r s t   b a c kw a r d   l a b e l :   S i nk  po i nt   i s   6 :   b a c kw a r d   l a b e l   ] 1    ,    ,    ,    , [   P o i n t   5:   b a c kw a r l a b e l   ] 1    , 9    , 9    , 6    , [   Po i n t   4:   b a c kw a r l a b e l   ] 1    , 10    , 10    , 6    , [   P o i n t   3:   b a c kw a r l a b e l   ] 1    , 9    , 7    , 4    , [   P o i n t   2:   b a c kw a r l a b e l   ] 1    , 10    , 7    , 5    , [       P o i n t   1:   b a c kw a r l a b e l   ] 1    ,    , 7    , 3    , [   R e s ul t   of   t h e   f l ow   i n c r e a s i ng  a dj us t m e n t   a n d   t h e   v a l ue   o f   t h e   i n c r e a s e   v ( F )   =   7     R e s ul t   of   t h e   s e c o n b a c kw a r l a b e l :   S i nk  po i nt   i s   6 :   b a c kw a r d   l a b e l   ] 1    ,    ,    ,    , [   P o i n t   5:   b a c kw a r l a b e l   ] 1    , 9    , 9    , 6    , [   P o i n t   4:   b a c kw a r l a b e l   ] 1    , 3    , 5    , 5    , [   P o i n t   3:   b a c kw a r l a b e l   ] 1    , 2    , 6    , 5    , [   P o i n t   2:   b a c kw a r l a b e l   ] 1    , 10    , 7    , 5    , [   P o i n t   1:   b a c kw a r l a b e l   ] 1    ,    , 7    , 2    , [   R e s ul t   of   t h e   f l ow   i n c r e a s i ng  a dj us t m e n t   a n d   t h e   v a l ue   o f   t h e   i n c r e a s e   v ( F )   =   14     R e s ul t   of   t h i r d   b a c kw a r d   l a b e l :   S i nk  po i nt   i s   6 :   b a c kw a r d   l a b e l   ] 1    ,    ,    ,    , [   P o i n t   5:   b a c kw a r l a b e l   ] 1    , 2    , 2    , 6    , [   P o i n t   4:   b a c kw a r l a b e l   ] 1    , 3    , 3    , 6    , [   P o i n t   3:   b a c kw a r l a b e l   ] 1    , 2    , 2    , 5    , [   P o i n t   2:   b a c kw a r l a b e l   ] 1    , 3    , 2    , 3    , [   P o i n t   1:   b a c kw a r l a b e l   ] 1    ,    , 2    , 2    , [   R e s ul t   of   t h e   f l ow   i n c r e a s i ng  a dj us t m e n t   a n d   t h e   v a l ue   o f   t h e   i n c r e a s e   v ( F )   =   16     T h i s   i s   t h e   m a x i m u m   f l ow ,   b e c a us e   i n   t h e   f o l l ow i n g   b a c kw a rd  l a b e l   i s   n o t   l a b e l l e d - S o ur c e   po i n t   i s   1.       6.   C O N C LU S I O N     T h e   a r t i c l e   r e ga r d i n g   b ui l d i n g   a   m o de l   o f   a e xt e nde n e t w o r s o   t ha t   t h e   s t y l i z a t i o o f   pr a c t i c a l   pr o b l e m s   c a b e   a pp l i e d   m o r e   a c c ura t e l y   a n d   e f fe c t i ve l y .   N e xt ,   s o ur c e   t o w a r d   s i nk   a n d   s i n k   t o w a r d   s o ur c e   a l go ri t hm   f i n d i n m a x i m a l   f l ow s   a r e   b e i n b ui l t .   F i na l l y ,   a   c o n c r e t e   e xa m pl e   i s   p r e s e n t e t o   i l l us t ra t e   s o ur c e   t o w a r s i n k   a n s i n k   t o w a r d   s o ur c e   a l go r i t h m .                 A C K N O WL ED G E M EN TS     T h e   a ut h o w o ul l i ke   t o   t h a nk   t h e   M i ni s t r y   of   T e c hn o l o g y   -   H i g h e E duc a t i o a n d   P r e s i de n t ,   V a L a n g   U n i v e r s i t y   fo r   f i na n c i a l   s uppo rt   t o   t h i s   r e s e a r c h.       R EF ER EN C ES     [ 1]   T r a n   Q uo c   C hi e n ,   W e i g ht e S o ur c e - S i nk  A l t e r n a t i v e   A l g o r i t hm   t o   F i nd   M a xi m a l   F l o w ,   T he   U n i v e r s i t y   o f   D anan g - V i e t nam   J o ur na l   o f   S c i e nc e   and   T e c hno l og y ,   v o l .   3,   no .   26 ,   pp.   9 9 - 105,   2 008 .   [ 2]   T r a n   N g o c   V i e t ;   T r a n   Q uo c   C hi e n;   a nd   L e   M a n T ha n h,   T he   R e v i s e d   F o r d - F ul ke r s o A l g o r i t hm   F i ndi ng   M a x i m a l   F l o w s   o E x t e n de d   N e t w o r k s ,   I n t e r nat i o nal   J o ur n al   of   C om pu t e r   T e c hn ol o gy   and   A pp l i c a t i o ns   v o l .   5,   no .   4,   p p.   14 38 - 1442 ,   201 4.   [ 3]   V i e t   T r a n   N g o c ;   C hi e n   T r a n   Q uo c ;   a nd  T a u   N g uy e V a n,   I m pr o v i ng   C o m put i ng   P e r f o r m a nc e   f o r   A l g o r i t hm   F i nd i ng   M a x i m a l   F l o w s   o E xt e nd e M i xe d   N e t w o r ks ,   J our nal   o f   I nf or m at i on  and  C om pu t i n S c i e nc e ,   E ng l a n d,   U K ,   v o l .   10,   no .   1 ,   p p.   07 5 - 080,   2 015 .   [ 4]   G o l dbe r g   A .   V ;   a nd  T a r j a n   R .   E ,   A   ne w   a pp r o a c t o   t h e   m a xi m u m   o w   pr o bl e m ,   J o ur na l   of   t he   A C M   ( J A C M ) N e w   Y o r k,   N Y ,   U S A ,   v o l .   35 ,   no .   4 ,   pp .   921 - 94 0,   19 88 .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                IS S N :   2088 - 8708   Int   J   E l e c   &   Co m E n g ,   V o l .   10 ,   N o .   2 A p ri l   2020   :     1632   -   1640   1640   [ 5]   T r a n   Q uo c   C hi e n;   N g uy e M a T u e ;   a n T r a n   N g o c   V i e t ,   S ho r t e s t   P a t A l g o r i t hm   o E xt e nd e G r a p hs ,   P r oc e e di ng  o f   t he   6 t h   N at i on al   C on f e r e nc e   on   F undam e nt a l   and   A p pl i e d   I n f o r m at i on   T e c hn ol o gy   R e s e ar c h   ( F A I R ) V i e t na m ,   p p.   52 2 - 527 ,   2 013 .   [ 6]   E l l i s   L .   J o hns o n,   G e o r g e   L .   N e m ha u s e r ;   J o e l   S .   S o ko l ,   a nd   P a m e l a   H .   V a nc e ,   S ho r t e s t   P a t hs   a nd   M ul t i c o m m o di t y   N e t w o r F l o w s ,   A   T h e s i s   P r e s e nt e d   t o   t he   A c a de m i c   F a c ul t y ,   pp.   41 - 73,   20 03.   [ 7]   A nde r s o R .   J ;   a n d   J o   A .   C .   S ,   O n   t h e   P a r a l l e l   I m pl e m e n t a t i o o f   G o l db e r g s   M a xi m um   F l o w   A l g o r i t hm ,   P r oc e e di ngs   of   t he   f o ur t h   an nua l   A C M   s y m pos i um   o n   P ar al l e l   a l go r i t hm s   a nd   a r c h i t e c t ur e s ,   N e w   Y or k ,   U SA :   A C M pp.   16 8 - 177,   1 992 .      [ 8]   X i a o l o ng   M a   a nd   J i e   Z ho u,   A e xt e nd e d   s ho r t e d   p a t h   pr o bl e m   w i t s w i t c c o s t   be t w e e n   a r c s ,”   P r oc e e di ng s   of   t he   i nt e r n at i on al   m u l t i c o nf e r e nc e   o f   e ng i ne e r s   a nd   c om p ut e r   s c i e nt i s t s ,   H o ng   K o ng ,   I M E C S ,   20 08 .     [ 9]   X i a ng m i ng   Y a o ,   B a o m i H a n ,   B a o m i H a n ,   H ui   R e n S i m u l a t i o n - B a s e D y na m i c   P a s s e ng e r   F l o w   A s s i g nm e nt   M o de l l i ng   f o r   a   S c he du l e - B a s e T r a ns i t   N e t w o r k;   D i s c r e t e   D y n a m i c s   i N at u r e   an S oc i e t y -   H i nda w i ,   2 017 .   [ 10]   M i c hi e l   C . J .   B l i e m e r ,   M a r k   P . H .   R a a ds e n,   S t a t i c   t r a f f i c   a s s i g nm e n t   w i t r e s i dua l   que ue s   a nd   s p i l l b a c k,   U n i v e r s i t y   o f   S y dne y ,   E T H   Z ur i c h   C on f e r e nc e   pa pe r   ST R C ,   201 7.   [ 11]   P .   T .   S o kka l i ng a m ,   R .   K .   A huj a   a n J .   B .   O r l i n ,   N e w   P o l y no m i a l - T i m e   C y c l e -   C a nc e l i ng   A l g o r i t hm s   F o r   M i ni m um - C o s t   F l o w s ,   N e t w or k s ,   pp .   1 - 21 ,   199 6.   [ 12]   L .   K .   F l e i s c he r ,   A ppr o xi m a t i ng   f r a c t i o na l   m u l t i c o m m o di t y   o w   i n de pe n de n t   o f   t he   num b e r   o f   c o m m o di t i e s ,   S I A M   J .   D i s c r e t e   M a t h . ,   v o l . 13 ,   no . 4 ,   2 000 .   [ 13]   G .   K a r a ko s t a s ,   F a s t e r   a p pr o xi m a t i o s c he m e s   f o r   f r a c t i o na l   m ul t i c o m m o di t y   o w   pr o bl e m s ,   I P r o c e e di ng s ,   A C M - SI A M   Sy m po s i um   o D i s c r e t e   A l gor i t hm s ,   v o l . 4 ,   no . 1 ,   2002 .   [ 14]   J o s e ph  P r a s hke r   a nd  S hl o m o   B e kho r ,   S o m e   o bs e r v a t i o ns   o s t o c ha s t i c   us e r   e qu i l i b r i um   a n s y s t e m   o pt i m um   o f   t r a f c   a s s i g nm e nt ,   T r ans por t a t i on   R e s e ar c h   P ar t   B :   M e t hod ol o gi c al ,   v o l .   34 ,   no .   4 ,   2000 .   [ 15]     L uc a   T r e v i s a n ,   G e ne r a l i z a t i o ns   o f   t he   M a x i m um   F l o w   P r o bl e m ,   St an f o r d   U ni v e r s i t y - C S2 61:   O p t i m i z at i on ,   20 11.   [ 16]   W a r dr o p,   J .   G ,   S o m e   T he o r e t i c a l   A s pe c t s   o f   R o a T r a f f i c   R e s e a r c h ,   P r o c e e di ngs   of   t he   I n s t i t ut e   o f   C i v i l   E ng i ne e r s P a r t   I I ,   195 2.   [ 17]   A l e ks a nd e r ,   F a s t e r   A ppr o xi m a t i o S c he m e s   f o r   F r a c t i o na l   M u l t i c om m o di t y   F l o w   P r o bl e m s   v i a   D y na m i c   G r a ph   A l go r i t hm s ,   M as s ac hus e t t s   I n s t i t ut e   of   T e c hn ol o g y ,   2009 .   [ 18]   J ua C a r l o s   M uno z ,   J o r g e   A .   L a v a l ,   S y s t e m   o pt i m um   dy na m i c   t r a f f i c   a s s i g nm e nt   g r a ph i c a l   s o l ut i o m e t ho f o r   a   c o n g e s t e d   f r e e w a y   a nd  o ne   de s t i na t i o n,   T r a ns p or t at i o R e s e ar c h ,   P a r t   B   40 ,   200 6.   [ 19]   O l a f   J a h n,   R o l f   H .   M öh r i ng ,   S y s t e m   O pt i m a l   R o ut i ng   o f   T r a f c   F l o w s   w i t h   U s e r   C o ns t r a i n t s   i n   N e t w o r ks   w i t C o ng e s t i o n,   V o l .   53 ,   N o .   4 ,   200 5.   [ 20]   E r e r a ,   A . L . ,   D a g a nz o ,   C . F . ,   L ov e l l ,   T he   a c c e s s   c o nt r o l   pr o b l e m   o c a pa c i t a t e d   F I F O   ne t w o r k s   w i t u ni q ue   O - pa t h s   i s   h a r d ,   O pe r a t i ons   R e s e ar c h ,   v o l .   5 0,   no .   4,   2 002 .     [ 21]   L a v a l ,   J . A . ,   M un ˜ o z ,   J . C ,   S y s t e m   O pt i m um   D i v e r s i o n   o f   C o ng e s t e d   F r e e w a y   T r a f f i c ,   I ns t i t u t e   o f   T r ans por t a t i on   St ud i e s   R e s e ar c R e por t   U C B - I T S - RR ,   2002 .     [ 22]   Z i l i a s ko po ul o s ,   A . K ,   A   l i ne a r   r o g r a m m i ng   m o de l   f o r   t he   s i ng l e   d e s t i na t i o s y s t e m   o pt i m um   dy na m i c   t r a f f i c   a s s i g nm e nt   p r o bl e m ,   T r a ns p or t at i on   S c i e nc e ,   v o l .   3 4,   no . 1 ,   200 0.   [ 23]   M e h l ho r n ,   K . ,   M .   Z i e g e l m a n n,   R e s o ur c e   c o ns t r a i ne d   s ho r t e s t   p a t h s ,   M .   P a t e r s o n,   e d .   P r o c .   8 t h   A nnua l   E u r .   S y m po s .   o A l g o r i t hm s   ( E S A ) .   L e c t ur e   N o t e s   i n   C om pu t e r   S c i e nc e ,   S p r i ng e r ,   H e i de l be r g ,   G e r m a ny ,   2000 .   [ 24]   M e r c ha nt ,   D .   K . ,   G .   L .   N e m ha u s e r ,     A   m o de l     a nd     a n     a l g o r i t h m   f o r   t he   dy na m i c   t r a f c   a s s i g nm e nt   p r o bl e m s ,   T r ans por t a t i on   Sc i .   12 ,   197 8.         [ 25]   N a g a r ne y   A ,   M a t h e m a t i c a l   M o de l s   o f   T r a ns po r t a t i o a nd   N e t w o r k s ,   M a t he m at i c a l   M o de l s   i n   E c o nom i c s ,   20 07.         [ 26]   S c hul z ,   A .   S . ,   N .   E .   S t i e r - M o s e s ,   O n   t he   p e r f o r m a nc e   o f   us e r   e q ui l i b r i a   i n   t r a f c   ne t w o r ks ,   P r o c .   14t A nnu al   A C M - SI A M   Sy m p os   on   D i s c r e t e   A l g or i t hm s   ( SO D A ) .   S I A M ,   P h i l a d e l ph i a ,   P A ,   20 03 .          B I O G R A P H I ES   O F   A U T H O R S         D r .   T r an   N go c   V i e t .   B o r n   i n   197 i T h a nh  K h e   D i s t r i c t ,   D a   N a ng   C i t y ,   V i e t na m .   H e   g r a dua t e f r o m   M a t hs _I T   f a c ul t y   of   D a   N a ng   un i v e r s i t y   of   s c i e nc e .   H e   g o t   m a s t e r   o f   s c i e nc e   a t   un i v e r s i t y   o f   D a na ng   a nd   ho l d   P h . D   D e g r e e   i n   2 017   a t   D a na ng   un i v e r s i t y   o f   t e c hno l ogy .   H i s   m a i n   m a j o r :   A ppl i c a bl e   m a t he m a t i c s   i t r a ns po r t ,   p a r a l l e l   a nd   di s t r i bu t e d   pr o c e s s ,   di s c r e t e   m a t he m e t i c s ,   g r a p t he o r y ,   g r i d   C o m put i ng   a n di s t r i but e d   pr o g r a m m i ng           L e   H o n D u n g   w a s   bo r i 1 977 .   H e   g r a du a t e f r o m   i nf o r m a t i o t e c hno l o gy   f a c ul t y   o f   D a   L a t   uni v e r s i t y .   H e   g o t   m a s t e r   o f   D a na ng   un i v e r s i t y .     S i nc e   201 8,   he   ha s   b e e a   P hD   c a nd i da t e   a t   u ni v e r s i t y   o f   D a na ng ,   V i e t n a m .   H i s   m a i m a j o r :   di s c r e t e   m a t he m e t i c s ,   g r a ph  t he o r y   a nd  d i s t r i bu t e d   pr o g r a m m i ng .         Evaluation Warning : The document was created with Spire.PDF for Python.