hpaths: Hamiltonian paths on the complete graph on 1..n, using...

In PairViz: Visualization using Graph Traversal

Hamiltonian paths on the complete graph on 1..n, using Lucas-Walecki constructions.

Description

zigzag - Constructs hamiltonian paths where each pair (i,j) appears in at least one of the hamiltonians.

hpaths - Returns a hamiltonian decomposition on the complete graph with n nodes. See Details.

permute_hpaths - Returns a modified version of paths, where vertices are re-labelled so that the first hamiltonian is path1.

Usage

zigzag(n)
hpaths(n, matrix=TRUE,cycle=NULL,...)
permute_hpaths(path1,paths= hpaths(length(path1)), matrix=TRUE,...)

Arguments

n	a positive integer. For hpaths, n may also be a vector specifying the first hamiltonian.
matrix	if TRUE, returns a matrix where each row is a hamiltonian path, otherwise concatenates the rows into a vector.
cycle	If TRUE, returns hamiltonian cycles, i.e. every hamiltonian starts at the same node. If FALSE, returned paths are open. Defaults to TRUE for odd n,FALSE for even n.
path1	A vector- This will be the first hamiltonian of the returned hamiltonian decomposition.
paths	A matrix where each row is a hamiltonian.
...	Ignored.

Details

hpaths - From graph theory we know that for odd n, the complete graph decomposes into (n-1)/2 edge distinct hamiltonian cycles, while for even n the graph decomposes into n/2 edge distinct hamiltonian paths. The default behaviour of the function hpaths is to produce the cycle decomposition for odd n and the path decomposition for even n.

However, if a TRUE value is supplied as argument cycle, the returned paths are cycles, and the result is a true decomposition for odd n, but for even n the last hamiltonian has some duplicate edges. If a FALSE value is supplied as argument cycle, the returned paths are open, and the result is a true decomposition for even n, but for odd n the last hamiltonian has some duplicate edges.

Value

A numeric matrix where each row contains a permutation of 1..n, or these rows concatenated into a vector if matrix=FALSE.

Author(s)

C.B. Hurley and R.W. Oldford

References

D.E. Lucas (1892), Recreations Matematiques, Vol II. Gauthier Villars, Paris.

Also see overview

See Also

weighted_hpaths, eseq.

Examples

require(PairViz)

zigzag(7)
hpaths(7) # the rows form a decomp. into hamiltonian cycles

# Now concatenate the rows and close the path
hpaths(7,matrix=FALSE)

# Form a decomposition into hamiltonian cycles- 
# this decomposition is not exact, as the last row duplicates edges
hpaths(7,cycle=FALSE)

# For even n, the default is a decomposition into hamiltonian paths, not cycles.
hpaths(6)

# If cycles are required for even n, 
# the decomposition will not be exact and the last row duplicates edges

hpaths(6,cycle=TRUE)

# If you want to specify the first hamiltonian of the decomposition, use
hpaths(1:7)

PairViz documentation built on Aug. 12, 2022, 5:06 p.m.