계기

올해의 기본 정보 기술자 시험에 인접 행렬의 문제가 출제되었습니다.
단지 읽고 있었다 개미 책 에 그래프의 설명이 실려 있었으므로, 정리해 보았습니다.

그래프란?

물건이나 상태와 같은 대상끼리의 연결 방법을 나타내기 위한 표현법.
그래프는 정점(노드)과 모서리(에지)로 구성됩니다.

변에 방향이 없는 그래프를 무향 그래프, 변에 방향이 있는 그래프를 유효 그래프라고 합니다.

인접 행렬 및 무향 그래프

인접 행렬에서는 |V|×|V|의 2차원 배열 g로 그래프를 표현합니다. g[i][j]는 i번째 정점과 j번째 정점 간의 관계를 나타낼 수 있습니다.

무향 그래프의 경우는 「i번의 정점과 j번째의 정점이 변에서 연결되어 있는지」의 정보만 있으면 되므로, g[i][j]와 g[j][i]의 값을 정점 i와 정점 j가 변에서 연결되어 있으면 1, 그렇지 않으면 0이 되는 것으로 무향 그래프를 표현합니다.

유향 그래프에서는 정점에서 정점으로의 방향을 나타내기 때문에, g[i][j]=g[j][i]는 되지 않는다.
⇒무향 그래프에서는 g[i][j]=g[j][i]가 됩니다.
행렬에 대각선을 그리면 대상이 되고 같은 내용이 됩니다.

예 4×4의 인접 행렬


i\j
1
2
3
4


1
0
1
0
0

2
1
0
1
1

3
0
1
0
0

4
0
1
0
0


예 위의 무향 그래프

령화 원년 가을기 기본 정보 기술자 시험 오전 질문 3

【문제】
노드와 노드 사이에 에지의 유무를 인접 행렬을 사용하여 나타낸다. 어느 무향 그래프의 인접 행렬이 다음의 경우, 그래프로 표현한 것은 어느 것인가. 여기서, 노드는 인접 행렬의 행과 열을 대응시키고, 노드 사이에 에지가 존재하는 경우는 1, 에지가 존재하지 않는 경우는 0으로 나타낸다.



【해결 방법】
왼쪽에서 노드의 연결을 확인하고, 부정해를 제외해 간다.
· [b] [c] = [c] [b] = 1, [b] [d] = [d] [b] = 1에서 노드 b는 노드 c와 d에 연결됩니다.
⇒⇒선택사항:아 부정해
· [c] [d] = [d] [c] = 1, [c] [e] = [e] [c] = 1에서 노드 c는 노드 b 이외에 d와 e에 연결됩니다.
⇒⇒선택사항:이 부정해
· 노드 d는 b와 c 이외에 연결되지 않습니다.
⇒⇒선택사항:에이 부정해

⇒⇒응답 선택지:우

읽었던 책

프로그래밍 콘테스트 챌린지북 [제2판]

마지막으로

전회보다 사이가 비었습니다만, 이번이 2회째의 기사가 됩니다.
시간이 있으면 실제로 프로그래밍을 한 다음 기사를 가필합니다.

기사의 내용에 오류나 문제등이 있으면, 정정합니다.

좋으면 코멘트 부탁드립니다.