Graph Magics

 Home Overview Gallery Updates & News Download Purchase Contacts

 Algorithms Applications of Graph Algorithms

 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-2021 Dumitru Ciubatii. All rights reserved.
Protected by copyright laws and international treaties.