4 min to read
자료구조(14) - 그래프
그래프의 정의와 관련 용어 설명
🔚 짧게 하는 복습
✅ 1. 승자 트리의 ADT를 구현할 수 있다.
혹시 기억이 안 난다면, 다시 돌아가자
저번 시간까지 트리에 대한 개념을 모두 다루었다.
그렇다면 우리가 트리를 어떻게 정의했는지 혹시 기억하는가?
트리는 순환성이 없는 노드와 간선의 집합이다.
사실 트리는 지금부터 배울 그래프라는 자료 구조의 부분집합으로, 모든 트리는 그래프에 속한다.
본격적으로 그래프가 무엇인지 알아보자.
그래프란?
그래프란 모든 정점과 간선의 집합이다. 트리에서는 이 정점을 노드라는 특별한 이름으로 불렀을 뿐이다.
순환성이 있으면 안 되는 트리와 다르게, 그래프는 순환성이 있어도 상관없다.
보통, 아래의 그림들 같은 모양으로 나타난다.
그래프의 분류1 - 간선의 종류 관점
그런데 조금 특이한 점이 보인다.
트리에서는 그냥 간선이 실선의 형태로 나타났는데, 그래프에서는 4-2 처럼 화살표로도 간선이 나타난다.
사실 그 이유는, 간선이라는 개념은 출발점(predecessor)과 도착점(successor)을 포함하기 때문이다.
그래서 실선 간선은 두 정점 사이 방향이 없음 혹은 유향을 뜻하고, 화살표 간선은 출발점에서 도착점으로 향한다는 것을 의미한다.
(a) 그래프처럼 두 정점 사이에 2개 이상의 간선이 들어갈 수도 있는데, 이를 평행 간선(parallel edge)라고 한다.
또한, 간선의 출발점과 도착점이 같은 경우 루프(Loop)라고 한다.
평행 간선을 포함한 그래프를 멀티 그래프(multigraph)
루프와 평행 간선을 모두 포함한 그래프를 일반 그래프(general graph)
그 어떤 루프와 평행 간선도 포함하지 않는 그래프를 단순 그래프(simple graph)라고 한다.
또 일반적인 간선의 관점에서,
그래프 내 모든 간선이 실선 간선인 경우, 무향 그래프(UnDirected Graph)라고 한다.
하나라도 화살표 간선을 가진 그래프는, 유향 그래프(Directed Graph/ Digraph)라고 한다.
보통 무향 그래프를 UDG, 유향 그래프는 DG라고 한다.
그래프의 분류2 - 가중치의 관점
우리가 지금까지 다룬 그래프는 간선에 값이 할당되지 않았다.
간선에 값이 할당되는 경우, 그 값을 가중치(Weight)라고 한다.
예를 들어, 아래 사진을 보자.
위 그래프를 보면 모든 간선에 가중치가 있는 모습을 볼 수 있다.
이렇게 모든 간선에 가중치가 있다면 가중치 그래프 (Weighted Graph), 모든 간선이 가중치가 없다면 비가중치 그래프(Unweighted Graph)라고 한다.
참고로 위 그래프는 가중치는 있고, 방향성이 없어서 가중치 유향 그래프(Weighted Directed Graph)라고 한다.
자료 구조 강의에서는 가중치 그래프를 다루는 여러 알고리즘을 배우지 않을 것이다.
하지만 그래프를 제대로 이해하려면, 후속되는 알고리즘 강의를 꼭 배우길 바란다.
그래프의 분류3 - 순환성의 관점
우리는 트리에서 순환성에 대한 개념을 얕게 다룬 적이 있다.
그래프답게 집합의 개념을 이용해서 명확하게 해보겠다.
우선, 무작위로 정점 2개를 정한다.
DG이면 출발점과 도착점을 정해서 출발점에서 도착점으로 향하게 할 수 있는 간선들을 찾는다.
물론, UDG라면 그냥 두 정점 사이를 이을 수 있는 간선들을 찾는다.
여기서 이 간선들의 집합이 공집합이라면, 둘 사이 경로가 없다고 한다.
아니라면, 그 집합의 간선을 순서대로 나열한 것을 경로라고 한다.
이 그래프를 예를 들면,
v3과 v5 사이 경로는 {e2}이다.
또한, v1과 v2 사이 경로는 {e3}, {e4, e5}, {e1, e6}으로 총 3개이다. (이처럼 두 정점 사이 경로는 하나만 존재하는 것이 아니다.)
여기서 보통, 비가중치 그래프에서는 경로 내 간선의 수, 가중치 그래프에서는 경로 내 간선의 가중치 합을 간선의 길이라고 한다.
가중치 그래프로 한 번 더 연습해보자.
0에서 2를 가는 경로는 {0과 1 경로, 1과 2 경로}, {0과 3 경로, 3과 2 경로}, {0과 1 경로, 1과 3 경로, 3과 2 경로} 총 3개이다.
각각의 길이는 4, 9, 9이며, 최단 길이 경로는 {0과 1 경로, 1과 2 경로}이다.
(최단 길이 경로를 구하는 방법은 알고리즘 강의에서 다루며, 여기서는 생략하겠다.)
그런데, 이 경로라는 것의 출발점과 도착점이 같은 경우 이를 순환성(사이클)이라고 한다.
0 정점의 사이클은 {0-1 경로, 1-3 경로, 3-0 경로}, {0-1 경로, 1-2 경로, 2-3 경로, 3-0 경로}, {0-1 경로, 1-2 경로, 2-3 경로, 3-4 경로, 4-0 경로}, {0-4 경로, 4-3 경로, 3-0 경로} 총 4개이다.
그리고 각각의 길이는 14, 13, 17, 18이다.
최단 길이 사이클은 {0-1 경로, 1-2 경로, 2-3 경로, 3-0 경로}이다.
이렇게 사이클이 있는 그래프를 순환 그래프(Cyclic Graph), 아니라면 비순환 그래프(Acyclic Graph)라고한다.
그래프의 분류4 - 연결성의 관점
그래프를 정점과 간선의 집합이라고 했다.
그렇기에, 집합의 개념을 빌려서 부분 그래프(subgraph)를 정의할 수 있다.
어떠한 그래프 A의 모든 정점과 간선이 다른 B에 속한다면, 그래프 A를 B의 부분 그래프라고 할 수 있다.
모든 정점 쌍에 대해 경로가 존재한다면 연결 그래프, 그렇지않는다면 비연결 그래프라고 한다.
비연결 그래프는 여러 부분 연결 그래프로 나눠진다.
이 부분 그래프들을 각각 연결 성분(component)라고 한다.
아래 그림을 보자.
여기서, 전체 그래프는 비연결 그래프이고 {b, a, f, e}, {c, g, h}, {d, i}, {j}, 총 연결 성분 4개로 나눠진다.
(정점 하나도 부분 그래프이다.)
📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)
✅ 1. 그래프의 용어에 대해 안다.
✅ 2. 그래프의 분류에 대해서 안다.
⚠️ 트리는 연결, 비순환, 무향 그래프이다.
💣 과제,
- 하나의 그래프를 골라 경로, 연결요소, 정점/간선 등을 복습해보자. (난이도 下)
🔜 더 공부해보기,
- 읽어볼 거리(1) : 강연결 vs 약연결 그래프(by chatgpt)
적당한 설명 글을 찾고 싶었는데, 없어서 본인이 원서에 있는 그대로 번역해서 올림
강하게 연결된 그래프 (Strongly Connected Graph):
방향 그래프에서 각 정점 쌍 간에 양방향으로 경로가 존재하는 경우를 말합니다. 즉, 모든 정점에서 출발하여 다른 정점으로 가는 경로와 해당 정점으로 돌아오는 경로가 모두 존재하는 경우를 의미합니다. 각 정점 쌍에 대해 최소한 한 개의 방향이 있는 경로가 있는 상황에 해당합니다.
약하게 연결된 그래프 (Weakly Connected Graph):
방향 그래프에서 강하게 연결된 그래프가 아니지만, 그래프의 양방향으로 연결된 경우를 말합니다. 즉, 강하게 연결된 그래프로 변환 가능한 경우를 포함합니다. 방향성이 있는 간선과 무방향 간선이 혼합된 상황에 해당합니다.
Comments