간선

간선(Edge)은 그래프 이론에서 두 노드(Node) 또는 정점(Vertex)을 연결하는 선분 또는 연결을 나타내는 추상적인 개념이다. 간선은 방향성 유무에 따라 방향 간선과 무방향 간선으로 분류된다.

• 무방향 간선: 두 노드를 연결하는 단순한 선분으로, 방향성이 없다. A와 B라는 두 노드를 무방향 간선으로 연결했다면, A에서 B로, B에서 A로의 이동이 모두 허용된다. 이는 관계가 상호적인 경우에 사용된다. 예를 들어, 사회적 네트워크에서 친구 관계를 나타낼 때 사용될 수 있다.

• 방향 간선: 두 노드를 연결하는 화살표로 표현되며, 방향성을 가진다. A에서 B로 향하는 방향 간선은 A에서 B로의 이동만 허용하며, B에서 A로의 이동은 허용되지 않는다. 이는 관계에 방향성이 있는 경우에 사용된다. 예를 들어, 웹페이지의 하이퍼링크를 나타낼 때 사용될 수 있다.

간선은 그래프의 연결성을 나타내는 중요한 요소이며, 그래프의 구조와 특성을 결정하는 데 큰 영향을 미친다. 간선에는 가중치(Weight)가 부여될 수 있으며, 이 가중치는 거리, 비용, 강도 등을 나타낼 수 있다. 가중치가 부여된 간선은 가중치 그래프(Weighted Graph)를 구성한다.

간선의 개수는 그래프의 크기와 복잡성을 나타내는 중요한 지표 중 하나이다. 특정 알고리즘의 시간 복잡도는 간선의 개수에 따라 달라지는 경우가 많다.

관련 용어: 그래프, 노드, 정점, 가중치, 가중치 그래프, 방향 그래프, 무방향 그래프, 경로, 사이클