[강의노트] 무방향 그래프 - 1

그래프 - 1

알고리즘에서 정말 중요한 추상 자료형인 그래프를 배워보자

 

그래프 ADT

그래프 추상 자료형은 정점과 간선 정보쌍을 가지고 있는 자료형이다.

아래 그림을 통해 이해하면, 정점은 공항도시의 이름 간선은 정점사이의 거리를 저장하게 된다.

 

이때 정점은 vertex 의 V로, 간선은 edge의 E라고 앞으로 칭할 것이다.

그래프는 간선의 방향성에 따라서 방향간선과 무방향 간선으로 구분된다.

아래의 예시는 정점 인천과 LA, 그리고 두 정점을 있는 간선을 보여주고 있다.

 

첫번째 예시는 간선에 방향이 있고, 두번째 예시는 방향이 없다

이때 방향이 있는 간선을 방향간선 그래프라고 한다. 정점에 방향성이 추가되었으므로

시작 정점을 시점 도착 정점을 종점이라고 부른다. 예시에서는 인천에서 LA로 가는 비행기편의 이름 KE085 라는 정보를

간선이 담고 있다.

 

반대로 방향이 없는 간선은 무방향간선 그래프라고 한다.

항로같은 경우 두 정점의 거리정보를 간선이 담고있기때문에 방향성이 필요없다.

 

이러한 그래프는 다양하게 응용되는데 예시는 다음과 같다.

 

그래프  관련 용어

아래 예시의 그래프를 통해 용어에 익숙해져보자.

간선의 끝점(end vertex) : 정점 U와 V는 간선 a의 양끝점이라고 부른다.

정점의 부착(incident) 간선 :  간선 a, d , b는 정점 V에 부착한다.

정점의 인접(adjacent) 정점 :  정점 U와 V는 하나의 간선 a를 사이에 두고 있으므로 서로 인접하다고 한다.

정점의 차수(degree) : 정점 X의 차수는 5이다. 차수란 부착되어있는 간선의 수를 말한다

병렬 간선(parallel edges) : 간선 h와 i는 병렬 간선이다.

루프 : 간선 j는 루프이다.

경로(path) : 정점과 간선의 교대열으로 정점으로 시작해서 정점으로 끝난다. 각 간선은 양 끝점으로 시작하고 끝난다.

단순경로 : 위에서 빨간 경로를 말한다. 즉 정점과 간선이 중복되지않고 유일한 경로

반대로 녹색 경로는 정점 W 를 두번 지나기때문에 비단순경로

 

 

싸이클은 정점과 간선이 교대하는 원형열. 각 간선은 양끝점으로 시작하고 끝남

마찬가지로 단순싸이클은 모든 정점과 간선이 유일한 싸이클

 

쉽게 말하면 경로중에 시작 정점으로 다시 오는경우를 싸이클이라 부름

 

그래프의 속성

차수는 정점에 부착되어있는 간선을 말한다. 그래프에 존재하는 정점의 차수를 모두 더하면 간선 수의 2배 값이 나온다.

그 이유는 각 간선이 두번씩 세어지기 때문이다.

 

루프나 병렬 간선이 없는 단순한 무방향 그래프에서는 항상 m이 n(n-1)/2 보다 작다.

 

속성 1 에서 그래프에 존재하는 정점의 차수를 모두 더하면 2*m 이라는 것을 알았다.

따라서 각 정점의 최대차수 n-1 x n 은 2m 보다 같거나 크다.

부그래프

그래프의 부분집합이라 이해하면 된다.

 

알아둬야할 것은 신장 부그래프에 대한 개념

부그래프 :  V의 부분집합 + E의 부분집합

신장 부그래프 :  V + E의 부분집합

연결성

모든 정점쌍에 대해 경로가 존재하면 그래프가 연결되었다고 말한다. 즉 어떤 정점 2개를 무작위로 골랐을 때, 모든 경우에서 시점에서 종점으로 가는 경로가 존재해야 연결된 것

 

그래프의 연결요소는 연결성을 가진 덩어리라고 이해하자. ( 그림을 통해 알아두면 훨씬 더 쉬움)

밀집도

