그래프의 종류
by 桜 高梨
1. 간선의 특성
1.1. 간선의 방향성
1.1.1. 무방향 그래프
1.1.1.1. 간선에 방향 X
1.1.1.2. 양방향으로 갈 수 O
1.1.1.2.1. (A, B) == (B, A)
1.1.1.3. 정점 A와 정점 B를 연결하는 간선 : (A, B)
1.1.1.4. 최대 간선 수 = 노드의 개수*(노드의 개수-1)/2
1.1.2. 방향 그래프
1.1.2.1. 간선에 방향 O
1.1.2.2. 한쪽 방향으로만 갈 수 O
1.1.2.2.1. <A, B> != <B, A>
1.1.2.3. 정점 A에서 정점 B로만 갈 수 있는 간선 : <A, B>
1.1.2.4. 최대 간선 수 = 노드의 개수*(노드의 개수-1)
1.2. 가중치 그래프
1.2.1. 간선에 정점 간 가중치를 나타냄
2. 구조적 특성
2.1. 완전 그래프
2.1.1. 그래프 내 모든 정점이 서로 1:1 간선으로 연결됨
2.1.2. 연결 가능한 최대 간선 수를 가짐
2.2. 부분 그래프
2.2.1. 정점의 집합과 간선의 집합의 부분 집합으로 이루어짐