Graph Magics

Practical applications of Graph Algorithms

Graphs are applied widely in our days. They are used in economy, aeronautics, physics, biology (for analyzing DNA), mathematics and other areas.
This page describes some of the applications of a collection of algorithms (all of them are available in Graph Magics).

Shortest Path:
View algorithm

This is probably the most often used algorithm. It may be applied in situations where the shortest path between 2 points is needed.
Examples of such applications would be:
  • Computer games - finding the best/shortest route from one point to another.
  • Maps - finding the shortest/cheapest path for a car from one city to another, by using given roads.
  • May be used to find the fastest way for a car to get from one point to another inside a certain city. E.g. satellite navigation system that shows to drivers which way they should better go.
Minimal Spanning Tree:
View algorithm
  • Consider some communications stations (for telephony, cable television, Internet etc.) and a list of possible connections between them, having different costs. Find the cheapest way to connect these stations in a network, so that a station is connected to any other (directly, or through intermediate stations). This may be used for example to connect villages to cable television, or to Internet.
  • The same problem, but instead of connecting communications stations - villages are to be connected with roads.
Eulerian Path/Circuit:
View algorithm
  • A postman has to visit a set of streets in order to deliver mails and packages. It is needed to find a path that starts and ends at the post-office, and that passes through each street (edge) exactly once. This way the postman will deliver mails and packages to all streets he has to, and in the same time will spend minimum efforts/time for the road.
Note that not all graphs have an eulerian circuit. If needed - the algorithm for Chinese Postman Problem can be used.

Chinese Postman Problem:
  • The same problem with the postman as above, but instead of visiting each street (vertex) exactly once, the postman can visit them more than once if needed. Thus the path should pass through each street at least one time and should have the minimum cost.
  • Drawing a circuit with a plotter in a fastest possible way, or with a minimum cost.
  • It may be used to determine the cheapest path for garbage collection, street cleaning, or snow removal.
  • Also applied in routing robots, analysing DNA, and others.
Hamiltonian Path/Circuit:
  • The same problem with the postman as above, but instead of visiting a set of streets (edges), he has to visit each point (house) exactly once.
Network Flows:
  • With Maximum Flow algorithm it is possible to find the most loaded roads or rails in a certain transportation network, and also to determine its maximum intensivity. This information may be then used to improve the traffic situation in those places.
Optimal Graph Coloring:
  • This algorithm may be used to color a map with a minimum number of colors.
Graph Median:
View algorithm
  • A warehouse should be placed in a city (a region) so that the sum of shortest distances to all other points (regions) is minimal. This is useful for lowering the cost of transporting goods from a warehouase to clients.
    Same thing can be considered for selecting the place of a shop, market, office and other buildings.
Graph Center:
View algorithm
  • Suppose that a hospital, a fire department, or a police department, should be placed in a city so that the farthest point is as close as possible. For example a hospital should be placed in such a way that an ambulance can get as a fast as possible to the farthest situated house (point).
Copyright 2004-2014 Dumitru Ciubatii. All rights reserved.
Protected by copyright laws and international treaties.