그래프이론기초(1) - 정점, 간선

그래프 이론의 기초를 배우려고 합니다.

 

기초중의 기초중에 정점과 간선이 있는데

 

정점(Vertex)

정점은 노드라고도 불리기도 하고 그래프를 형성하는 기본 단위중 하나입니다.

정점은 분할할 수 없는 객체이어야 하며 점으로 표현되는 위치, 물건 등이 될 수 있습니다.

 

간선(Edge)

간선은 정점을 잇는 선을 의미합니다.

경로 또는 관계가 될 수 있습니다.

 

예를 들어서 어떠한 물건 또는 어떠한 위치로부터 무언가를 통해 이어진다라고 하였을 때,

어떠한 물건, 어떠한 위치는 정점이며, 무언가를 통해 이어진다는 간선이 됩니다.

 

지하철 노선도를 예로 보여드리겠습니다.

 

여기서 보면 모든 정점은 하나의 역들이며 그것을 이어주는 것이 간선입니다.

 

그럼 사람으로도 예를 들어보죠.

나도 빨간실 줘

지금 왼쪽의 사람과 오른쪽의 사람은 정점이고

저 빨간실이 간선입니다.

 

저게 만약 왼쪽 사람만 좋아한다라고 치면 단방향 간선

양쪽이 둘 다 마음이 있다면 양방향 간선입니다.

 

슬프네요.

 

ㅎㅎㅎ

 

 

끄읕