자바에서 그래프의 인접 행렬 코딩 및 삼각형 계산

Question

프로그래밍 경험이 거의 없으므로 연습을 위해 Java에서 그래프를 2 차원 배열로 인접 행렬을 코딩하여 "구성"하고 싶었습니다. 특히, 여기 https://www.cut-the-knot.org/arithmetic/combinatorics/Ramsey44.shtml에서 찾은 빨간색 그래프를 만들고 싶습니다. 그러나 내가 코딩 한 것보다 매트릭스에서 가장자리가 적습니다.

공용 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의가되어야한다 : 여기서 I는 지금까지이 무엇 인접 행렬을 만들었지 만 수동으로 계산하면 인쇄 할 때 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){