New Operators On Ford-Fulkerson Algorithm

Download as pdf or txt
Download as pdf or txt
You are on page 1of 10

IOSR Journal of Mathematics (IOSR-JM)

e-ISSN: 2278-5728, p-ISSN: 2319-765X. Volume 11, Issue 2 Ver. V (Mar - Apr. 2015), PP 58-67
www.iosrjournals.org

New Operators on Ford-Fulkerson Algorithm


M. Shokry
Department of physics and Mathematics, Faculty of Engineering, Tanta University, Tanta-Egypt,

Abstract: The maximum ow in network involves sending the maximum amount of material from a specied
source vertex s to another specied sink vertex t, subject to capacity restrictions on the amount of material that
can ow along each path.A closely related we formed a new concept of -closure space and -interior
space using subgraphs generated by Ford- Fulkerson algorithm steps, also we induced some new topological
properties .
Keywords: Graph theory, Rough set, Topology, Fuzzy set and Data mining.

I.

Introduction

Topology originated a branch of mathematics played an important role in the development of the
general theory. The concept of topology can be helpful in understanding phenomena in modern materials
science, complex system science, networks of life, economics, relativity and quantum theory, which represent
20th century physics and information science from a broader perspective.
Graph theory is a widely applied frame work in information, technology, geography, and computer
science. It is primarily Concerned with maximally efficient ow or connectivity in networks(Grossand
Yellen,1999). There are a number of interesting theorems, relative to capacitated networks, that give necessary
and sufficient conditions for existence of flows satisfying some conditions for various kinds. Typical of these
are the supply-demand theorem due to a condition for the existence of a flow satisfying demands at certain
nodes from supplies at other nodes ,which states a condition for the existence of circulatory flow in a network
in which each path has upper flow values and lower flow values
In this paper we add some new results along this lines which described asfollows. We fist establish a
new definitions for closure space and interior space concept on a network with certain of the nodes designated
as sources ,other as sinks, and assume that each source is required to send, and each sink to receive , an amount
that lies between this prescribed bounds. The new results asserts that if there is a flow that sends out of each
source an amount at least as great as the lower bound for the source,and into each sink no mor the upper bound
for the sink, and if there is a flow that sends out of each source no more than the upper bound for the source, and
into each sink at least as much as the lower bound for the sink, then there is a flow that meets all the
requirements simultaneously.
A flow network is a directed graph where each edge has a capacity and each edge receives a flow. A
network can be used to model traffic in a road system, fluids in pipes, current in an electrical circuit, web service
networks [1,2,8 ], or anything similar in which something travel through network of nodes, an example from the
medical field: it is known that the topology of the networks produced by cancer or other tissue anomalies is
different from that of normal tissue.The basic concepts of the networks are presented. Our purpose is explaining
Ford-Fulkerson algorithm and evaluate the maximal flow in the networks.
Also, we give new definitions of i closure and i interior operator in the networks flow using
the concept of classical closure operator and topological structures generated from from the steps of maximum
flow algorithm on a connected graphs, of network.
1.1 Basic Concepts
A network N is a digraph with two distinguished subsets of vertices X and Y, the vertices in X are the
source of N and those in Y are the sinks of N . Vertices which neither source nor sink are called intermediate
vertices denoted by I .The function C is the capacity function of N and its value on an arc a is the capacity of a
[8 ].A source is a vertex(s) of a directed graph with indegree 0. A Sink is a vertex (t) of a directed graph with
out degree 0.A Capacity is the maximum flow that may be sent through an edge or a vertex.A flow in network N
is an integer valued function f defined on its arc set A such that :
1- The rate of flow along an arc cannot exceed the capacity of the arc 0 f (a) c(a)

for all a A
2-The rate at which material is transported in to v is equal to the rate at which it is transported out of v

(v ) f

(v) for all v I .

DOI: 10.9790/5728-11255867

www.iosrjournals.org

58 | Page

New Operators on Ford-Fulkerson Algorithm


A flow augmenting path in a network with a given flow fij on each edge eij is a path from s to t such that :
- No flow in forward edge is equal to capacity thus fij < cij .
-No backward edge has flow 0 thus fij > 0. Let N be a network with a single source x and single sink y, a cut
in N is a set of arcs of the form S , S , where, x S, y S [16].
Example 1.1.1
In Fig. (4.2) a network flow N,where the first number is the capacity and the second is a given flow

