그래프 연습 문제

연습문제

무방향그래프와 관련된 method만을 가지며 갱신 메쏘드를 포함하지 않는, 단순화한 그래프 ADT를 그림 13-14(그래프 ADT의 연결리스트 구현)에 보인 것처럼 연결리스트를 사용하여 구현하기 위해 다음 A,B 두 가지 경우 각각에 대해 다음 메쏘드 들을 의사코드로 작성하라.

• integer deg(v): 정점 v의 차수를 반환
• vertex opposite(v,e): 정점 v의 간선 e에 대한 반대쪽 끝점을 반환
• boolean areAdjacent(v,w): 정점 v와 w가 인접한지 여부를 반환
• iterator adjacentVertices(v): 정점 v의 인접정점을 모두 반환
• iterator incidentEdges(v): 정점 v의 부착간선을 모두 반환

  그래프가 인접 리스트 구조로 표현됨

  Alg deg(v)              $O(deg(v))$

1. c= 0
2. e = (v.incidentEdges).next
3. while(e != NULL){
   c++;
   e++;
   }
4. return e;

Alg opposite(v,e) $O(1)$

1. w,v= e.endpoints
2. if (v==u) return w
   else return u

Alg areAdjacent(v,w) $O(min(deg(v),deg(w)))$

1. if(deg(v)<deg(w))
   m= v
   else
   m=w
2. e = (m.incidentEdges).next
3. while( e!= NULL){
   a,b = e.endpoints
   if((v==a)&&(w==b) || (v==b)&&(w==a))

    return True

   e = e.next
   }
4. return False

Alg adjacentVertices(v) $O(deg(v))$

1. L = empty list
2. e = (v.incidentEdges).next
3. while(e != NULL){
   L.addLast(opposite(v,e))
   e = e.next
   }
4. return L.elements()

Alg incidentEndges(v) $O(deg(v))$

1. L = empty list
2. e = (v.incidentEdges).next
3. while(e!= NULL){
   L.addLast(e)
   e = e.next
   }
4. return L.elements()

#### 그래프가 인접 행렬 구조로 표현됨

Alg deg(v) $O(n)$

1. c = 0
2. vi = index(v)
3. for j = 0 to n-1
   if(A[vi,j]!= NULL)

    c ++

4. return c

Alg opposite(v,e) $O(1)$

1. w,v= e.endpoints
2. if (v==u) return w
   else return u

Alg areAdjacent(v,w) $O(1)$

1. return A[index(v),index(w)]!= NULL

Alg adjacentVertices(v) $O(n)$

1. L = empty list
2. vi = index(v)
3. for j = 0 to n-1
   if(A[vi,j] != NULL)

    L.addLast(opposite(v,A[vi,j]))

4. return L.elements()

Alg incidentEndges(v) $O(n)$

1. L = empty list
2. vi = index(v)
3. for j = 0 to n -1
   if(A[vi,j]!=NULL)

    L.addLast(A[vi,j])

4. return L.elements()

```

12개의 정점과 18개의 간선으로 이루어지고 3개의 연결요소를 가진 단순 무방향그래프 G를 그려라. 위에서 만약 G가 18개가 아닌 66개의 간선으로 이루어졌다면 G를 그리는 것이 불가능한 이유를 설명하라

4개의 정점을 가진 3개의 연결요소가 각각 22개의 간선을 가지는 것 or 10개의 정점을 가진 1개의 연결요소와 아무와도 연결되지 않은 정점 1개를 가진 2개의 연결요소 일 경우 66개의 간선을 가질 수 없다. 를 논리적으로 설명해야 하는데 흠...

G가 66개의 간선으로는 이루어질 수 없다. G가 12개의 정점과 3개의 연결요소로 이루어졌다면 G가 가질 수 있는 최대 간선수는 45개이다. 이는 10개의 정점으로(따라서 45개의 간선을 가짐) 이루어진 완건 연결요소와 각각 단일 정점으로 이루어진 두 개의 연결요소로 이루어지 경우다.

아 최대 간선 수는 n(n-1)/2였다...

G를 n개의 정점과 m개의 간선으로 이루어진 단순 연결그래프라 하자. 왜 $O(\log{m}) = O(\log{n})$ 인지 설명하라

단순연결그래프면 m<= n(n-1)/2 이기 때문이다.

m<= n(n-1)/2며 이는 $O(n^2)$이다. 따라서 $O(\log{m}) =O(\log{n^2})=O(2\log{n})= O(\log{n})$