Generate a Random Two-Coloring of K[n];

Wm C Bauldry, April 1998

The routines below are:
   mat_K: adjacency matrix of K[n];
   V: vertex set for K[n]; on the unit circle
   edge_K: edge set for K[n];
   f01: random value 0 or 1
   C: random two-coloring matrix
   TwoColoring: a plot of the coloring generated by C
   GenerateGraph: draw side by side images of the two-coloring with complements hilighted

Usage: GenerateGraph(positive integer)

> mat_K := n -> matrix(n,n, (i,j)->if i<>j then 1 else 0 fi):
  
  V := n -> evalf([seq([cos(2*k*Pi/n), sin(2*k*Pi/n)],k=0..n)],3):
  
  edge_K := proc(n::posint)
   local i, m, j, edge, verts;
   m := mat_K(n);
   verts := V(n);
   edge := NULL;
   for i from 1 to n do
    for j from i+1 to n do
     if m[i,j]=1 then edge := edge, [verts[i],verts[j]] fi;
    od;
   od;
   RETURN([edge]);
   end:
  
  f01 := rand(0..1):
  C := n -> matrix(n,n, (i,j)-> if i<j then f01() else 0 fi):
  
  TwoColoring := proc(A)
  local d, edgeR, edgeB, i, j, v;
  d := linalg[rowdim](A);
  v := V(d):
  edgeR := NULL:
  edgeB := NULL:
  for i from 1 to d do
    for j from i+1 to d do
      if A[i,j] = 1 then
        edgeR := edgeR, [v[i],v[j]]
      else
        edgeB := edgeB, [v[i],v[j]] fi;
    od:
  od:
  RETURN([plot({edgeR}, scaling=constrained, thickness=3, color=red),
          plot({edgeB}, scaling=constrained, thickness=3, color=blue)]);
  end:
  
  GenerateGraph := proc(n::posint)
  local k, c, pltL, pltR;
  k := plots[display]([
    plot(edge_K(n), scaling=constrained, color=grey),
    plot(edge_K(n), style=point, symbol=circle, scaling=constrained, color=blue)], axes=none):
  c := TwoColoring(C(n));
  pltL := plots[display]([k, c[1]]):
  pltR := plots[display]([k, c[2]]): 
  RETURN(plots[display](matrix(1,2,[pltL, pltR])));
  end:
  
> GenerateGraph(9);

> GenerateGraph(15);

Today's Date:
Last Modified: - WmCB