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

프로그래밍 경험이 거의 없으므로 연습을 위해 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 개가 발견됩니다. 나는 모서리가없는 이유를 모른다. 그 열 번호와 행 번호의 차이에 따라 가장자리를 할당하는 것은 웹 사이트 에서처럼 "정점 간 차이"와 같지 않다고 생각합니다. 대신 무엇을해야합니까?

다음 연습은 그래프의 삼각형 수를 세는 것입니다. 어떻게해야하는지에 대한 아이디어가 있지만 힌트를 얻을 수 있을까요?

출처

2017-12-31 Paul Cusson

구성을 행렬의 한 삼각형으로 제한하고 있지만 연결된 노드의 색인 쌍 구성을 행렬의 다른 절반으로 제한해서는 안됩니다. - 인쇄물을 보아라 : 'i-j |> 8'과 색인 쌍이 틀렸을 것이다. – laune

구성을 행렬의 한 삼각형으로 제한하고 있지만 연결된 노드의 인덱스 쌍 구성을 행렬의 다른 부분, 즉 대각선 "스트립"으로 구성하지 않을 수 있습니다 (|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){

출처

2017-12-31 06:05:42 laune

아, 네 말이 맞아. 겹치는 부분이 있어야 해. 왜냐하면 여기에 두 배가 아닌 9 개가 더 늘어날 것이기 때문이다. 또한, 하반부 대신 전체 인접 매트릭스를 구성하면 더 간단할까요? –

확장 테스트는 아래쪽 삼각형 바깥쪽에 배열 요소를 생성하지 않습니다. -'graph [i] [j]'의 설정을 추가하기 때문에 전체 행렬을 채우면 많이 변하지 않을 것입니다. – laune

감사합니다! 나는 지금 모든 68를 센다! 나는 지금 두 번째 부분을 다룰 것이다. 나는 그것을 보았다. 그것은 예상보다 훨씬 더 계산하기 어려운 문제이다. –

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

답변

관련 문제