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

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.

Value

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

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.

References

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

Also see overview

Author

C.B. Hurley and R.W. Oldford

Examples

require(PairViz)

zigzag(7)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,]    1    2    7    3    6    4    5
#> [2,]    2    3    1    4    7    5    6
#> [3,]    3    4    2    5    1    6    7
#> [4,]    4    5    3    6    2    7    1
hpaths(7) # the rows form a decomp. into hamiltonian cycles
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,]    1    2    3    7    4    6    5
#> [2,]    1    3    4    2    5    7    6
#> [3,]    1    4    5    3    6    2    7

# Now concatenate the rows and close the path
hpaths(7,matrix=FALSE)
#>  [1] 1 2 3 7 4 6 5 1 3 4 2 5 7 6 1 4 5 3 6 2 7 1

# Form a decomposition into hamiltonian cycles- 
# this decomposition is not exact, as the last row duplicates edges
hpaths(7,cycle=FALSE)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,]    1    2    7    3    6    4    5
#> [2,]    2    3    1    4    7    5    6
#> [3,]    3    4    2    5    1    6    7
#> [4,]    4    5    3    6    2    7    1

# For even n, the default is a decomposition into hamiltonian paths, not cycles.
hpaths(6)
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    1    2    6    3    5    4
#> [2,]    2    3    1    4    6    5
#> [3,]    3    4    2    5    1    6

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

hpaths(6,cycle=TRUE)
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    1    2    3    6    4    5
#> [2,]    1    3    4    2    5    6
#> [3,]    1    4    5    3    6    2

# If you want to specify the first hamiltonian of the decomposition, use
hpaths(1:7)
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,]    1    2    3    4    5    6    7
#> [2,]    1    3    5    2    7    4    6
#> [3,]    1    5    7    3    6    2    4