그래프의 밀집도는 간선의 수에 개념으로 알고리즘 선택에 영향을 끼치기 때문에 중요하다.

 

예를 들어 어떤 알고리즘 A,B의 시간복잡도가 다음과 같다고 하자.

알고리즘 A : O(n *m)

알고리즘 B : O(n^2)

 

즉 두 알고리즘의 시간복잡도를 비교하는 것은 m과 n 의 크기를 비교하는 문제로 연결된다.

m은 간선의 수 , n은 정점의 수 이다. 이때 밀집도는 m에 대한 개념이기때문에

 

밀집되어있다는 것은 m이 커지는 것 , 즉 알고리즘 B가 A보다 효율이 좋다.

희소하다는 것은 m이 작아지는 것, 즉 알고리즘 A가 B보다 효율이 좋다.

싸이클

자유트리 또는 트리 라는 개념이 나오는데, 자료구조형 트리와는 다른 개념이다.

그래프의 트리는 싸이클이 존재하지않는 무방향 그래프이다.

 

숲은 트리보다 한 단계 큰 개념으로, 트리는 숲의 연결요소가 된다.

 

신장

아까 부그래프에서 신장 부그래프라는 개념이 나왔었다. 신장 부그래프는 모든 정점 + 부분 간선으로 이루어진 그래프였다.마찬가지로 신장트리는 신장 부그래프중에 트리를 신장트리라고 한다.

그래프 ADT 메소드(공통)

이제 그래프 추상 자료형의 메소드를 알아보자.

먼저 그래프 ADT에서 무방향, 방향 그래프에서 공통적으로 쓰이는 메소드를 알아보겠다.

 

일반 메소드

numVergices(): 그래프내의 정점의 개수를 반환한다.

numEdges(): 그래프내의 간선의 개수를 반환한다.

vertices(): 모든 정점을 반환한다

edges(): 모든 간선을 반환한다.

 

접근 메소드

aVertex(): any Vertex라는 의미로, 아무 정점을 반환한다. (여기서 아무거나를 구현하기 위해 그냥 맨 앞의 정점을 반환함)

질의 메소드

isDirected(e) : 방향 간선인지 아닌지 반환

반복 메소드

directedEdges() : 모든 방향간선을 반환한다

unDirectedEdges(): 모든 무방향간선을 반환한다.

갱신 메소드

insertVertex(o) : 정점을 삽입한다.

removeVertex(v) : 정점을 삭제한다

removeEdge(e) : 간선을 삭제한다.

 

무방향 그래프 ADT 메소드

다음은 무방향 그래프에서 사용하는 메소드이다.

접근 메소드

deg(v):  정점의 차수를 반환한다.

opposite(v,e): 정점 v에 대한 끝점을 반환한다.

질의 메소드

areAdjacent(v,w): 두 정점이 이웃한가를 판별

반복 메소드

endVertices(e): 간선에 대한 양끝점을 반환한다.

adjacentVertices(v) : 정점v에 이웃하는 정점들을 반환한다.

incidentEdges(v) : 정점v에 부착되어있는 간선을 반환한다.

갱신 메소드

insertEdge(v,w,o): 정점 v에서 w로 항목 o를 저장한 무방향간선을 삽입하고 반환

 

 

 

방향 그래프 ADT 메소드

다음은 방향 그래프에서 사용하는 메소드이다.

접근 메소드

origin(e):  간선의 시점을 반환한다.

destination(e): 간선의 종점을 반환한다.inDegree(v): 정점으로 진입하는 간선의 차수를 반환한다.outDegree(v): 정점에서 진출하는 간선의 차수를 반환한다.

반복 메소드

inIncidentEdges(v): 진입부착간선 반환

outIncidentEdges(v): 진출부착간선 반환

inAdjacentVertices(v): 진입인접정점 반환

outAdjacentVertices(v): 진출인접정점 반환

갱신 메소드

insertDirectedEdge(v,w,o): 정점 v에서 w로 항목 o를 저장한 방향간선을 삽입하고 반환

makeUndirected(e): 간선 e를 무방향간선으로 전환

reverseDirection(e): 방향간선 e를 역행