New Operators On Ford-Fulkerson Algorithm
New Operators On Ford-Fulkerson Algorithm
New Operators On Ford-Fulkerson Algorithm
e-ISSN: 2278-5728, p-ISSN: 2319-765X. Volume 11, Issue 2 Ver. V (Mar - Apr. 2015), PP 58-67
www.iosrjournals.org
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
DOI: 10.9790/5728-11255867
www.iosrjournals.org
58 | Page
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
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.
Step 3 Put
II.
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
c ij
Hi , Nv ii
i
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
ij
ij
ij
int i
= V(G)
ij
(3) int i (Hi Hj ) = int i (Hi ) int i (Hj ), for all Hi ,Hj G
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
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}
(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
If V( H0 ) = {a}
If
If
,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}}
DOI: 10.9790/5728-11255867
www.iosrjournals.org
62 | Page
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}
02
, then (V, cl02
i )= (V(G), int i )= {V(G), }
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
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}
If H0 = {a}
If H1 = {a, b}
(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}}
For i = 0.5
If H0 = {a}
If H1 = {a, b}
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}}
www.iosrjournals.org
64 | Page
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
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
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
Proof
ij
( a)If vi int i V Hi
vi V Hi
ij
so Nv ii int i V Hi
f ij
c ij
> i then
ij
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
vi int i V Hi+1
so
ij
ij
so Nv ii int i V Hi
int i V Hi
ij
ij
DOI: 10.9790/5728-11255867
V Hi V Hi+1 then
ij
www.iosrjournals.org
ij
cli V Hi+1
65 | Page
ij
ij
ij
ij
ij
ij
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
ji
i
cl (V(H i ))
V(G)
ji
i
cl (V(H i+1 ))
V(G)
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
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
DOI: 10.9790/5728-11255867
www.iosrjournals.org
67 | Page