Ramsey's theorem: Difference between revisions
("clique" seems to be a misnomer) |
m (tidy up, mark long line (don't know whether I can line-break mathprog code)) |
||
Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
The task is to find a graph with 17 Nodes such that any 4 Nodes are neither totally |
The task is to find a graph with 17 Nodes such that any 4 Nodes are neither totally connected nor totally unconnected. |
||
connected nor totally unconnected. |
|||
=={{header|C}}== |
=={{header|C}}== |
||
Line 29: | Line 28: | ||
} |
} |
||
return 0; |
return 0; |
||
⚫ | |||
} |
{{out}} (17 x 17 connectivity matrix): |
||
<pre> |
<pre> |
||
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 |
- 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 |
||
Line 51: | Line 51: | ||
=={{header|Mathprog}}== |
=={{header|Mathprog}}== |
||
{{lines too long|Mathprog}} |
|||
<lang> |
|||
/*Ramsey 4 4 17 |
<lang>/*Ramsey 4 4 17 |
||
This model finds a graph with 17 Nodes such that no clique of 4 Nodes is either fully |
This model finds a graph with 17 Nodes such that no clique of 4 Nodes is either fully |
||
Line 65: | Line 65: | ||
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; |
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; |
end;</lang> |
||
⚫ | |||
This may be run: |
This may be run with: |
||
⚫ | |||
The solution may be viewed on [[Solution Ramsey Mathprog|this page]]. |
|||
⚫ | |||
⚫ | |||
The solution may be viewed on this page http://rosettacode.org/wiki/Solution_Ramsey_Mathprog |
|||
⚫ |
Revision as of 16:36, 20 May 2012
The task is to find a graph with 17 Nodes such that any 4 Nodes are 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 with: <lang bash>glpsol --minisat --math R_4_4_17.mprog --output R_4_4_17.sol</lang> The solution may be viewed on this page. In the solution file, the first section 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.