在java中编码图形的邻接矩阵并计算三角形

Question

我的编程经验很少，所以对于实践，我想通过用二维数组编码它的邻接矩阵来“构造”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){