연결성을 정의한다면 그래프 상에서 하나의 노드가 얼마나 많은 노드와 연결되어 있는지를 의미한다.
이전에 연결성을 정의할때,몇가지 예비 개념을 자세히 설명할 필요가 있다.
인접 노드와 incident(충도?사고?가 발생하는) 엣지.
노드 v1과 v2를 보이는 그래프 G(V,E)에서 엣지로 서로 연결되어 있는데:
e1(a,b)와 e2(c,d) 두개의 엣지가 있을때 문제가 생기는 이유는 하나의 endpoint 를 공유할때 발생한다고 할수 있다
그림 2.6에서는 예시 그래프에서 근접 노드와 사고 발생 엣지를 보여준다.
방향성을 가지는 그래프에서, 두개의 엣지에서 사고가 발생하게 되는 상황은 한개의 끝 노드가 다른 노드의 시작점일경우 사고가 발생한다, 이럴때, 엣지의 방향성이 같을때 사고가 발생한다고 정의할수 있다.
그림 2.6 : 근접 노드와 사고나는 엣지.
이 그림에서 u와 v는, 인접 노드이며, 엣지 (u, v) 와 (v,w)는 사고 발생 엣지로 볼수 있다.
가로로 횡단하는 엣지.
그래프 상에서 엣지는 시작점에서 끝점까지 횡단하는 엣지인데,엣지의 형상이 한개이며, 끝노드에서 멈추게 있다.
그러므로, 만약 엣지 e(a,b)에서 (노드 a와 b를 연결하는엣지), e 노드를 찾아가기 위해서 a에서 시작해 b에서 끝나게 된다.
대신에, 방향성이 없는 그래프에선 b에서 시작해서 a로 갈수있다(방향성이 없으니 어디서 시작하던 같다).
Walk, Path, Trail, Tour, 와 Cycle.
(번역하면 이상하기 때문에 원문 그대로 사용)
walk란 사고난 엣지를 처음부터 끝까지 단계를 밟아가며 움직이는것이다.
다르게 설명하면, 엣지 e1(v1,v2),e2(v2,v3), e3(v3, v4)...en(vn,vn+1)를 이동한다면, v1을 시작 노드로 Vn+1 노드에서 끝을 맺게 된다.
v1에서 시작한 walk 가 끝나지 않으면 "open walk"라고 부른다.
walk가 시작지점으로 돌아온다면 (v1 = vn+1)상황으로서 "closed walk"라고 부른다.
비슷하게, walk 는 노드의 sequence 를 나타내는데 사용할수 있다 (walk가 노드들을 순차적으로 방문한다는 의미이기 때문에).
이 예시에서, 엣지의 형상은 e1(v1,v2),e2(v2,v3)... en-1(vn-1, vn)로 이루어져 있다.
walk의 길이는 전체 엣지 크기를 n이라 할때 n-1로 정의할수 있다.
trail의 정의는 walk의 종류로 볼수 있지만 1번 이상 이동할수 없는 상황을 의미한다, 즉 모든 walk 엣지는 distinct하다고 볼수 있다.
닫힌 (closed)trail은 (끝점이 시작점인)상황으로서 tour 나 circuit으로 불린다.
노드와 엣지를 walk 하는 과정 자체를 path라고 칭하고,닫힌 path 는 cycle이라고 한다.
path의 길이나 cycle의 길이를 지칭할때는 path 와 cycle에서 거쳐가는 엣지의 수를 의마한다.
방향성 있는 그래프에서,경로가 지정되어 있는데 당연하게도 방향이 지정된 곳으로 이동해야 하기 때문이다.
그림 2.7을 살펴보면, v4,v3,v6,v4,v2는 walk 과정이며, v4,v3은 path, v4, v3, v6, v4, v2는 trail, v4, v3, v6, v4는 tour와 cycle 이라고 부른다.
그래프는 Hamiltonian cycle을 가지고 있는데 이는 모든 노드를 방문하는 cycle이 있을때 Hamiltonian cycle이 있다고 할수 있다.
Eulerian tour를 가지는 상황은 모든 엣지가 한번만 이용될때를 의미한다.
그림 2.8을 보면 Hamiltonian cycle 과 an Eulerian tour를 설명하고 있다.가중치 그래프에서 노드가 랜덤으로 방문되는 상황은, random walk라고 한다
그림 2.7:Walk, Path, Trail, Tour,Cycle. 그림에서 볼수 있듯이,v4,v3,v6,v4,v2는 walk를, v4,v3 는 path, v4, v3, v6, v4, v2 는 trail and v4, v3, v6, v4 는 tour 와 cycle을 의미한다.
그림 2.8 : Hamiltonian Cycle 과 Eulerian Tour.
Hamiltonian cycle은 한개의 노드에서 시작하며, 한번만 다른 노드를 방문하며, 시작지점으로 다시 돌아온다.
Eulerian tour 에서는, 모든 엣지를 한번만 방문하고 시작지점으로 돌아온다.
Eulerian tour 에서는, 한개의 노드를 여러번 방문할수 있다.
그림에서는 v1, v5, v3, v1, v2, v4, v6, v2, v3, v4, v5, v6, v1이 Eulerian tour를 의미한다.
이 상황에서 엣지의 가중치는, 엣지를 가로지르는 가능성에 의해 정해진다.
이 work 상황을 정확히 수행하기 위해서는, 모든 엣지가 Vi상황에서 시작해야 하며
임의의 walk 단계는 알고리즘 2.1에 의해 수행되어야 한다(알고리즘 2.1은 하단을 참조).
알고리즘의 시작은 노드 v0에서 시작하고 방문하는 노드의 순서는 높은 가중치(상단에서 설명했듯 방문 가능성이 높으면 가중치가 높아진다)부터 방문하게 된다.
댓글 없음:
댓글 쓰기