Network Problems

Concept of Network Problems

  • Network problems are mathematical and logical problems that require the optimisation of routes through points known as vertices.
  • The vertices are interconnected with paths known as edges or arcs, and the complete arrangement is called a graph or network.
  • Directed graphs and undirected graphs are two types of graphs used in solving network problems. Directed graphs have edges with defined directions while undirected graphs don’t.

Simplex Algorithm

  • The simplex algorithm is a method to solve optimisation problems in linear programming.
  • Designed by George Dantzig, it is an iterative method for obtaining the most optimal solution for a problem.
  • An important concept in the simplex algorithm is the feasible region, which defines all the possible solutions to the problem.

Types of Network Problems

  • The different types of network problems include the shortest path problem, transportation problem, travelling salesman problem, minimum cost flow problem, and minimum spanning tree problem.

Shortest Path Problem

  • The shortest path problem involves finding the shortest possible route from one vertex to another within a graph.
  • Dijkstra’s algorithm is a common approach used to solve this problem, where the path with the smallest total weight is identified.

Travelling Salesman Problem

  • The travelling salesman problem poses the challenge of finding the shortest possible route that covers all vertices and returns to the original vertex.
  • This problem is known to be an NP-hard problem - a problem whose solution cannot be found in polynomial time.

Minimum Cost Flow Problem

  • The minimum cost flow problem aims to find the cheapest way to transport a certain amount of flow through a network from a source to a sink.
  • Popular methods to solve this include the Simplex Algorithm and Network Simplex Algorithm.

Practical Application and Exercises

  • Real-life scenarios such as logistics planning or networking can aid in understanding the concept of network problems.
  • Implementing the Simplex Algorithm or Dijkstra’s Algorithm in coding exercises can help reinforce understanding.
  • Using contrasting examples to visualise different network problem types supports cognitive understanding.