graphau3

A graph in this context is a set of objects (called nodes or vertices - this program uses nodes) where some pairs of nodes are linked by arcs (also known as edges). The arcs are weighted, meaning there is a certain cost for traveling over them. This can be in terms of distance, time, cost or anything else. This program does not give units for arc weights though. Not to be confused with bar charts and line graphs you might see in excel.

A graph can represent a lot of problems. For example, you can think of a road map as being a graph, with nodes representing junctions and arcs representing roads. The weight of an arc could be the distance of that road in kilometers. Once as a graph, there are a number of algorithms to solve certain problems. For example Dijkstra's algorithm finds the shortest route from one node to another.

Currently implemented are the following algorithms:

• Dijkstra's algorithm for finding the shortest path.
• Kruskal's algorithm for finding the minimum spanning tree.
• Prim's algorithm for finding the minimum spanning tree.

To do:

• Chinese postman
• Traveling salesman
• Max flow = Min cut

for a more complete list of graph problems see wikipedia: http://en.wikipedia.org/wiki/Graph_theory#Problems_in_graph_theory