Graph Magics
Partners
DocsPalFree online file Converter and Viewer

 Shortest Path  Finds the shortest/cheapest path between two vertices.
View algorithm
Finding shortest paths between every pair of vertices
 Minimal Spanning Tree  Finds a connected ayclic subgraph that contains all vertices of the graph and has the smallest sum of
costs of its edges.
View algorithm
 Eulerian Path/Circuit  Finds a path/circuit that visits every edge exactly once.
View algorithm
 Chinese Postman Problem  Finds a circuit of minimum cost that starts and ends at selected vertex, passing through each edge
at least once.
 Hamiltonian Path/Circuit  Finds a path/circuit that passes through each vertex exactly once.
 Maximum Flow  Finds the maximum amount of flow (e.g. water) that can flow from start vertex (source) to destination vertex (sink).
 Maximum Flow of Minimum Cost  Finds the maximum amount of flow (e.g. water) that can flow from start vertex (source) to destination
vertex (sink) with minimum cost.
 Minimum Cut  Finds the minimum number of edges that must be cut (deleted) so that start vertex is isolated from destination
vertex (i.e. they are not connected directly or indirectly).
 Maximal Subset of Independent Vertices  Finds the largest subset of vertices that don't have any edge between them.
 Maximum Clique (complete subgraph)  Finds the largest subset of vertices that are connected all to each other.
 Optimal Graph Coloring  Colors the graph with a minimum number of colors, so that no two neighbour vertices have the same color.
 Graph Median  Finds the vertex for which the sum of lengths of shortest paths to all other vertices is the smallest.
View algorithm
 Graph Center  Finds the vertex for which the length of shortest path to the farthest vertex is the smallest.
View algorithm

