Scribd
Upload
111 views2 pages

Maximum Flow and Minimum Spanning Tree Analysis

The document describes a network flow problem and minimum spanning tree problem. It provides a graph with nodes and edges showing capacities and flows for the network flow problem and costs for the minimum spanning tree problem. The tasks are to find the maximum flow from node s to t in the network flow problem and find the minimum spanning tree in the graph for the minimum spanning tree problem.

Uploaded by

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

Maximum Flow and Minimum Spanning Tree Analysis

The document describes a network flow problem and minimum spanning tree problem. It provides a graph with nodes and edges showing capacities and flows for the network flow problem and costs for the minimum spanning tree problem. The tasks are to find the maximum flow from node s to t in the network flow problem and find the minimum spanning tree in the graph for the minimum spanning tree problem.

Uploaded by

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

Capacities are shown in the circles.

Start from the feasible flow shown


v2
10 in blue and find the maximum flow
3
7 10 from 𝑠 to 𝑡.
9
s 7
t At each iteration choose vertex vi
v1
10 3
v3
10 6
v5
labeled and not explored with
minimum index.
10
10 10
10 0
8
v4

0
Costs are shown in blue.
2 5 Find the minimum spanning tree.
v1 v2 v4
1
9
3

3
v3 v5

You might also like