[그래프] #1 그래프 용어 정리

그래프는 정점(Vertex)의 집합과 간선(Edge)의 집합으로 이루어져 있습니다. 조금 더 직관적으로는 점과 그 점 사이를 잇는 선분으로 이루어진 그림이라고 할 수 있겠습니다.

참고로, 정점은 꼭짓점이나, 노드(Node)라고 부르기도 합니다.

(a)는 루프와 다중변이 있는 그래프, (b)는 단순한 그래프, (c)는 루프가 있는 그래프이다. (a)와 (c)는 유향 그래프이며, (b)는 무향 그래프이다.

 

간단하게 용어를 정리하자면

정점(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)라 한다.

 

여기서 설명한 용어 정도만 알고 있다면, 그래프에 관련된 이론 설명은 어느정도는 전부 이해가 갈 것이라고 생각합니다.

 

오류가 있다면 지적바랍니다.