인접성 매트릭스 이웃 확장하기

Question

인접 매트릭스가 있습니다. 이미의 이웃이 이웃 추가 된 존재 예를 들어, 다음,

+---+-------------------------------+ 
| | 1  2  3  4  5 | 
+---+-------------------------------+ 
| 1 | 0  1  0  0  0 | 
| 2 | 1  0  0  0  1 | 
| 3 | 0  0  0  1  0 | 
| 4 | 0  0  1  0  1 | 
| 5 | 0  1  0  1  0 | 
+---+-------------------------------+ 

는 우리가 어떻게 각 요소 (행 또는 열)에 대한 루프에 대한없이 다음 인접 행렬, 을 추출 할 수 있습니다? 예를 들어, 요소 3에는 인접 요소 인 4이 있으므로 새 인접성 행렬에서 요소 3은 인접 요소에 4 및 5 요소를 갖습니다.

+---+-------------------------------+ 
| | 1  2  3  4  5 | 
+---+-------------------------------+ 
| 1 | 0  1  0  0  1 | 
| 2 | 1  0  0  1  1 | 
| 3 | 0  0  0  1  1 | 
| 4 | 0  1  1  0  1 | 
| 5 | 1  1  1  1  0 | 
+---+-------------------------------+ 

안부,

토트.

Answer 1

A는, 다음 원하는 매트릭스 A2는, 당신의 인접 행렬의 경우 여기서

A2 = (A+A^2) > 0 

이있는 인접 행렬의 제곱은 s_ij 길이의 경로의 수는 구성 요소 s_ij을 가지고 있기 때문에 2 개는 i와 j 사이에 있습니다. (In fact (A^n)_ij is the number of paths from i to j of length n).

따라서 길이가 2 인 경로로 연결된 모든 쌍을 포함하는 A^2에 A (길이가 1 인 경로로 연결된 모든 쌍이 들어 있음)를 추가하면 길이가 1 인 경로 수를 얻게됩니다 또는 2. (이 경우 긍정적 인 경우에만주의를 기울이십시오). 길이가 2 인 경로는 이웃 노드의 경로입니다.