Ford-Fulkerson Method

Facts

  • The Ford-Fulkerson method (G,S,t) is iterative
  • This method depends on three ideas:
    • Augmenting paths
    • Residual networks
    • Cuts
  • Simplified Pseudo-code:
    initialize flow f to 0
    while there exist an augmenting path p
        do augmented flow f along p
    return f

Augmenting Paths

  • An augmenting path p is a simple path from source S to sing t in the residual network
  • Each path have alternative free and matched edges in such way that begins and ends with free vertices.

Residual networks

  • Definition: Each edge (u,v) on an augmenting path admits some additional positive flow u to v without violating the capacity constrain on the edge.
    Ford_fulkerson_Residual_Flow
  • Example:
    Ford_Fulkerson_Transformation

Cuts

  • Minimum cut of a network: A cut whose capacity is minimum over all cuts on the network.
  • Max-flow min-cut theorem: A flow is maximum if and only if its residual network contains no augmenting path.
  • Example: cut(\{S, v_{1}, v_{2}\}), \{v_{3}, v_{4}, t\})
    Net-flow Across Cut (including net-flow between vertices): f(v_{1}, v_{3}) + f(v_{2},v_{3}) + f(v_{2}, v_{4}) = 14 + (-4) + 11 = 19
    Capacity (only edges going from source S to sink t): c(v_{1}, v_{3}) + c(v_{2}, v_{4}) = 12 + 14 = 26

 

Pseudocode

// Comments
Ford-Fulkerson (G,S,t)
for each edge (u,v)\epsilon E[G]
do f[u,v]\leftarrow 0 // f:flow
do f[v,u]\leftarrow 0
while there exist a path p from S to t in the residual network Gf
do cf(p)\leftarrow min\{cf(u,v): (u,v) is in p \} // cf: residual capacity
for each edge (u,v) in p
do f[u,v]\leftarrow f[u,v]+cf(p) // p: path
do f[v,u]\leftarrow -f[u,v]

 

Big O

Using either dept-first search or breadth-first search, the time to find a path in a residual network is O(V+E

Total running time is O(E|F*|) where f* is the maximum flow found

 

Note: If you find any mistake please let me know

Share

How to Create a Graph Derived from the 3-CNF Formula

The Clique Problem

The clique problem is an optimization problem where we ask if a clique (complete subgraphs) of a given size k exists in the graph.
The idea is to find the clique maximum size in a graph.

List of Facts

  • A clique in a undirected graph G = (V, E) is a subset V of vertices
  • Each pair of vertices is connected by an edge in E.
  • A clique is a complete sub-graph of G
  • The size of the clique is the number of vertices it contains

Example

Lets compute the graph from the formula \phi in polynomial time.

  • \phi = (x_{1} \vee \neg x_{2} \vee \neg x_{3} ) \wedge (\neg x_{1} \vee x_{2} \vee x_{3} ) \wedge (x_{1} \vee x_{2} \vee x_{3} )

Steps

First draw a graph G derived from the formula \phi where:

  • c_{1} = (x_{1} \vee \neg x_{2} \vee \neg x_{3} )
  • c_{2} = (\neg x_{1} \vee x_{2} \vee x_{3} )
  • c_{3} = (x_{1} \vee x_{2} \vee x_{3} )
  1. Connect c_{1}(x_{1}) to c_{2}(x_{2}, x_{3}) and c_{3}(x_{1},x_{2}, x_{3})
  2. Connect c_{1}(\neg x_{2}) to c_{2}(\neg x_{1}, x_{3}) and c_{3}(x_{1}, x_{3})
  3. Connect c_{1}(\neg x_{3}) to c_{2}(\neg x_{1}, x_{2}) and c_{3}(x_{1}, x_{2})
  4. Connect c_{2}(\neg x_{1}) to c_{1}(x_{2}, x_{3})
  5. Connect c_{2}(x_{2}) to c_{3}(x_{1}, x_{2}, x_{3})
  6. Connect c_{2}(x_{3}) to c_{3}(x_{1}, x_{2}, x_{3})
  7. Done

GNF Draw Steps3CNF Draw Complete

 

 

 

 

 

 

 

 

 

Share

Maximum Flow

Definition

  • The capacity constrain indicate that a given capacity must not be exceed by the flow from one vertex to another.
  • The skew symmetry (a notational convenience) indicate that the flow from vertex u to vertex v is the negative of the flow in the reverse direction.
  • The flow-conservation property indicate that the total flow out of a vertex other than the source S or sink t is 0
  • The total positive flow leaving a vertex is defined symmetrically
  • The total positive flow leaving the vertex minus the total positive flow entering a vertex is the  total net-flow at a vertex
  • The total positive flow entering a vertex other than the source S or sink t must be equal to the positive flow leaving that vertex.

Examples

 

 

Share

Notes: Operative Systems – Part 6

< Previous (Operative Systems – Part 5) | (Operative Systems – Part 7) Next >

NOTIFICATION: These notes are published for educational purposes. Using these notes is under your own responsibility and risk. These notes are given ‘as is’. I do not take responsibilities for how you use them.

PDF Content:

  • Least recently used  (LRU) page replacement algorithm
  • Not frequenty used (NFU) algorithm
  • Aging (approximation of LRU) algorithm
  • Working set
  • Current virtual time
  • Page replacement algorithm
  • Clock page replacement algorithm
  • WSClock page replacement algorithm
  • Local vs. Global replacement policies
  • Internal vs. External fragmentation
  • Page size
  • Periodic cleaning policy
  • Thrashing
  • Separation of policy and mechanism
  • Concurrency vs. parallelism
  • Critical sections

Operative_Systems_6

 

< Previous (Operative Systems – Part 5) | (Operative Systems – Part 7) Next >

Share