The only augmenting paths are

p1 : 1 2 3 6, p 2 : 1 4 5 3 6 .If there's a flow


ij

augmenting path, we can use it to push through it an additional flow as the following:First compute
such as
ij cij f ij
min ij
for forward edge, ij f ij for backward edge and
. And add to each flow in
this path . In above network 3 in p1, 2 in
And the maximum flow is shown in Fig. (1.1.2)

p2

We notice that network flow with a cut set (S,T)has capacity of cut is the sum of the capacities of all
forward edge in (S,T) cap(S,T)=11+7=18
Any given flow in a network N is the net flow through any cut set (S,T) of N.
A flow f in a network N cannot exceed the capacity of any cut set (S,T)in N.A flow from S to T in a network N
is maximum if and only if there doesn't exist a flow augmenting path from S to T in N.Thus a flow is maximum
when doesn't exist a flow augmenting path[ 16 ].
Ford-Fulkerson Algorithm
A network flow inspired computer network applications which considered a point-to-point
communication network on which a number of information sources be multicast to certain sets of destinations.
We present an algorithm for determining a maximum flow in a network [1, 8]. This algorithm starting from the
initial flow and it recursively constructs a sequence of flow of increasing value and terminates with a maximum
flow.
1. Assign an initial flow fij
2. Label s by ,mark the other vertices '' un labeled"

DOI: 10.9790/5728-11255867

www.iosrjournals.org

59 | Page

New Operators on Ford-Fulkerson Algorithm


3.

