Graph Magics



Algorithms Descriptions

  • 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

 
Copyright © 2004-2024 Dumitru Ciubatii. All rights reserved.
Protected by copyright laws and international treaties.