1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | % % Diamond-free Degree Sequence (CSPLib #50) in MiniZinc. % % """ % Proposed by Alice Miller, Patrick Prosser % % Given a simple undirected graph G=(V,E), where V is the set of vertices and E the set of % undirected edges, the edge {u,v} is in E if and only if vertex u is adjacent to vertex v∈G. % The graph is simple in that there are no loop edges, i.e. we have no edges of the form {v,v}. % Each vertex v∈V has a degree dv i.e. the number of edges incident on that vertex. Consequently % a graph has a degree sequence d1,…,dn, where di>=di+1. A diamond is a set of four vertices % in V such that there are at least five edges between those vertices. Conversely, a graph is % diamond-free if it has no diamond as an induced subgraph, i.e. for every set of four vertices % the number of edges between those vertices is at most four. % % In our problem we have additional properties required of the degree sequences of the graphs, % in particular that the degree of each vertex is greater than zero (i.e. isolated vertices % are disallowed), the degree of each vertex is modulo 3, and the sum of the degrees is % modulo 12 (i.e. |E| is modulo 6). % % The problem is then for a given value of n, produce all unique degree sequences d1,…,dn such % that % % * di≥di+1 % * each degree di>0 and di is modulo 3 % * the sum of the degrees is modulo 12 % * there exists a simple diamond-free graph with that degree sequence % % Below, as an example, is the unique degree sequence forn=10 along with the adjacency matrix of % a diamond-free graph with that degree sequence. % % n = 10 % 6 6 3 3 3 3 3 3 3 3 % % 0 0 0 0 1 1 1 1 1 1 % 0 0 0 0 1 1 1 1 1 1 % 0 0 0 0 0 0 0 1 1 1 % 0 0 0 0 1 1 1 0 0 0 % 1 1 0 1 0 0 0 0 0 0 % 1 1 0 1 0 0 0 0 0 0 % 1 1 0 1 0 0 0 0 0 0 % 1 1 1 0 0 0 0 0 0 0 % 1 1 1 0 0 0 0 0 0 0 % 1 1 1 0 0 0 0 0 0 0 % % """ % % Note: Most FlatZinc solver yields all solutions of x even when % degree is the only in output. % % The exception is the Gecode solver, which just prints the % distinct degrees proviso: % - only degrees is in the output % - only degrees is in the labeling (or "solve satisfy") % % This MiniZinc model was created by Hakan Kjellerstrand, hakank@gmail.com % See also my MiniZinc page: http://www.hakank.org/minizinc/ % include "globals.mzn" ; int : n = 11; % decision variables array [1 .. n,1 .. n] of var 0 .. 1: x; array [1 .. n] of var 1 .. n: degrees; % solve satisfy; solve :: int_search(degrees, first_fail, indomain_split, complete) satisfy ; constraint forall(i,j,k,l in 1 .. n where i < j /\ j < k /\ k < l) ( x[i,j] + x[i,k] + x[i,l] + x[j,k] + x[j,l] + x[k,l] <= 4 ) /\ forall(i in 1 .. n) ( degrees[i] = sum ([x[i,j] | j in 1 .. n]) /\ degrees[i] mod 3 = 0 % no loops /\ x[i,i] = 0 ) /\ % undirected graph forall(i,j in 1 .. n) ( x[i,j] = x[j,i] ) /\ sum (degrees) mod 12 = 0 % symmetry breaking /\ decreasing(degrees) /\ lex2(x) ; output [ "degrees: " , show (degrees), "\n" ] % ++ % [ % if j = 1 then "\n" else " " endif ++ % show(x[i,j]) % | i,j in 1..n % ] ; |