Find a label vertex i that has not yet been scanned. Scan ias the follows: for every unlabeled adjacent vertex
j if cij > ij .
4. Compute ij = cij fij , ij = 1 if i=1 and ij = min i , ij if i > 1 .
5. Label j with "forward label"(i+ , j )or if fij > 0
6. Compute j = min i , fji and label j by a "backward label"(i , j . If no such j by a "backward
label"(i , j if no such j exist then output f is the maximum flow (stop), else continue (go to step4)
7. Repeat 3 until t is reached. (This gives a flow augmenting path p) if it is possible to reach t then output f is
the maximum flow (stop) else continue (go to step 5).
8. Back track the path using the labels.
9. Increase the existing flow by i as f = f + i
10. Remove all labels from vertices 2,..,n and go to step 3. End Ford- Fulkerson.
Example 1.1.2: In Fig. (4.5) we compute the maximum flow by applying Ford- Fulkerson algorithm.

Let s(1) by ,mark {2,3,4,5,6}(un labeled) and initial flow f=9 .


Step1 Compute 12 = 20 5 = 2 label 2 by (1+,15) , 14 = 10 4 = 4 label 4 by (1+,6).Compute
23 = 11 8, 3 = min 2 , 3 = 3 label 3 by (2+,3) .Compute
5 = min 2 , 3 = 3 ,label 5 by (2-,3).
Step 2 Compute 36 = 13 6, 6 = min 3 , 7 = 3 label 6 by (3+,3) .

P : s 1 2 3 6 t is a flow augmenting path

Step 3 Put

3 the flow is f12 8 , f 23 11 , f36 9 and other fij unchanged

Step 4 Remove labels on vertices 2,.., 6 and go to step1


Step 5 Compute 12 = 20 8 = 2 label 2 by (1+,12) , 14 = 10 4 = 4 label 4 by (1+,6).Compute
14 = 10 4, 4 label 4 by (1+,6) .Compute 5 = min 2 , 3 = 3 ,label 5 by (2-,3). 3 = min 5 , 2 = 2 label
3 by (5-,2).36 = 13 9, 6 = min 3 , 4 = 2 label 6 by (3+,2).
P : s 1 2 5 3 6 t
Step
6
is
a
flow
augmenting
path

i 2 and the flow is f12 10 , f52 1 f35 0 f36 11


and other fij unchanged and the flow is maximum.

II.

New Operators On Ford-Fulkerson Algorithm Steps

In several areas of Computer Science, one is interested in using abstract mathematical structures as a basis
for modelling certain phenomena of the real world. This interest is particularly strong in the knowledge
representation subfield of artificial intelligence so, it must putting some conditions on closure operator to be
compatibles with its application.
In the following Hi denotes the subgraph Hi=(V(Hi), E(Hi)) which is represent the subgraph in step i
for Ford-Fulkerson algorithm of a graph G=(V(G), E(G)), He denotes the subgraph He=(V(He), E(He)) which is
represent the subgraph in end step for Ford-Fulkerson Algorithm, and C i will be used for a family of subgrahs of
the power set of P(V(Hi)) obtained by closure operators cli (K)where K Hi .

DOI: 10.9790/5728-11255867

www.iosrjournals.org

60 | Page

New Operators on Ford-Fulkerson Algorithm


Definition 2.1
Let N=(G,s,t,c) be a network with capacity cij ,s start vertex , t terminal vertex and flow
f ij

fij , i neighborhoods can defined as Nv ii = {vj : vj V, eij E ,

c ij

Hi , Nv ii
i

> i } and i -closure operators ,

cl1i K = {vj : vj
V(K) } P(V(Hi ))for i, j, k = 1, , n , 1 < i 1
defined on a family C of subgrahs from G=(V,E) and satisfies axioms.
(1) cl1i () = and cl1i V G = V G (2) Hi Hj G implies cl1i (Hi ) cl1i (Hj )
(3) cl1i (Hi Hj ) = cl1i (Hi ) cl1i (Hj ), for all Hi ,Hj G
ij

The pair (V(G), cli ) is i -closure space this notations is close to the classical notation of topology. , i
-closure space differs from topologies in that they do not require the open subgraphs to be stable with respect to
finite intersection. Furthermore, there exists the maximal open subgraph denoted as max(Cji ) in Cji :
ij

ij

j = 1, 2.The i interior operator (Dual operator) can defined by int i K = V G (cli ((V G K))
which satisfy axioms:

ij

ij

(1) int i () = and int i V G


(2) Hi Hj G implies
ij

ij

ij

ij
int i

= V(G)
ij

(Hi ) int i (Hj )


ij

(3) int i (Hi Hj ) = int i (Hi ) int i (Hj ), for all Hi ,Hj G

The pair (V(G), int i ) is i -interior space.


Definition 2.2
Let N=(G,s,t,c) be a network with capacity cij ,s start vertex , t terminal vertex and flow fij , a (V(G),
i1
cli )on a subgraph Hi of Ford-Fulkerson algorithm in step i of a graph G is a family where
i
C1i = {cl1i
i K : K Hi } P(V(Hi )) together V(G). The elements of C1 are called 1-closed subgraphs of i closure space in step i (V(G), cli1
i ).
Definition 2.3
Let N=(G,s,t,c) be a network with capacity cij ,s start vertex , t terminal vertex and flow fij , a (V(G),
cli2
)on
a
subgraph Hi of Ford-Fulkerson algorithm in step i of a graph G is a family
i
C2i = {cli2
i K : K Hi} P(V(Hi)) where

i2
clsi K = V K {vj : vj Hi , Nv ii V(K) } P(V(Hi ))
i2
together V(G). The elements of (V(G), cli2
i ) are called i -closed subgraphs of the (V(G), clsi )in step i.
The complement of ji -open subgraph is called ji -closed subgraph. The ji -interior of subgraph K is int1i
i K
= {V(O) : O is j-open subgraph, V(O) V(K)}, and the ji -closure of subgraph K is cl1i
K
=

{V(F)
: F is
i
ji -closed subgraph,
V(K) V(F)} where j = 1, 2.
Example 2.1 :
Given a network flow N=(G,a,d,c)

Here we find a weighted graph, of maxinum weight connecting two specified vertices a and d, evaluate
ij
ij
i closure spaces (V, cli ) and i interior spaces (V, int i )corresponding to each step for Ford-Fulkerson
algorithm.
DOI: 10.9790/5728-11255867

www.iosrjournals.org

61 | Page

New Operators on Ford-Fulkerson Algorithm


Step 1
vi

a
b
f
c
e
d

a
---0.25
-0.4

Table (2.1)
For i = 0
If

V(H0 )= {a}

If

V(H1 )= {a,b}

b
-0.25
-
-0.7
-0.8

f
-0.4

-
-0.6

c
-
0.7

--0.4
-0.5

e
-
-0.8
0.6
0.4
--1

d
-

0.5
1
--

Nv0i

{b,f}
{ c}
{ e}
{e, d}
{d}

N0.5
vi

{ c}
{e}
{d}
{d}

N0.8
vi

{d}

,then (V, cl01


i )= {V(G), , {b,f }}and
(V(G), int 01
i )= {V(G), , {a,c,e,d }}
, then (V, cl11
i )= {V(G), , {c},{b,f},{b,f, c}}
(V(G), int 21
i )={V(G), , {a,b,f,e,d},{a,c,e,d},{a,e,d}}

If V(H2 )= {a, b, f}, then


(V(G), cl21
i )= {V(G), , {c},{e},{b,f},{b,f, c},{c,e},{b,f,e},{b,f,c,e}
(V(G), int 21
i )= {V(G), , {a,b,f,e,d },{a,b,c,f,d},{a,c,e,d},{a,e,d},{a,b, f,d},{a,c,d},{a,d}}

If V(H3 )= {a, b, f,c}, then


(V, cl31
i ) = {V(G), ,{c},{e},{b,f},{e,d},{b,f,c},{c,e},{b,f,e},{b,f,c,e}{e,c,d},
{b,f,e,d},{b,f,c,e,d}
(V(G), int 31
i )= {V(G), , {a,b,f,e,d },{a,b,c,f,d},{a,c,e,d},{a,e,d},
{a,b, f,d},{a,c,d},{a,d},{a,b,f,c},{a,b,f},{a,c},{a}}

If V( H4 ) = {a, b, f,c,e}, then


(V(G), cl41
i )= {V(G), ,{c},{e},{d},{b,f},{e,d},{b,f,c},{c,e},
{b,f,e},{b,f,c,e}{e,c,d}, {b,f,e,d},{b,f,c,e,d},{c,d},{b,f,d},{b,f,c,d},{c,e,d}}
(V(G), int 41
i )= {V(G), , {a,b,f,e,d },{a,b,c,f,d},{a,c,e,d},{a,e,d},
{a,b, f,d},{a,c,d},{a,d},{a,b,f,c},{a,b,f},{a,c},{a},{a,b,f,e},{a,c,e},{a,e},{a,b,f}}

If V(H5 )= {a, b, f,c,e,d}, then

(V, cl51
i )= {V(G), ,{c},{e},{d},{b,f},{e,d},{b,f,c},{c,e},{b,f,e},{b,f,c,e}{e,c,d},
{b,f,e,d},{b,f,c,e,d},{c,d},{b,f,d},{b,f,c,d},{c,e,d}}
(V(G), int 51
i )= {V(G), , {a,b,f,e,d },{a,b,c,f,d},{a,c,e,d},{a,e,d},
{a,b, f,d},{a,c,d},{a,d},{a,b,f,c},{a,b,f},{a,c},{a},{a,b,f,e},{a,c,e},{a,e},{a,b,f}}

For i

= 0.5

, then (V, cl01


i )= {V(G), }
(V(G), int 01
i )= {V(G), }
V(H1 ) = {a, b}
, then (V, cl11
i )= {V(G), , { c }}
(V(G), int11
i )= {V(G), ,{a,b,f,e,d}
21
V(H2 ) = {a, b, f} , then (V, cli )= {V(G), , { c },{e},{c,e}}
(V(G), int21
i )= {V(G), ,{a,b,f,e,d},{a,b,f,c,d},{a,b,f,d}}

If V( H0 ) = {a}
If
If

If V(H3) = {a, b, f,c}

,then

(V, cl31
i )= {V(G), , { c },{e},{d},{c,e},{c,d},{e,d},{c,e,d}}
(V(G), int 31
i )= {V(G), ,{a,b,f,e,d},{a,b,f,c,d},{a,b,f,d},{a,b,f,c,e},{a,b,f,e},
{a,b,f,c },{a,b,f}}

If H4 = {a, b, f,c,e}

, then

(V(G), cl41
i )= {V(G), , { c },{e},{d},{c,e},{c,d},{e,d},{c,e,d}}
(V(G), int 41
i )= {V(G), ,{a,b,f,e,d},{a,b,f,c,d},{a,b,f,d},{a,b,f,c,e},{a,b,f,e},
{a,b,f,c },{a,b,f}}

If V( H5 )= {a, b, f,c,e,d} , then


(V(G), cl51
i )= {V(G), , { c },{e},{d},{c,e},{c,d},{e,d},{c,e,d}}
(V(G), int 51
i )= {V(G), ,{a,b,f,e,d},{a,b,f,c,d},{a,b,f,d},{a,b,f,c,e},{a,b,f,e},
{a,b,f,c },{a,b,f}}

DOI: 10.9790/5728-11255867

www.iosrjournals.org

62 | Page

New Operators on Ford-Fulkerson Algorithm


For i = 0.8
If H0 = {a}

01
, then (V(G), cl01
i )= (V(G), int i )= {V(G), }

If H1 = {a, b}

11
, then (V(G), cl11
i )= {(V(G), int i )= V(G), }

21
, then (V(G), cl21
i )= (V(G), int i )= {V(G), }
31
31
,then (V(G), cli )= (V(G), int i )= {V(G), }
, then (V(G), cl41
i )= {V(G), , {d }}
(V(G), int41
i )= {V(G), , {a,b,f,c,e }}
If H5 = {a, b, f,c,e,d} , then (V(G), cl51
i )= {V(G), , {d }}
(V(G), int 41
i )= {V(G), , {a,b,f,c,e }}

If H2 = {a, b, f}
If H3 = {a, b, f,c}
If H4 = {a, b, f,c,e}

Step 2: Add 3 to augumented path and obtain i closure spaces (V, cli2
i )

vi

a
b
f
c
e
d

a
---0.4
-0.4

b
-0.4
-
-1
-0.8

f
-0.4

-
-0.6

c
-
1

--0.4
-0.7

e
-
-0.8
0.6
0.4
--1

d
-

0.7
1
--

N0v i

{b,f}
{ c}
{ e}
{e, d}
{d}

Nv0.5
i

{ c}
{e}
{d}
{d}

N0.8
vi

{c}

{d}

Table (4.1)
We notice that (V, cli2
)in
step
2
are
the
same
as
(V,
cli1
i
i ) , i = 1, ,5 in step 1 for the same values of i except
for

k 0.8

If H0 = {a}

the values of (V, cli2


i ) are

02
, then (V, cl02
i )= (V(G), int i )= {V(G), }

, then (V, cl12


i )= {V(G), ,{c}}
(V(G), int12
i )= {V(G), ,{a,b,f,e,d}}
H2 = {a, b, f} , then (V, cl22
i )= {V(G), ,{c}}
(V(G), int 22
i )= {V(G), ,{a,b,f,e,d}}
H3 = {a, b, f,c} ,then (V, cl32
i )= {V(G), ,{c}}
(V(G), int 32
i )= {V(G), ,{a,b,f,e,d}}
H4 = {a, b, f,c,e} , then (V, cl42
i )= {V(G), ,{c},{d },{c,d}}
(V(G), int 42
i )= {V(G), ,{a,b,f,e,d},{a,b,c,f,e},{a,b,f,e}}
H5 = {a, b, f,c,e,d} , then (V, cl52
i )= {V(G), , {c},{d },{c,d}}
(V(G), int 52
i )= {V(G), ,{a,b,f,e,d},{a,b,c,f,e},{a,b,f,e}}

If H1 = {a, b}
If
If
If
If

In similar manures we can add the vertices of Hi of every step to calculate (V(G), clsi2i )in every step i.
Step 3

DOI: 10.9790/5728-11255867

www.iosrjournals.org

63 | Page

New Operators on Ford-Fulkerson Algorithm


vi

a
---0.4
-0.6

a
b
f
c
e
d

b
-0.4
-
-1
-0.8

f
-0.6

-
-0.9

Table(2.2)
For i = 0

c
-
1

-0
-0.8

e
-
-0.8
0.9
0
--1

d
-

0.8
1
--

N0v i

{b,f}
{ c}
{ e}
{d}
{d}

N0.5
vi

{f}
{ c}
{e}
{d}
{d}

N0.8
vi

{d}

, then (V, cl03


i )= {V(G), , {b,f }}
(V(G), int 01
i )= {V(G), , {a,c,e,d }}
, then (V, cl13
i )= {V(G), , {c},{b,f},{b,f, c}}
(V(G), int 21
i )={V(G), , {a,b,f,e,d},{a,c,e,d},{a,e,d}}

If H0 = {a}
If H1 = {a, b}

If H2 = {a, b,f}, then


(V, cl23
i )= {V(G), , {c},{e},{b,f},{b,f, c},{c,e},{b,f,e},{b,f,c,e}}
(V(G), int 21
i )= {V(G), , {a,b,f,e,d },{a,b,c,f,d},{a,c,e,d},{a,e,d},
{a,b, f,d},{a,c,d},{a,d}}

If H3 = {a, b, f,c}, then


(V, cl31
i )= {V(G), ,{c},{e},{d},{b,f},{b,f,c},{c,e},{c,d},{e,d},{b,f,e},{b,f,c,e},
{b,f,d},{b,f,c,d},{b,f,e,d},{c,e,d},{b,f,c,e}}
(V(G),int31
i )={V,,{a,b,f,e,d},{a,b,c,f,d},{a,c,e,d},{a,e,d},{a,b,f,d},{a,c,d},{a,d},
{a,b,f,c},{a,b,f},{a,c},{a},{a,b,f,e},{a,c,e},{a,e},{a,b,f},{a,b,f,c}}

If H4 = {a, b, f,c,e}, then

(V, cl43
i )= {V(G), ,{c},{e},{d},{b,f},{b,f,c},{c,e},{c,d},{e,d},{b,f,e},{b,f,c,e},
{b,f,d},{b,f,c,d},{b,f,e,d},{c,e,d},{b,f,c,e}}
(V(G), int 41
i )= {V(G), , {a,b,f,e,d },{a,b,c,f,d},{a,c,e,d},{a,e,d},
{a,b, f,d},{a,c,d},{a,d},{a,b,f,c},{a,b,f},{a,c},{a},{a,b,f,e},{a,c,e},{a,e},{a,b,f}}

If H5 = {a, b, f,c,e,d}, then


(V, cl53
i )= {V(G), ,{c},{e},{d},{b,f},{b,f,c},{c,e},{c,d},{e,d},{b,f,e},{b,f,c,e},
{b,f,d},{b,f,c,d},{b,f,e,d},{c,e,d},{b,f,c,e}}
(V(G), int 51
i )= {V(G), , {a,b,f,e,d },{a,b,c,f,d},{a,c,e,d},{a,e,d},
{a,b, f,d},{a,c,d},{a,d},{a,b,f,c},{a,b,f},{a,c},{a},{a,b,f,e},{a,c,e},{a,e},{a,b,f}}

For i = 0.5
If H0 = {a}

, then (V, cl03


i )= {V(G), , {f}}

If H1 = {a, b}

, then (V, cl13


i )= {V(G), , { c },{f},{c,f}}

If H2 = {a, b, f}

, then
(V, cl23
i )= {V(G), , { c },{f},{e},{c,f},{f,e},{c,e},{c,f,e}}

If H3 = {a, b, f,c}

,then

(V, cl33
i )= {V(G), , { c },{f},{e},{d},{c,d},{f,d},{e,d},{d,c,f},{d,f,e},{d,c,e},
{d,c,f,e}{c,f},{f,e},{c,e},{c,f,e}}

If

H4 = {a, b, f,c,e}

, then

(V, cl43
i )= {V(G), , { c },{f},{e},{d},{c,d},{f,d},{e,d},{d,c,f},{d,f,e},{d,c,e},
{d,c,f,e}{c,f},{f,e},{c,e},{c,f,e}}

If H5 = {a, b, f,c,e,d} , then


(V, cl53
i )= {V(G), , { c },{f},{e},{d},{c,d},{f,d},{e,d},{d,c,f},{d,f,e},{d,c,e},
{d,c,f,e}{c,f},{f,e},{c,e},{c,f,e}}

Thus we arrived to the maximum flow


(k+1)i
(k+1)i
In above example we notice that (V, clki
) for k=0,,5 and i=1,2,3 (i.e (V, cli
)
i ) (V, cli
is finar than (V, clki
)).
From
abve
we
must
generalized
the
inclusion
relation
to
formulate
topological
properties
i
which appeared in Ford-Fulkerson algorithm .
DOI: 10.9790/5728-11255867

www.iosrjournals.org

64 | Page

New Operators on Ford-Fulkerson Algorithm


Definition 2.4
ki
ki
Let (V, clki
i )is called i -subclosure space of a (V, cl )if for each i -closed subgraph F1 (V, cli ),
i

ki
ki
there exists each i -closed subgraph F (V, clki
i )such that F1 F and denoted by cli s cli .

Proposition 2.1
Let N=(G,s,t,c) be a network with capacity cij ,s start vertex , t terminal vertex and flow fij , and
Hi=(V(Hi), E(Hi)), Hi+1=(V(Hi+1), E(Hi+1)) are subgraphs in G represent the steps i, i+1in Ford-Fulkerson
algorithm such that
(k+1)i
Hi Hi+1, then clki
.
i ) cli
Proof.
In a network the neighborhood of xi is the points that achieves

f ij

> i and at the first step the ratio

c ij

fi
ci

is increase in some points thusNv ii Nv ji for every j i Where Nv 0i is the neighborhood of xi at step

o(before applying the algorithm) and Nv 1i is the neighborhood of xi at Step 1Similarly, the next steps

N v o N v1 .... N v n so V, clkii ) (V, cl(k+1)i


).
i
i
i
i

Proposition 2.2
The minimal closed set in any network flow is the sink vertex and it always a singleton.
Proof .From the definition network and i -neighborhood .
Proposition 2.3
Let N=(G,s,t,c) be a network with capacity cij ,s start vertex , t terminal vertex and flow fij , and
Hi=(V(Hi), E(Hi)) subgraph in G represent the steps i, in Ford-Fulkerson algorithm , then the following
satisfies:
ij
ij
(a) int i V Hi V Hi cli V Hi for any subgraph Hi
ij

(b) cli V Hi

= V Hi for any induce subgraph Hi

Proof
ij

( a)If vi int i V Hi
vi V Hi

then there exist Nv ii , vj V(Hi ), eij E(Hi ) and

ij

so Nv ii int i V Hi

f ij
c ij

> i then

V Hi . Also, vi V Hi then there exists Nv ij such that


ij

ij

Nv ij V Hi which implies that vi cli V Hi


( b)is obvious .

so V Hi cli V Hi

Proposition 2.4
Let N=(G,s,t,c) be a network with capacity cij ,s start vertex , t terminal vertex and flow fij ,
Hi=(V(Hi), E(Hi)) is subgraph in G represent the steps i with value i ,Hp=(V(Hp, E(Hp)) subgraph in G
represent the steps p with value k in Ford-Fulkerson algorithm and k i then following satisfies:
ij
ij
ij
ij
(a )If Hi Hi+1 then int i V Hi int i V Hi+1 and cli V Hi cli V Hi+1
ij

(b) clk V Hi V Hp
ij

(c) int i V Hi V Hp

ij

cli V Hi

ij

cli V Hp

ij

ij

int k V Hi

int k V Hp

Proof:

ij
If vi int i V Hi then there exist Nv ii such that vj V Hi , eij E Hi
and

f ij

c ij

> i such that vi V Hi


ij

vi int i V Hi+1

so

ij

ij

so Nv ii int i V Hi

int i V Hi

ij

ij

int i V Hi+1 .If vi cli V Hi then there exist Nv ii such that


ij

Nv ii V Hi then vi V Hi+1 so,vi cli V Hi+1


(b) ,(c) from Prop. 2.3 and (a)

DOI: 10.9790/5728-11255867

V Hi V Hi+1 then
ij

which implies cli V Hi

www.iosrjournals.org

ij

cli V Hi+1

65 | Page

New Operators on Ford-Fulkerson Algorithm


Proposition 2.5
Let N=(G,s,t,c) be a network with capacity cij ,s start vertex , t terminal vertex and flow fij and
Hi=(V(Hi), E(Hi)) subgraph in G represent the steps i in Ford-Fulkerson algorithm then following satisfies::
ij
ij
(a) int i V G V Hi = V G cli V Hi
ij

ij

ij

ij

(b) int i (int i V Hi ) = cli int i V Hi


ij

ij

ij

ij

(d) cli (cli V Hi ) = int i (cli V Hi )


Proof. Obviously
Definition 2.5
Let N=(G,s,t,c) be a network with capacity cij ,s start vertex , t terminal vertex and flow fij , a (V(G),
ji
cli )on a subgraph Hi =(V(Hi), E(Hi)) of Ford-Fulkerson algorithm in step i of a connected graph G=(V,E)
.The i -independency of a vertices of Hi on G with respect to i closure spaces and defined as follows:
ji
cli (V(Hi ))
ji (V(Hi )) = 1
i
V(G)
Example 2.2
From Examples 2.1 we have:
ij (V(H0 )) = 1 , i =1,2,3 j= 0,,5 and i {0,0.5,0.8}
i

11
(V(H1 )) = 6 , 11
(V(H1 )) = 1 ,
0
0.5

11
(V(H1 )) = 1
0.8

21
(V(H1 )) = 1 , 21
(V(H1 )) = 6 ,
0
0.5

21
(V(H1 )) = 1
0.8

31
(V(H1 )) = 1 , 31
(V(H1 )) = 6 ,
0
0.5

31
(V(H1 )) = 1
0.8

3
3

By the same way we can find all i -independency for all subgraphs inducd by all step of Ford-Fulkerson
algorithm.
Proposition 2.6
Let N=(G,s,t,c) be a network with capacity cij ,s start vertex , t terminal vertex and flow fij ,,
G=(V(G), E(G)) be a connected graph, and Hi, Hi+1 be a subgraphs in G represent of Ford-Fulkerson algorithm
in step i, i+1, then
ij (V(Hi )) ij (V(Hi+1 ))
i
i
for every i = 0, 1, , k-1 , where k is the unumber of subgraphs in induced by Ford-Fulkerson algorithm in
each step i of a connected graph G=(V,E)
Proof.
Let Hi , Hi+1 be a subgraphs in G represent Ford-Fulkerson algorithm of steps i, i+1:
i = 0, 1, , k. Since V(Hi) V(Hi+1) for every i = 0, 1, , k, implies
ji

ji

cli (V(Hi ) cli (V(Hi+1 ) then

ji
i

cl (V(H i ))
V(G)

ji
i

cl (V(H i+1 ))
V(G)

so ij (V(Hi )) ij (V(Hi+1 )).


i

Proposition 2.7
Let N=(G,s,t,c) be a network with capacity cij ,s start vertex , t terminal vertex and flow fij ,, G=(V(G),
E(G)) be a connected graph, and Hi, be a subgraph in G represent of Ford-Fulkerson algorithm in step i, i+1,
then ij (V(Hi )) ij (V(Hi )) ,i j for every i = 0, 1, , k-1 , where k is the unumber of subgraphs in
i

induced by Ford-Fulkerson algorithm in each step i of a connected graph G=(V,E)


Proof. Obviously

III.

Conclusion

The basic concepts of the networks are presented. We explain Ford-Fulkerson Algorithm. The aim of
this paper is to linked topological directions with graph theory directions through maximal network flow
algorithm to evaluate the maximal flow in the networks. Therefore we will try to study applications used this
algorithms where a metric important to formulate it and illustrate some hidden topological properties.

DOI: 10.9790/5728-11255867

www.iosrjournals.org

66 | Page

New Operators on Ford-Fulkerson Algorithm


References
[1].
[2].
[3].
[4].
[5].
[6].
[7].
[8].
[9].
[10].
[11].

J. Bondy, D. S. Murty, Graph theory with Applications, North-Holland, 1992.


R. Diestel, Graph Theory II, Springer-Verlag, 2005.
R. Englking, Outline of General Topology, Amsterdam, 1989.
S. Lee, F. Hsu, Spatial reasoning and similarity retrieval of images using 2D C-string knowledge representation. Pattern
Recognition 25 (3), 305318, 1992.
W. D. Wallis, A Beginner's Guide to Graph Theory, Second Edition, 2007.
S. Willard, General Topology, Addison Wesley Publishing Company, Inc, 1970.
R. J. Wilson, Introduction to Graph Theory, Fourth Edition, 1996.
M. Shokry and Y. Y. Yousif, Closure operators on graphs, Australian Journal of Basic and Applied Sciences, Australia, Vol.5,
No.11, (2011), pp.1856-1864.
M. Shokry and Y. Y. Yousif, Connectedness in graphs and Gm-closure spaces, Journal of Computer Sciences, International Centre
For Advance Studies, India, Vol.22, No.3, (2011), pp.77-86.
M. Shokry and Y. Y. Yousif, Gm-closure spaces on digraphs and near boundary region and near accuracy in G m-closure
approximation spaces, International Journal of Intelligent Information Processing, Korea, 2012. (Accepted, waiting publication).
M. Shokry and Y. Y. Yousif, Pre-topology generated by the shortest path problem, International Journal of Contemporary
Mathematical Sciences, Hikari Ltd, Bulgaria, Vol.7, No.17, (2012), pp.805-820.

DOI: 10.9790/5728-11255867

www.iosrjournals.org

67 | Page

You might also like