Ramsey's theorem: Difference between revisions
(→{{header|REXX}}: added the REXX language. -- ~~~~) |
m (→{{header|REXX}}: added a comment in the OUTPUT section. -- ~~~~) |
||
Line 94: | Line 94: | ||
end /*r*/ |
end /*r*/ |
||
/*stick a fork in it, we're done.*/</lang> |
/*stick a fork in it, we're done.*/</lang> |
||
'''output''' |
'''output''' <br><br>('''17x17''' connectivity matrix): |
||
<pre style="overflow:scroll"> |
<pre style="overflow:scroll"> |
||
- 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 |
Revision as of 00:01, 18 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
(17x17 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 -