행렬과 그래프 - 그래프를 행렬로 나타내기

그래프와 행렬의 관계에 대해서 알아보죠.

그래프를 행렬로 바꿔볼 거예요. 그래프를 행렬로 바꿨을 때 행렬이 그래프의 특징들을 잘 드러내는지도 알아볼 거예요. 행렬이 나타내는 그래프의 특징을 보고 그래프를 예상할 수 있어야 해요.

정말 어려울 것 같지만 따지고 보면 별거 아닌 내용이에요.

행렬과 그래프 - 그래프를 행렬로 나타내기

다음과 같은 그래프가 있다고 해보죠.

그래프를 행렬로 나타내기

한 점이 다른 점과 변으로 연결되어 있으면 1, 연결되어 있지 않으면 0이라고 써서 표로 나타내 보죠. 예를 들어 A는 B와 변으로 연결되어 있으니까 1, D와는 변으로 연결되어 있지 않으니까 0이라고 쓰는 거예요.

그래프를 표로 나타내기
	A	B	C	D
A	0	1	1	0
B	1	0	1	0
C	1	1	0	1
D	0	0	1	0

이번에는 이 표를 행렬로 나타내보죠.

4차 정사각형렬이네요. (꼭짓점의 개수) × (꼭짓점의 개수) 행렬이죠.

이 행렬은 왼쪽 위에서 오른쪽 아래로 그어지는 대각선에 대해서 대칭이에요. A와 B가 변으로 연결되어 있으면 B와 A도 연결되어 있어서 같은 값을 가지니까요.

행렬의 성분으로 표현하자면 (i, j)의 성분 = (j, i)의 성분이 되는 거예요.

반대로 행렬만 보고 그래프의 특징을 알아낼 수 있나요?

예를 들어 이 행렬은 4차 정사각행렬이에요. 꼭짓점이 4개 있다는 뜻이에요.

변의 개수를 알 수 있을까요? 변은 꼭짓점과 꼭짓점을 연결한 선이에요. 행렬에서 1이 의미하는 건 두 꼭짓점 사이가 변으로 연결되어 있다는 뜻이죠? 그래서 행렬에 있는 1을 모두 더하면 돼요. 하지만 AB와 BA를 모두 1로 나타냈으니까 중복되는 걸 빼려면 행렬에서 1을 모두 더한 값을 2로 나눠줘야 하죠.

변의 개수 = (행렬의 모든 성분의 합) ÷ 2

한 꼭짓점에서 다른 꼭짓점에 연결된 변의 개수도 구할 수 있어요. 행렬에서 1은 다른 꼭짓점과 연결되었는지를 나타내는 거니까 A에서 다른 꼭짓점으로 연결된 변의 개수는 A가 있는 제 1 행의 모든 성분을 다 더한 값과 같아요.

꼭짓점에 연결된 변의 개수 = 해당 꼭짓점이 나타내는 행(또는 열)의 모든 성분의 합

A에 연결된 변의 개수는 A를 나타내는 제 1 행 (또는 제 1 열)의 성분을 모두 더한 2가 되는 거죠.

행렬의 성분과 경우의 수

행렬을 P라고 해볼게요.

P =

p₁₂ = 1이 의미하는 건 A와 B가 변으로 연결되어 있다는 뜻이죠.

P를 제곱했더니 위와 같은 행렬이 만들어졌어요. P는 두 꼭짓점이 서로 변으로 연결되어 있는지 아닌지를 나타내요. 즉 1이면 한 꼭짓점에서 다른 꼭짓점으로 이동할 때 변을 하나만 지나는 된다는 걸 말하죠. P²은 한 꼭짓점에서 다른 꼭짓점으로 이동할 때 변을 두 번 지나면 된다는 걸 의미해요. 여기서는 1이 아닌 2, 3이라는 숫자도 있죠? 이건 경우의 수를 말해요.

p₁₁ = 2죠? A에서 변을 두 개 지나서 A로 오는 방법이 두 가지가 있다는 얘기예요. A - B - A, A - C - A의 두 가지예요.

p₂₁ = 1이죠? B에서 변을 두 개 지나서 A로 가는 방법이 한 가지가 있다는 얘기예요. B - C - A뿐이네요.

Pⁿ의 p_ij = k (n, k는 자연수)
→ i에서 n개의 변을 지나서 j로 가는 방법은 k가지이다.

그래프와 행렬 1 - 그래프에서 경로에는 한 번 지나간 변은 다시 지나지 않는 것으로 한다고 했는데 행렬에서는 한 번 더 지나는 것도 포함된다는 차이가 있어요.

다음 그래프를 보고 물음에 답하여라.
(1) 그래프를 행렬로 나타내어라.
(2) A에서 변을 두 개 지나서 B까지 가는 방법의 수를 구하여라.