이번 글에서는 인접 행렬의 표현과 함께 인접 행렬에 대해 논의할 것입니다.
자바 해시맵이 뭐야?
인접 행렬 정의
그래프 이론에서 인접 행렬은 유한 그래프 구조를 설명하는 조밀한 방법입니다. 그래프 노드 간의 연관성을 매핑하는 데 사용되는 2D 매트릭스입니다.
그래프가 있는 경우 N 꼭지점의 개수인 경우 해당 그래프의 인접 행렬은 다음과 같습니다. nxn , 행렬의 각 항목은 한 꼭지점에서 다른 꼭지점까지의 모서리 수를 나타냅니다.
인접 행렬은 다음과 같이 불립니다. 연결 매트릭스 . 때로는 a라고도 불립니다. 꼭짓점 행렬 .
인접 행렬 표현
방향이 없는 그래프 G가 n개의 정점으로 구성된 경우 그래프의 인접 행렬은 n x n 행렬 A = [aij]이고 -로 정의됩니다.
ㅏij= 1 {V로부터 경로가 존재하는 경우나V에게제이}
ㅏij= 0 {그렇지 않은 경우}
인접 행렬과 관련된 몇 가지 중요한 사항을 살펴보겠습니다.
- 꼭지점 V 사이에 모서리가 있는 경우나그리고 V제이, 여기서 i는 행이고 j는 열입니다. 그러면 a의 값은ij= 1.
- 꼭지점 V 사이에 가장자리가 없는 경우나그리고 V제이, 다음의 값은ij= 0.
- 단순 그래프에 자체 루프가 없으면 정점 행렬(또는 인접 행렬)의 대각선이 0이어야 합니다.
- 인접 행렬은 방향이 없는 그래프에 대해 대칭입니다. i의 값이 다음과 같이 지정됩니다.일행과 j일열은 j의 값과 같습니다.일나 행일
- 인접행렬 자체를 곱한 경우, i에 0이 아닌 값이 존재하는 경우일행과 j일열, 그러면 V에서 오는 경로가 있습니다나V에게제이길이는 2에 해당합니다. 인접 행렬의 0이 아닌 값은 개별 경로의 수가 존재함을 나타냅니다.
참고: 인접 행렬에서 0은 두 노드 사이에 연관성이 없음을 나타내고, 1은 두 노드 사이에 연관성이 있음을 나타냅니다.
인접 행렬을 만드는 방법은 무엇입니까?
그래프가 있다고 가정하자 g ~와 함께 N 꼭지점의 개수인 경우 꼭지점 행렬(또는 인접 행렬)은 다음과 같이 지정됩니다.
다이애나 안쿠디노바
A=a열하나ㅏ12. . . . . ㅏ1nㅏ이십 일ㅏ22. . . . . ㅏ2n. . . . . . . . . ㅏn1ㅏn2. . . . . ㅏnn
어디에서ij꼭지점 i에서 j까지의 모서리 수와 같습니다. 위에서 언급한 것처럼 인접 행렬은 무방향 그래프에 대해 대칭이므로 무방향 그래프의 경우ij=a히히.
그래프가 단순하고 간선이나 다중 간선에 가중치가 없으면 인접 행렬의 항목은 0과 1이 됩니다. 자체 루프가 없으면 인접 행렬의 대각선 항목은 0이 됩니다.
이제 무향 그래프와 유향 그래프의 인접 행렬을 살펴보겠습니다.
무방향 그래프의 인접 행렬
무방향 그래프에서 간선은 방향과 연관되어 있지 않습니다. 무방향 그래프에서 정점 A와 정점 B 사이에 간선이 존재하면 정점은 A에서 B로, B에서 A로 이동할 수 있습니다.
아래의 방향이 없는 그래프를 고려하여 인접 행렬을 구성해 보겠습니다.
자바에서 날짜 형식 지정
그래프에서 자체 루프가 없음을 볼 수 있으므로 인접 행렬의 대각선 항목은 0이 됩니다. 위 그래프의 인접 행렬은 -
유방향 그래프의 인접 행렬
유향 그래프에서 간선은 순서쌍을 형성합니다. 모서리는 일부 정점 A에서 다른 정점 B로의 특정 경로를 나타냅니다. 노드 A를 초기 노드라고 하고 노드 B를 터미널 노드라고 합니다.
아래 방향 그래프를 고려하여 인접 행렬을 구성해 보겠습니다.
위 그래프에서 자체 루프가 없음을 알 수 있으므로 인접 행렬의 대각선 항목은 0이 됩니다. 위 그래프의 인접 행렬은 -
인접 행렬의 속성
인접 행렬의 일부 속성은 다음과 같습니다.
- 인접 행렬(Adjacency Matrix)은 (V의 위치에 숫자 0과 1이 있는 간단한 레이블 그래프를 나타내는 데 사용되는 행과 열을 포함하는 행렬입니다.나, 안에제이), 2개의 V가 존재하는지 여부에 따라나 그리고 V제이인접해 있습니다.
- 유향 그래프의 경우 정점 i와 V 사이에 간선이 존재하는 경우나정점 j 또는 V로제이, A[V의 값나][안에제이] = 1, 그렇지 않으면 값은 0이 됩니다.
- 무방향 그래프의 경우 정점 i와 V 사이에 간선이 존재하는 경우나정점 j 또는 V로제이, A[V의 값나][안에제이] = 1 및 A[V제이][안에나] = 1, 그렇지 않으면 값은 0이 됩니다.
인접 행렬에 대한 몇 가지 질문을 살펴보겠습니다. 아래 질문은 가중치가 부여된 무방향 그래프와 방향 그래프에 관한 것입니다.
참고: 각 가장자리에 가장자리의 가중치라고 하는 양수가 할당된 경우 그래프를 가중치 그래프라고 합니다.
질문 1 - 아래 무방향 가중치 그래프의 인접 행렬은 무엇입니까?
해결책 - 주어진 질문에는 자가 루프가 없으므로 위 그래프에 대한 인접 행렬의 대각선 항목이 0이 될 것이 분명합니다. 위 그래프는 가중 무방향 그래프입니다. 그래프 가장자리의 가중치는 인접 행렬의 항목으로 표시됩니다.
위 그래프의 인접 행렬은 다음과 같습니다.
질문 2 - 아래 방향 가중치 그래프의 인접 행렬은 무엇입니까?
해결책 - 주어진 질문에는 자가 루프가 없으므로 위 그래프에 대한 인접 행렬의 대각선 항목이 0이 될 것이 분명합니다. 위 그래프는 가중 방향 그래프입니다. 그래프 가장자리의 가중치는 인접 행렬의 항목으로 표시됩니다.
위 그래프의 인접 행렬은 다음과 같습니다.
터보 C++ 다운로드
이 글이 인접행렬을 이해하는데 도움이 되기를 바랍니다. 여기서는 인접 행렬의 생성 및 속성과 함께 인접 행렬에 대해 논의했습니다. 또한 가중치 부여 여부에 관계없이 유향 그래프나 무방향 그래프에서 인접 행렬을 형성하는 방법에 대해서도 논의했습니다.