Lec 12. Graphs, Networks, Incidence Matrices | 교수: Gilbert Strang |
그래프
그래프는 노드와 edge 로 표현 합니다.
그래프의 노드를 매트릭스의 행과 열로 표현합니다.
매트릭스의 성분은 선으로 이어져 있으면 1, 아니면 0 입니다.
대칭 행렬로 표현되며, 대각선은 0 입니다.
( 여기서 점 . 은 선이라 가정 합시다. )
(2)
. . . .
. . . .
. . . (5)
(1) . . .
. . (4)
. . .
. .
(3)
이것을 인접 매트릭스로 표현하여 봅시다.
각 노드들을 행과 열로 표현합니다.
각 노드와 노드에 선이 있으면 1 없으면 0 입니다.
그러면 이렇게 표현할 수 있을 것입니다.
합
┌ ┐
│ 0 1 1 0 0 │ 2
│ │
│ 1 0 1 1 1 │ 4
│ │
│ 1 1 0 1 0 │ 3
│ │
│ 0 1 1 0 1 │ 3
│ │
│ 0 1 0 1 0 │ 2
└ ┘
이 매트릭스는 대칭으로 대각선은 0 입니다.
각 행의 합은 각 노드에 있는 선의 개수 즉, 차수를 의미 합니다.
성분을 다 더했을 때 그것은 2 x 선의 개수 입니다.
이러한 그래프 이론과 네트워크 이론에서 중요하게 다룹니다.
Incidence matrix
인시던스 매트릭스는 1 과 0 으로 표현하는 논리 매트릭스로서
두 개체 클레스 사이의 인시던스 릴레이션을 표현 합니다.
(4) e6
e1 . . . .>
.> . . .
. . ↑ e5 (5)
(1) e3 ↑ . .>
.> . (3) e7
e2 . . .
. .> e4
(2)
이라고 할 때 노드는 (1), (2), (3) ...
으로 n = 5 개
edge 는 1-2, 1-3, 2-3, 2-4, 2-5, 3-4, 4-5
m = 7 개 입니다.
이제 이것을 인시던트 매트릭스로 표현하여 봅시다.
각 노드들을 행 edge 들을 열로 표현합니다.
각 edge 와 노드에 선이 있으면 1 없으면 0 입니다.
-1 은 시작을 의미합니다.
┌ ┐
│ -1 0 1 0 0 │
│ │
│ -1 1 0 0 0 │
│ │
│ 0 -1 0 1 0 │
│ │
│ 0 -1 1 0 0 │
│ │
│ 0 -1 0 1 0 │
│ │
│ 0 0 0 -1 1 │
│ │
│ 0 0 -1 0 1 │
└ ┘
인시던스 매트릭스에 대하여
첫 번째 클래스를 X, 두 번째 클래스를 Y 라 합시다.
그러면 이 매트릭스는 X 의 각 원소, 즉 각 요소에 대하여 하나의 행과
Y 의 각 원소에 대하여 하나의 열을 갖습니다.
행 x 와 열 y 의 항목 x 와 y 가 incident 되어 있다면
그 값은 1 아니면 0 입니다.
그래프 이론에서 incidenct 매트릭스는 일반적인 그래프 입니다.
그런데 이것은 vertext 와 vertext 의 쌍의 관계를 인코딩하는
인접 행렬과는 다릅니다.
무방향 그래프의 무방향 인시던스 행렬은 다음과 같이
정의할 수 있습니다.
┌ ┐
│ 1 1 1 0 │
│ │
│ 1 0 0 0 │
A = │ │
│ 0 1 0 1 │
│ │
│ 0 0 1 1 │
└ ┘
인시던스 매트릭스의 각 열의 합은 2 입니다.
이는 각 edge 가 두 개의 정점에 연결되어 있기 때문입니다.
방향 그래프의 인시던스 매트릭스는 다음과 같이 정의 합니다
무방향 그래프의 방향 인시던스 행렬은 그래프의 어떤 방향성이든 방향
그래프의 인시던스 행렬입니다.
즉, edge e의 열에서 e 에 해당하는 정점의 행에 1이 하나 있고,
e의 다른 정점에 해당하는 행에 -1이 하나 있으며,
다른 행들은 다 0 입니다.
그래프 G 의 무방향 인시던스 매트릭스는 그 라인 그래프 L(G) 의 인접
매트릭스에 대하여 다음이 성립합니다.
B(G) = A(L(G)) - Im
이때, (A(L(G)))는 G의 라인 그래프의 인접 매트릭스,
(B(G))는 인시던스 매트릭스
(Im)은 m 차 단위 매트릭스 입니다.
그래프의 이산 라플라시안 ( 키르히호프 매트릭스) 은 방향 인시던스
매트릭스 (B(G)) 에서 다음과 같이 얻어집니다.
L = B(G)B(G)'
참고자료 : 위키피디아
Incidence 매트릭스