I have tried using the Edge coloring of a complete graph.
This problem turns into one of the special cases ( The case [r=2] ) of Baranyai’s theorem.
As it can be proved that there’s no solution for odd (N > 1
), this problem comes into “class one” graphs according to Vizing’s theorem . I have tried to implement it in O(N^2)
but sadly didn’t succeed. Has anyone approached this problem using Graphs and came up with an efficient solution?
For example
consider N = 6
As we need 2N -1
groups
(i > j) --> (N-1)
(i = j) -- > 1
(i < j) --> (N-1)
and the (i < j)
part of the matrix is
(1,2)(1,3)(1,4)(1,5)(1,6)
(2,3)(2,4)(2,5)(2,6)
(3,4)(3,5)(3,6)
(4,5)(4,6)
(5,6)
Consider a graph with 6 vertices and above 15 pairs as edges (complete graph ) we need to divide these 15 pairs into 5 (N -1)
groups (coloring) such that all 6 numbers occur in each group.
5 - coloring
(1,2) (3,4) (5,6)
(1,3) (2,5) (4,6)
(1,4) (2,6) (3,5)
(1,5) (2,4) (3,6)
(1,6) (2,3) (4,5)