Ramsey's theorem: Difference between revisions
m (tidy up, mark long line (don't know whether I can line-break mathprog code)) |
(→{{header|REXX}}: added the REXX language. -- ~~~~) |
||
Line 71: | Line 71: | ||
The solution may be viewed on [[Solution Ramsey Mathprog|this page]]. |
The solution may be viewed on [[Solution Ramsey Mathprog|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=<tt>1</tt>, unconnected=<tt>0</tt>) is shown. |
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=<tt>1</tt>, unconnected=<tt>0</tt>) is shown. |
||
=={{header|REXX}}== |
|||
{{trans|C}} |
|||
<lang rexx>/*REXX programs finds and displays a 17 node graph such that any four */ |
|||
/*────── nodes are neither totally connected nor totally unconnected.*/ |
|||
@.=0 /*initialize the node graph to 0.*/ |
|||
do d=0 for 17; @.d.d=2; end /*set the diagonal elements to 2.*/ |
|||
k=1 |
|||
do while k<=8 |
|||
do i=0 for 17 /*process each column in array. */ |
|||
j= (i+k) // 17 /*set a row,col and col,row. */ |
|||
@.i.j=1; @.j.i=1 /*set two array elements to one. */ |
|||
end /*i*/ |
|||
k=k*2 /*double the value of K each loop*/ |
|||
end /*while k≤8*/ |
|||
do r=0 for 17; _=; do c=0 for 17 /*show each row, build col by col*/ |
|||
_=_ @.r.c /*add this column to the row. */ |
|||
end /*c*/ |
|||
say left('',9) translate(_,'-',2) /*display the constructed row. */ |
|||
end /*r*/ |
|||
/*stick a fork in it, we're done.*/</lang> |
|||
'''output''' |
|||
<pre style="overflow:scroll"> |
|||
- 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 - |
|||
</pre> |
Revision as of 23:56, 17 December 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.
REXX
<lang rexx>/*REXX programs finds and displays a 17 node graph such that any four */ /*────── nodes are neither totally connected nor totally unconnected.*/ @.=0 /*initialize the node graph to 0.*/
do d=0 for 17; @.d.d=2; end /*set the diagonal elements to 2.*/
k=1
do while k<=8 do i=0 for 17 /*process each column in array. */ j= (i+k) // 17 /*set a row,col and col,row. */ @.i.j=1; @.j.i=1 /*set two array elements to one. */ end /*i*/ k=k*2 /*double the value of K each loop*/ end /*while k≤8*/
do r=0 for 17; _=; do c=0 for 17 /*show each row, build col by col*/ _=_ @.r.c /*add this column to the row. */ end /*c*/
say left(,9) translate(_,'-',2) /*display the constructed row. */ end /*r*/ /*stick a fork in it, we're done.*/</lang>
output
- 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 -