Кодирование матрицы смежности для графа в 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 единиц, что я и пытаюсь построить, но когда я их вручную подсчитываю, при печати я нахожу 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){