Correct predictions are in blue. If we detect only a subset of a labelled sentence, we highlight the caught part as blue, the missing part light blue. False positives are in green and false negatives are in red.

Problem 050 (Diamond-free degree sequences) — Constraint detection

Given a simple undirected graph $ G = -LRB- V , E -RRB- $ , where $ V$ is the set of vertices and $ E$ the set of undirected edges , the edge -LCB- $ u , v $ -RCB- is in $ E$ if and only if vertex u is adjacent to vertex $ v \ in G$ . The graph is simple in that there are no loop edges , i.e. we have no edges of the form -LCB- $ v , v $ -RCB- . Each vertex $ v \ in 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 $ d_i > = d _ -LCB- i +1 -RCB- $ . 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 -LRB- i.e. isolated vertices are disallowed -RRB- , the degree of each vertex is modulo $ 3 $ , and the sum of the degrees is modulo $ 12 $ -LRB- i.e. $ | E | $ is modulo $ 6 $ -RRB- . The problem is then for a given value of $ n $ , produce all unique degree sequences $ d1 , - , dn $ such that $ d_i \ ge d _ -LCB- i +1 -RCB- $ ; each degree $ d_i > 0 $ and $ d_i $ is modulo $ 3 $ ; the sum of the degrees is modulo $ 12 $ ; there exists a simple diamond-free graph with that degree sequence .

Problem 050 (Diamond-free degree sequences) — Detection of the decisions and objects to be modeled

Given a simple undirected graph $ G = -LRB- V , E -RRB- $ , where $ V$ is the set of vertices and $ E$ the set of undirected edges , the edge -LCB- $ u , v $ -RCB- is in $ E$ if and only if vertex u is adjacent to vertex $ v \ in G$ . The graph is simple in that there are no loop edges , i.e. we have no edges of the form -LCB- $ v , v $ -RCB- . Each vertex $ v \ in 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 $ d_i > = d _ -LCB- i +1 -RCB- $ . 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 -LRB- i.e. isolated vertices are disallowed -RRB- , the degree of each vertex is modulo $ 3 $ , and the sum of the degrees is modulo $ 12 $ -LRB- i.e. $ | E | $ is modulo $ 6 $ -RRB- . The problem is then for a given value of $ n $ , produce all unique degree sequences $ d1 , - , dn $ such that $ d_i \ ge d _ -LCB- i +1 -RCB- $ ; each degree $ d_i > 0 $ and $ d_i $ is modulo $ 3 $ ; the sum of the degrees is modulo $ 12 $ ; there exists a simple diamond-free graph with that degree sequence .

Back to list