Javaでグラフの隣接行列をコーディングし、三角形を数える

Question

私はプログラミング経験がほとんどないので、練習のために、2次元配列で隣接行列をコーディングしてJavaでグラフを構築したかったのです。具体的には、https://www.cut-the-knot.org/arithmetic/combinatorics/Ramsey44.shtmlという赤いグラフを作成したいのですが、コード化したものは、マトリックスのエッジが少なくて済むようになりました。ここで私はこれまで持っているものです。

のpublic static int型[] [] createGraph（）{

int[][] graph = new int[17][]; 
for(int i=0; i<17; i++){ 
    graph[i] = new int[i+1]; 
} 

for(int i = 0; i<17; i++){ 
    for(int j = 0; j<=i; j++){ 
    if(i-j == 1 || i-j == 2 || i-j == 4 || i-j == 8){ 
     graph[i][j] = 1; 

    } 
    } 
} 
return graph; 

グラフ内の68個のエッジがありますので、の下三角に68 1つのがあるはずです私が作ろうとしている隣接行列ですが、手作業で計算すると、それを印刷すると59個見つかります。なぜ辺が欠落しているのか分かりません。私は、列番号と行番号の違いに基づいてエッジを割り当てることは、ウェブサイトの「頂点の違い」と同じではないことを推測しています。代わりに私は何をすべきですか？

また、私の次の課題は、グラフの三角形の数を数えることです。私はそれをする方法について考えているが、ヒントを得ることができるだろうか？

Answer 1

構成をマトリックスの三角形に制限していますが、接続ノードのインデックスペアの構成をマトリクスの他の部分、つまり対角の「ストリップ」に|i-j| <= 8で制限することはできません。したがって、

if(i-j == 1 || i-j == 2 || i-j == 4 || i-j == 8 || 
    i-j == 9 || i-j == 13 || i-j == 15 || i-j == 16){