Scribd
Upload
16 views5 pages

prim's algo

The document outlines Prim's and Kruskal's algorithms for finding the Minimum Spanning Tree (MST) of a graph, detailing their steps and providing examples. It also introduces network flow theory, emphasizing key concepts like flow networks, maximum flow problems, and the Max-Flow Min-Cut Theorem, along with their applications. Additionally, it mentions the Ford-Fulkerson algorithm for computing maximum flow in a flow network.

Uploaded by

l5ee2s1nth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
16 views5 pages

prim's algo

The document outlines Prim's and Kruskal's algorithms for finding the Minimum Spanning Tree (MST) of a graph, detailing their steps and providing examples. It also introduces network flow theory, emphasizing key concepts like flow networks, maximum flow problems, and the Max-Flow Min-Cut Theorem, along with their applications. Additionally, it mentions the Ford-Fulkerson algorithm for computing maximum flow in a flow network.

Uploaded by

l5ee2s1nth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Simple Steps of Prim's Algorithm

1. Start with Any Vertex:


o Pick any vertex to start. This will be the starting point of your
MST.
2. Grow the Tree:
o Look at all the edges connected to the vertices already
included in the MST.
o Select the edge with the smallest weight that connects a
vertex in the MST to a vertex outside the MST.
o Add the selected edge and the new vertex to the MST.
3. Repeat:
o Continue this process until all vertices are included in the
MST.
Example
Let's use a simple example to illustrate the steps:
Graph:
Vertices: {A, B, C, D}
Edges with weights:
{ (A-B, 1), (A-C, 3), (B-C, 2), (B-D, 4), (C-D, 5) }
Steps:
1. Start with Vertex A:
o A is included in the MST.
2. Choose the Minimum Weight Edge:
o The edges connected to A are (A-B, 1) and (A-C, 3).
o The smallest weight is (A-B, 1). Add B to the MST.
3. Add B to the MST:
o Now A and B are in the MST.
o The edges to consider are (A-C, 3), (B-C, 2), and (B-D, 4).
o The smallest weight is (B-C, 2). Add C to the MST.
4. Add C to the MST:
o Now A, B, and C are in the MST.
o The edges to consider are (A-C, 3), (B-D, 4), and (C-D, 5).
o The smallest weight is (B-D, 4). Add D to the MST.
5. Final MST:
o Edges: { (A-B, 1), (B-C, 2), (B-D, 4) }
o Total Weight: 7
Sure! Here's an overview of Kruskal's Spanning Tree Algorithm, a popular algorithm used to
find the Minimum Spanning Tree (MST) of a graph.

Kruskal's Spanning Tree Algorithm


Objective: Kruskal's algorithm aims to find the Minimum
Spanning Tree (MST) of a connected, undirected graph with
weighted edges. The MST is a subset of the edges that
connects all vertices in the graph without cycles and with the
minimum possible total edge weight.
Steps:
1. Sort the Edges:
o Sort all the edges in the graph in non-decreasing

order of their weights.


2. Initialize the MST:
o Create an empty set to store the edges included in

the MST.
3. Iterate through Sorted Edges:
o Iterate through the sorted edges and for each edge:

 Check if adding the edge to the MST will form a

cycle using the Union-Find data structure.


 If it does not form a cycle, add the edge to the

MST.
 Repeat until the MST contains (V - 1) edges,

where V is the number of vertices in the graph.


4. Return the MST:
o The edges in the MST form the Minimum Spanning

Tree of the graph.


Example:
Let's consider a simple example to illustrate Kruskal's
algorithm.
Graph:
Vertices: {A, B, C, D, E}
Edges with weights: { (A-B, 1), (A-C, 3), (B-C, 2), (B-D, 4), (C-
D, 5), (C-E, 6) }

Steps:
1. Sort edges by weight:
2. (A-B, 1), (B-C, 2), (A-C, 3), (B-D, 4), (C-D, 5), (C-E, 6)
3. Initialize an empty MST set.
4. Iterate through sorted edges and add to MST if it doesn't
form a cycle:
o Add (A-B, 1)

