Math Archives Homepage


LS. Prof. A. Bachem
Universität zu Köln
Weyertal 80
D-50931 Köln

This is a collection of eleven programs to study problems in graph theory and combinatorics.

The graphs considered for the "edge coloring problem" are nondirected without loops and multiple edges. A graph G is said to be r-cromatic if if its edges can be colored with r colors in such a way that two edges with a common endnode always receive different colors. The smallest number r for which the graph G is r-chomatic is called chomatic Index X'(G) and finding this index is referred to as the 'coloring problem'.
Is it possible to color any geographical map with four colors so that any two countries with a common frontier have different colors? This famous problem, solved by Appel and Haken reduces to showing that every planar graph is 4-chromatic. It is possible to associate with each geographical map a graph. Coloring the faces of this graph is done by coloring the nodes of the corresponding dual graph.
A graph G is said to be 'r-chromatic' if its nodes can be colored with r colors in such a way so that no two adjacent nodes are of the same color. The smallest number r for which the graph is r-chromatic is called the 'chromatic number X(G)' of the graph and finding this number is referred to as the 'coloring problem'.
There are two network flow algorithms represented: the Algorithm of Edmonds and Karp and the Algorithm of Shiloach & Vishkin. convhull.exe Find the convex hull of a finite set of points in 2 or 3 dimensional space or of a finite cut of halfspaces in 3 dimensional space.
Let G=(V,E) be an undirected graph with a finite set E of edges and a finite set V of nodes. Each edge (i,j) has a real-valued weight w(i,j). A matching M in G is a set of edges no two of which have a common node. The size M of M is the number of edges it contains (its cardinality), the weight of M is the sum of its edge weights. The MAXIMUM CARDINALITY MATCHING problem is to find a matching of maximum size. The MINIMUM WEIGHTED MATCHING problem is to find a matching of minimum weight.
When a Shortest Path problem is solved by traversing the arcs of a given (di)graph and recording the information so obtained, the underlying technique is called a combinatorial or graph traversal technique. In this CATbox application the algorithms of Johnson, of Mehlhorn and of Bellman - Ford are implemented.
The planarity testing program PLANAR is an application of the program that tests whether a given (di)graph is planar and visualizes the concept of the testing algorithm.
The Vehicle Routing and Scheduling Problem with time window constraints and combined pick up and delivery is to find a set of vehicle routes so as to minimize the total distance traveled and the number of tours such that the total demand on each route does not exceed the truck capacity at all times and each customer is visited in one of its time windows on exactly one route.
To visualize the geometrical ideas and interpretations of combinatorial methods to solve or approximate the NP-complete Steiner problem in any kind of directed graph.
Application of seven algorithms (NEAREST NEIGHBOR, FURTHEST INSERT, NEAREST INSERT, SWEEP, SPACEFILL.CURVE, SCEC, RANDOM TOUR) to tackle the Travelling Salesman Problem.
These programs are contained in the two zipped files and
(modified from the documentation)
Download [126 KB].

Download [143 KB].

Look at the readme file from the program.

Home page for CATBox.