|
MAPLE
|
f:= proc(N)
local verts, Rverts, edg, cons, i, j, e;
verts:= [seq(seq([i, j], i=1..N), j=1..N)]:
for i from 1 to N^2 do Rverts[op(verts[i])]:= i od:
edg:= {seq(seq({Rverts[i, j], Rverts[i+1, j+2]}, i=1..N-1), j=1..N-2),
seq(seq({Rverts[i, j], Rverts[i+2, j+1]}, i=1..N-2), j=1..N-1),
seq(seq({Rverts[i, j], Rverts[i+1, j-2]}, i=1..N-1), j=3..N),
seq(seq({Rverts[i, j], Rverts[i+2, j-1]}, i=1..N-2), j=2..N)}:
cons:= {seq(x[e[1]]+x[e[2]]<=1, e=edg),
seq(x[i]+add(`if`(member({i, j}, edg), x[j], 0), j=1..N^2)>=1, i=1..N^2)}:
Optimization:-Minimize(add(x[i], i=1..N^2), cons, assume=binary)[1]
end proc:
|