Ramsey's theorem: Difference between revisions
No edit summary |
|||
Line 51: | Line 51: | ||
=={{header|Mathprog}}== |
=={{header|Mathprog}}== |
||
<lang> |
|||
An example in Mathprog may be found on this page http://rosettacode.org/wiki/Execute_Ramsey_Mathprog. |
|||
/*Ramsey 4 4 17 |
|||
This model finds a graph with 17 Nodes such that no clique of 4 Nodes is either fully |
|||
connected, nor fully disconnected |
|||
Nigel_Galloway |
|||
January 18th., 2012 |
|||
*/ |
|||
param Nodes := 17; |
|||
var Arc{1..Nodes, 1..Nodes}, binary; |
|||
clique{a in 1..(Nodes-3), b in (a+1)..(Nodes-2), c in (b+1)..(Nodes-1), d in (c+1)..Nodes} : 1 <= Arc[a,b] + Arc[a,c] + Arc[a,d] + Arc[b,c] + Arc[b,d] + Arc[c,d] <= 5; |
|||
end; |
|||
</lang> |
|||
This may be run: |
This may be run: |
||
glpsol --math R_4_4_17.mprog --output R_4_4_17.sol |
glpsol --minisat --math R_4_4_17.mprog --output R_4_4_17.sol |
||
(see page http://rosettacode.org/wiki/Category:Mathprog) |
|||
The solution may be viewed on this page http://rosettacode.org/wiki/Solution_Ramsey_Mathprog |
The solution may be viewed on this page http://rosettacode.org/wiki/Solution_Ramsey_Mathprog |
Revision as of 16:31, 19 January 2012
The task is to find a graph with 17 Nodes such that any clique of 4 Nodes is neither totally connected nor totally unconnected.
C
For 17 nodes, (4,4) happens to have a special solution: arrange nodes on a circle, and connect all pairs with distances 1, 2, 4, and 8. It's easier to prove it on paper and just show the result than let a computer find it (you can call it optimization). <lang c>#include <stdio.h>
int main() { int a[17][17] = Template:0; int i, j, k; char *mark = "01-";
for (i = 0; i < 17; i++) a[i][i] = 2;
for (k = 1; k <= 8; k <<= 1) { for (i = 0; i < 17; i++) { j = (i + k) % 17; a[i][j] = a[j][i] = 1; } }
for (i = 0; i < 17; i++) { for (j = 0; j < 17; j++) printf("%c ", mark[a[i][j]]); putchar('\n'); } return 0; }</lang>output (17 x 17 connectivity matrix):
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 0 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
Mathprog
<lang> /*Ramsey 4 4 17
This model finds a graph with 17 Nodes such that no clique of 4 Nodes is either fully connected, nor fully disconnected Nigel_Galloway January 18th., 2012
- /
param Nodes := 17; var Arc{1..Nodes, 1..Nodes}, binary;
clique{a in 1..(Nodes-3), b in (a+1)..(Nodes-2), c in (b+1)..(Nodes-1), d in (c+1)..Nodes} : 1 <= Arc[a,b] + Arc[a,c] + Arc[a,d] + Arc[b,c] + Arc[b,d] + Arc[c,d] <= 5;
end; </lang>
This may be run:
glpsol --minisat --math R_4_4_17.mprog --output R_4_4_17.sol
The solution may be viewed on this page http://rosettacode.org/wiki/Solution_Ramsey_Mathprog
In the mprog file each clique is named as st<xxxxxx>. A corresponding entry in the solution file identifies the number of nodes connected in this clique. In the second part of the solution the status of each arc in the graph, connected=1 unconnected=0 is shown.