networks2

 Minimum Spanning Tree Problem

A spanning tree connects all of the nodes in a graph and has no cycles.  There are numerous ways to select connecting arcs to create a spanning tree.  A minimum spanning tree is a spanning tree that has the shortest total length of connecting arcs. It may not be unique.

In the graph below, the arcs are labeled with distances between the nodes that they are connecting. The animation demonstrates Prim's Algorithm for finding a minimum spanning tree.



Popular posts from this blog

Contents

Chapter 1: Introduction.  An introduction to the process of optimization and an overview of the major topics covered in the course.  Last revision: December 2020 . Chapter 2: Introduction to Linear Programming.  The basic notions of linear programming and the simplex method. The simplex method is the easiest way to provide a beginner with a solid understanding of linear programming.  Last revision: December 2020. See animation  LP1 . A good  article on formulating LPs  by Gerry Brown and Rob Dell. Example questions with solutions . March 4, 2021. Chapter 3: Towards the Simplex Method for Efficient Solution of Linear Programs.  Cornerpoints and bases. Moving to improved solutions.  Last revision: December 2020 . See animation  LP2 . Chapter 4: The Mechanics of the Simplex Method.  The tableau representation as a way of illustrating the process of the simplex method. Special cases such as degeneracy and unboundedness.  Last revis...
Read more