o Add (B-C, 2)

o Add (A-C, 3) (forming a cycle, not added)

o Add (B-D, 4)

o Add (C-D, 5) (forming a cycle, not added)

o Add (C-E, 6)

Final MST:
Edges: { (A-B, 1), (B-C, 2), (B-D, 4), (C-E, 6) }
Total Weight: 13

Network Flow Theory is a fascinating area within graph theory, and it's applicable to a variety
of real-world problems. Here's an overview of network flow concepts in graph theory:
Key Components
1. Flow Network:
o A directed graph where each edge has a capacity (maximum amount of flow it
can handle).
o Contains a source node ss (where flow originates) and a sink node tt (where
flow terminates).
2. Flow:
o Assignment of flow to each edge, respecting the capacity constraint.
o The amount of flow into a node equals the amount of flow out of it, except for
the source and sink nodes.

Important Problems and Theorems


1. Maximum Flow Problem:
o Find the maximum possible flow from the source to the sink in a flow network.
2. Min-Cost Max-Flow Problem:
o Find the maximum flow from the source to the sink with the minimum possible
cost.
3. Max-Flow Min-Cut Theorem:
o States that the maximum flow in a network is equal to the capacity of the
minimum cut, which is the smallest set of edges that, if removed, would
disconnect the source from the sink.

Max-Flow Min-Cut Theorem


Definition:
The Max-Flow Min-Cut Theorem states that in any flow network, the maximum value of the
flow from the source to the sink is equal to the total capacity of the edges in the smallest
(minimum) cut that separates the source and the sink.
Key Components:
 Flow Network: A directed graph where each edge has a capacity, and each edge
receives a flow that is subject to the capacity constraint.
 Source (s): The starting point of the flow.
 Sink (t): The endpoint where the flow is collected.
 Flow (f): The amount of flow passing through an edge.
 Cut: A partition of the vertices into two disjoint subsets such that the source is in one
subset and the sink is in the other.
 Capacity of a Cut: The sum of the capacities of the edges that are directed from the
source's subset to the sink's subset.
 Minimum Cut: The cut with the smallest capacity among all possible cuts.
Theorem Statement:
For any flow network, the value of the maximum flow is equal to the capacity of the minimum
cut.
Maximum Flow=Minimum Cut Capacity
Proof Outline:
1. Augmenting Path: An augmenting path is a path from the source to the sink in the
residual graph where additional flow can be pushed.
2. Flow Value: The value of the flow is equal to the sum of the flow values on the edges
leaving the source.
3. Cut Capacity: Consider a cut that separates the source and the sink. The capacity of
this cut is the sum of the capacities of the edges crossing the cut.
4. Equality: Prove that the maximum flow value and the minimum cut capacity are
equal using the properties of the residual graph and augmenting paths.
Applications:
 Telecommunications: Ensuring efficient data transfer through networks.
 Transportation: Optimizing traffic flow and logistics.
 Resource Allocation: Managing tasks and resources in project management.
 Sports: Fair scheduling and determining standings in tournaments.
Example:
Consider a network where nodes represent locations and edges represent paths with certain
capacities. The Max-Flow Min-Cut Theorem can be used to determine the maximum number
of goods that can be transported from a central depot (source) to a remote warehouse (sink)
through the network of roads.

Algorithms
1. Ford-Fulkerson Algorithm:
o An iterative algorithm to compute the maximum flow in a flow network by
finding augmenting paths and increasing the flow until no more augmenting
paths are found.
Applications
 Telecommunications: Routing data efficiently through networks.
 Transportation: Optimizing traffic flow in logistics and supply chains.
 Project Management: Scheduling and resource allocation.
 Sports: Determining team standings and tournament scheduling.
Example of Maximum Flow Problem
Consider a network where nodes represent locations and edges represent paths with certain
capacities. The goal is to maximize the flow of goods from a central depot (source) to a
remote warehouse (sink).

You might also like