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

Question

我的编程经验很少，因此为了练习，我想 "construct" 通过使用二维数组对其邻接矩阵进行编码来 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 个。我不知道为什么缺少边缘。我猜测根据列号和行号之间的差异分配边缘与网站中的 "difference between vertices" 不同。我应该怎么做？

另外，我的下一个练习是计算图中三角形的数量。我知道如何做到这一点，但我能得到提示吗？

Answer 1

您将构造限制为矩阵的一个三角形，但您不能将连接节点的索引对构造限制在矩阵的其他部分，即对角线 "strips" 和 |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){

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

Coding the adjacency matrix for a graph in java and counting triangles

java

graph-theory

adjacency-matrix