728x90
그래프는 정점(Vertex)의 집합과 간선(Edge)의 집합으로 이루어져 있습니다. 조금 더 직관적으로는 점과 그 점 사이를 잇는 선분으로 이루어진 그림이라고 할 수 있겠습니다.
참고로, 정점은 꼭짓점이나, 노드(Node)라고 부르기도 합니다.
간단하게 용어를 정리하자면
정점(Vertex) | 그래프의 정점 |
간선(Edge) | 그래프의 두 정점을 잇는 간선 |
루프(Loop) | 하나의 정점만을 연결하는 간선 |
보행(Walk) | 정점과 간선을 이용하여 나타낸 열. 이때, 정점과 정점 사이에 나오는 간선은 두 정점을 연결한다. 보행에서 시작하는 정점과 끝나는 정점이 같을 경우, 이 보행은 닫혀있으며, "닫힌 보행(Closed Walk)"이라고 한다. |
트레일(Trail) | 간선이 중복되지 않는 보행 |
경로(Path) | 정점이 중복되지 않는 트레일 |
사이클 또는 순환(Cycle) | 시작하는 정점과 끝나는 정점이 같은 경로 |
회로(Circuit) 또는 여행(Tour) | 시작하는 정점과 끝나는 정점이 같은 트레일 |
차수(Degree) | 정점에 입사하는 간선의 수 |
이 밖에도
- 간선으로 연결된 두 정점이 있다면, 두 정점은 인접(Adjacency)하다.
- 두 정점 사이에 여러 개의 변이 있다면, 이를 다중변(Multiple Edges)이라 한다.
- 그래프에 루프나 다중변이 없다면 해당 그래프는 단순하며, 이러한 그래프를 단순 그래프(Simple Graph)라 부른다.
- 임의의 한 점에서 다른 모든 정점에 방문할 수 있다면, 이 그래프를 강하게 연결(Strongly Connected)되었다고 한다.
- 그래프의 부 그래프(Sub Graph)가 강하게 연결되어 있다면, 이를 강한 연결 요소(Strongly Connected Component)라 한다. 무향 그래프에서는 그다지 의미가 없다.
- 연결 그래프(Connected Graph)는 모든 정점이 간선을 통해 연결된 그래프이다. 다른 말로, 모든 두 정점 사이를 잇는 경로가 존재하는 그래프이다.
- 그래프를 잇는 간선에 방향성이 있다면, 해당 그래프는 유향 그래프(Directed Graph)라 하며 방향이 없다면,
무향 그래프(Undirected Graph)라 한다.
여기서 설명한 용어 정도만 알고 있다면, 그래프에 관련된 이론 설명은 어느정도는 전부 이해가 갈 것이라고 생각합니다.
오류가 있다면 지적바랍니다.
728x90
'기초 내용 > 그래프' 카테고리의 다른 글
[그래프] 트리의 지름 (0) | 2022.10.02 |
---|---|
[그래프] #2 인접 행렬과 인접리스트 (1) | 2022.09.11 |