[자료구조] 12-2. 그래프의 용어

하나의 개체를 표현하는 것을 노드 혹은 버텍스라고 부른다. 표현할 때는 원 내부에 숫자나 문자를 쓴다. 그 버텍스를 연결하는 선을 엣지라고 한다. 일대일 관계만을 나타낸다. 일대다는 할 수 없다. 또한, 방향성에 따라 대칭인 관계와 그렇지 않은 관계가 있다.

관계를 표현하는 것에는 adjacent와 incident가 있다. 

- adjecent: 버텍스에 대한 표현. 각 버텍스가 서로 연결되어 있다면, 즉 둘이 한 리스트에 포함되어 있다면 adjacent라고 쓴다. 그림을 보면 0과 1이 연결되어 있으므로 adjacent하다.

- incident: 엣지에 대한 표현. 두 엣지가 같은 버텍스를 공유하고 있다면 incident 하다고 말한다. 그림에서 0,1과 0,2는 같은 버텍스를 공유하고 있으므로 incident 하다.

부분 그래프는 부분 집합을 생각하면 쉽게 이해할 수 있다.

경로는 한 버텍스에서 다른 버텍스로 갈 때 위의 조건을 만족하는 버텍스의 연속체이다. u에서 v로 갈 때까지 계속 연속된 엣지들이 존재하는 것이다.

예를 들어, 1에서 7까지 가는 path(1,7)이 있다면 u=1, v=7이 되고 그 사이의 i1, i2, i3...는 0, 1, 4, 6이 된다. 

여러 개의 패스가 존재할 수도 있다.

그러면 경로의 길이에 대해 얘기해보자. 경로의 길이는 버텍스 또는 엣지의 수를 말한다.

예를 들어, 1번 버텍스에서 7번 버텍스까지 가는 경로를 1 0 2 4 6이라고 한다면, 버텍스를 기준으로는 5가 된다. 엣지 기준으로는 4이다.

만약 weighted라면 가중치의 합을 경로의 길이라고 한다. 위의 그림을 계산하면 5 3 4 3 을 모두 더한 15가 경로의 길이가 된다.

최단 경로는 그 중에서 길이가 최소, 또는 가중치의 합이 최소인 경로를 말한다.

심플 패스는 시작하는 버텍스와 끝나는 버텍스를 제외한 모든 버텍스가 다 다른 경로를 의미한다.

예를 들어, 1에서 3으로 가는 경로는 1 3, 1 0 2 3이 될 수 있다. 이 두 경로는 버텍스들이 다 다르기 때문에 심플 패스다. 하지만 1에서 3으로 가는데 0에서 1로 갔다가 5로 가고 6으로 갔다가 2로, 3으로 간다면 단순 경로가 아니다. 경로 상에 중첩된 버텍스가 있기 때문이다.

사이클은 첫번째 버텍스와 마지막 버텍스가 일치하는 단순 경로를 얘기한다.

사이클이 존재하지 않는 것은 비순환 그래프라고 한다.

버텍스 u와 v 사이에 경로가 존재하면 연결이라고 말한다. 예로, 5와 8은 연결이지만 1과 5는 연결이 아니다.

만약 모든 쌍의 버텍스들이 연결되어 있다면 커넥티드 그래프라고 한다. 위의 그래프는 커넥티드가 아니다.

연결 성분은 연결된 부분 그래프의 '최대치'를 의미한다. 예를 들어, 연결 성분을 5 6 7이라고 하면 안된다. 8과 9를 더할 수 있기 때문이다. 이 그림에서 연결 성분은 딱 2개이다. 1 2 3과 5 6 7 8 9다.

그래프의 관점에서 트리는 순환이 없다. 또한 모든 버텍스들이 연결되어 있다. 따라서 트리는 connected acyclic graph라고 말한다.

방향 그래프의 관점에서 살펴보자. 뱡향 그래프에서 연결이라고 말할 수 있으려면 모든 방향이 다 연결되어 있어야 한다. 1 0은 연결되는데 0 1은 연결되어있지 않다면 연결이라고 말할 수 없다.

이러한 성질을 강하게 연결되었다고 해서 strongly connected component라고 한다. 위의 그림을 보면 1 2 3과 4 5는 강한 연결 성분이다.

버텍스에 연결된 엣지의 수를 차수라고 말한다. 예를 들어, 7번 버텍스는 4개의 엣지에 연결되어 있으므로 디그리가 4이다.

한 그래프의 부분 그래프가 다음의 조건을 만족시킬 때 신장 트리라고 한다.

1. 버텍스는 같고 엣지는 작거나 같다.

2. 하지만 엣지에 순환은 존재하지 않는다.

3. 엣지의 수는 n-1개여야 한다. n은 버텍스의 수다.

오른쪽 그림은 n=5이므로 엣지의 수는 n-1=4이다. 또한, 순환이 존재하지 않는다. 이러한 그래프를 신장 트리라고 하고, 한 트리에는 여러 개의 신장 트리가 존재할 수 있다.