|
This is a collection of eleven programs to study problems in
graph theory and combinatorics.
- coledge.exe
- 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'.
- colface.exe
- 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.
- colnode.exe
- 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'.
- flows.exe
- 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.
- cmatch.exe
- 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.
- paths.exe
- 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.
- planar.exe
- 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.
- vr.exe
- 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.
- steiner.exe
- 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.
- hacy.exe
- 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 catbox1.zip
and catbox2.zip.
(modified from the documentation)
|
Download