Pogo stick. 2013 Round 1C. 문제 해설.

알고스팟/알고리즘 2013.10.22 21:45




일단 문제 원문 부터 보자.


Problem

You have just got the best gift ever, a Pogo stick. The pogo stick is something you use to jump off the ground while standing on it. 

This Pogo stick is a special one: the first jump will move you a distance of 1 unit, the second jump will move you 2 units, the third jump will move you 3 units and so on. You can jump in only four directions using this stick: north (increasing y), south (decreasing y), east (increasing x) or west (decreasing x). 

Now you want to play a game in your backyard, which we model as an infinite plane. You are standing with your stick in at point (0, 0) and you want to go to point (XY). 

The point (XY) will never be (0, 0), and it will always be reachable from your starting point. 

Check the output section carefully, because the required outputs for the small and large datasets are not the same.

Input

The first line of the input gives the number of test cases, TT test cases follow, one per line. Each line consists of 2 integers separated by a single space, X and Y, the coordinates of the point you want to reach.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is a string represents the directions of the moves, for example if you are going to move north then south then east then west, this string should be NSEW. 

For the small dataset, the output is considered correct if it does not take more than 500 moves to reach the destination in each test case. 

For the large dataset, the output is considered correct if it reaches the destination point in the minimum possible number of moves. 

If there are multiple correct solutions, print any of them.

Limits

Small dataset

1 ≤ T ≤ 50.
0 ≤ |X|, |Y| ≤ 100.

Large dataset

1 ≤ T ≤ 100.
0 ≤ |X|, |Y| ≤ 106.

Sample


Input 
 

Output 
 
2
3 4
-3 4
Case #1: ENWSEN
Case #2: ENSWN



요약하면,

스카이 콩콩을 타는데, (0,0)에서 시작해서 동서남북 4방향으로 뛴다. (대각선 이동은 불가). 이 스카이 콩콩은 특별해서

 번째에  만큼을 동서남북중 한 방향으로 이동해야 된다. 


Image: Underwater Pogo Stick 오지게 어려워 보인다..


자 여기서 문제는, 2D 좌표상의 점 (x, y) 가 주어 졌을 때 (0, 0)점에서 시작해 이 스카이 콩콩을 최소한( 점프 즉 가 최


)으로 타서 (x, y)에 도달 할 수 있는 방법을 구하여라 이다.


예를 들어보자. (3,4)의 좌표가 주어 졌을 때 물론, 서(-1, 0)동(1, 0)서(-2, 0)동(2, 0)서(-3, 0)동(3, 0) 이렇게 


6번만에 무식하게 이동 한 뒤 마찬가지 방식으로 남북남북남북남북 해서 (3,4)로 이동 할 수 있다.


혹은, 우리의 코드잼 꿈나무 기가막힌 알고리즘 이해를 통하여 WNSEN(서북남동북) 이렇게 이동해서 


5번만에 (3, 4)에 도달 할 수도 있을 것이다.


자 그럼 어떻게하면 효율적으로 (12323231412312, 12323232321115) 이런 원점으로부터 상당히 멀리 떨어진 점이 주어 져도


콩콩이를 타는 방법을 빠르게 구할 수 있을까?


일단 몇가지 정말 단순한 방법부터 알아보자.


DFS, BFS 서치


DFS, BFS에 대한 이해가 없다면 쉽게 말해서, 먼저 쪽으로 간 후 다시 (-1, 0)으로 부터 동서남북. 또  (0, 1)에서 시작해서 동서남북, ....,  쭉쭉 뻗어나가는 식으로 모든 경우의 수를 다 조사하는 방법이 있다. 컴공 새내기가 들어도 엄청 무식해 보인다.

물론, 엄청나게 멀리 떨어진 좌표에 대해선 좆나 오래 걸릴 것이다. 




자 그럼 이제 아주 효율적인 알고리즘을 알아보기에 앞서 몇가지 짚고 넘어가도록 하자.


몇가지 observations


1)  pogo stick을 한번에 1 unit 씩만 이동한다고 해도 최소한 |X| + |Y| unit 만큼은 이동을 해야 도착 할 수 있다. 돌려 말하면 이 스카이콩콩을  번 만큼 타서 목표 지점  에 도달 한다고 가정할 경우   이 성립함을 볼 수 있다. 


이 경우 최소 1번 이상을 갈려던 방향 반대 방향으로 이동 했다는 뜻이다. 예를 들어 (10, 5)이 목표지점일 경우 동쪽, 북쪽으로 이동해야 하는데 콩콩이의 특성상  번째에  만큼을 이동하다 보니 서쪽, 남쪽으로 한번은 이동 했다는 뜻이다. 


2) 스카이콩콩을  번 만큼 타서 목표 지점  에 도달 한다고 가정할 경우   의 짝홀성 (저 숫자가 짝이냐 홀이냐)은  과 동일하다. 일단 설명에 앞서 어떤 숫자에 "짝수"를 빼거나 더할 경우 


이 숫자의 짝홀성은 변하지 않음을 알 수 있다. (딱히 증명은 생력해도 되겠지??)


마찬 가지로 콩콩이를  만큼 동쪽으로 이동 후 나중에  만큼 다시 서쪽으로 부득이하게 이동해야 하는 경우, 실제론 


 만큼 동쪽으로 이동 했다고 생각 할 수 있다.  중  에 도달하는 점프의 집합을  라 하면 이중에서 반대 방향으로 이동 하는 집합에 속하는 원소는 반대 방향이기 때문에


일단 전체  에서 그 크기 (콩콩이로 뛰는 거리) 만큼 - 로 카운트 된다. 즉  만큼 빼지는 것이다. 


마찬 가지 방향으로  방향도 설명 할 수 있고,  의 짝홀성이 같으니 더한 값,  도 짝홀성이 같다.





이상으로 x,y 에 도달 하는 어떤 일련의 moves, 그리고 moves 들의 합 (n^2 + n) /2가 있을 때 이 답은 반드시 위의 두가지 조건을 만족해야 함을 보였다.


자 이제, 충분 조건으로 위의 조건을 만족할 시 (0, 0)에서 (x, y)로 가는 답이 존재 함을 보이자. 



induction 을 써서 쉽게 증명 가능하다. 일단 편의상 마지막  점프가 북쪽이라고 가정 하자. 그럼  점프 안에  만큼 이동해야 한다. 이 좌표 또한 위의 두가지 조건,   과 짝홀성을 만족함을 보여 준다면 점프 점프 점프 점프 해서 결국엔 (0, 0)에서 (x, y)로 뛸 수 있을 겄이다.


편의상  라고 가정하자. (나머지 경우에 관해서도 symmetric 하게 증명 가능하다.)


자 두가지 경우의 수가 있다.  인 경우,   에서 


그냥 양변에  을 빼서  이 성립함으로


첫번째 조건을 만족. 짝홀성의 경우,  이 짝수 일 경우 양변의 짝홀성에 영향을 주지 않으므로 만족.  이 홀수 일 경우, 


짝홀성을 양변 모두 바꿈으로 이 경우에도  을 만족한다.


이제 콩콩이로 뛰었는데 X 축의 반대 방향으로 가버린  의 경우를 생각 해보자.  이 경우, 


 (가정에 의해서  이므로)



이므로 첫번째 조건이 성립한다.


마지막으로 base case 즉  에 대해서는 쉽게 각각 (-1, 2), (1, 2)의 경우 2만큼 남쪽으로 이동시 (-1, 0), (1, 0)이 되며 이 두가지 경우에 위의 두조건이 성립함을 쉽게 보일 수 있다. 따라서 induction 성립! 


즉, 저 두조건을 만족하는 일련의 1, 2, ..., N-1, N 점프들이 있을 경우 (0, 0)에서 (x, y)에 도달 할 수 있음을 보였다.




자 이제 본론으로 돌아가서 저 두 조건을 만족하는 최소한의 N을 찾았다고 하자. (아래의 코드를 통해서 찾을 수 있다.)


N = 0
  sum = 0
  while sum < abs(x) + abs(y) or (sum + x + y) % 2 == 1:
    N += 1
    sum += N

이제 마지막으로 확인해야 할 점은, 

과연 저 위의 코드로 찾은  =  (찾고자 하는 최소값)?   이냐 하는 질문이다.

이건 쉽게 보여질 수 있다.

일단 

1)  을 포함한 모든 답은 저 위의 두 조건을 만족하는데, 위의 코드에 의해 찾아진 은 by construction

 에 의해 이런  중 최소값이다. 따라서 .

2) 위에서 구해진 은 induction 에 의해 에 도달 할 수 있음을 보였다. 이런 정답중에 이 최소값이 므로 .

1), 2)에 의해 .


이제까지 얘기한 모든걸 종합하는 코드가 바로

def Solve(x, y):
  N = 0
  sum = 0
  while sum < abs(x) + abs(y) or (sum + x + y) % 2 == 1:
    N += 1
    sum += N
  result = ""
  while N > 0:
    if abs(x) > abs(y):
      if x > 0: 
        result += 'E'
        x -= N
      else:
        result += 'W'
        x += N
    else:
      if y > 0:
        result += 'N'
        y -= N
      else:
        result += 'S'
        y += N
    N -= 1
  return result.reversed()



이다. 




실제로 지금 파이썬이 안깔려 있길래 repl.it 들어가서 web python shell에서 코드를 돌려본 결과


Solve(111232,78231)

=> NWSNSENSNWSNSENSNWSNESNWESNWESNWESNWESNWESNWESNWEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENNEENENENENENENENENENENENENEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE

시간이 많다면.. 한번 손으로 해보기 바란다. 아니면 열심히 코딩과 알고리즘 공부를.

설정

트랙백

댓글

구글 코드잼. 아프리카 예선문제 Store Credit

알고스팟/알고리즘 2013.10.17 22:41


올 여름에 미국판 Round 2 까지 갔었는데 아쉽게 Round 3 까지 가지 못했다. 


포스팅을 정리하고 짬짬이 공부해서 내년에는 좀 더 좋은 성과 냈으면 한다.. 


우선 코드잼에 대해 간단히 소개를 하자면 국내에서도 많이 있는걸로 아는 알고리즘 대회의 일종인데 구글에서 매년 연다. 


문제는 보통 small data, big data가 주어지며 small data 는 efficient/intuitive한 observation을 전혀 이용 하지 않은 straightforward


brute force 방식으로도 종종 풀리나 big data 는 의도적으로 사이즈를 크게해, 원하는 방향으로의 알고리드믹한 생각을 하지 않으면


점수를 얻는게 쉽지 않게 해놨다. 


많은 문제들도 있고 실제로 이미 대회가 끝났음에도 불구하고 practice run 을 해볼 수 있는게 장점이며 다른 contestants의 코드를 


볼 수 있는게 또한 장점이다. 또 대회 이후엔 analysis, 즉 주최측에서 원하던 방향의 생각에 대한 답을 올리기도 해서 교육용으로 


좋은 것 같다. 거두절미하고, 코드잼 혹은 알고리즘의 간단한 맛을 보기 위해 analysis가 올라오지 않은 2010 아프리카 예선 문제인


Store Credit 문제를 한번 내가 생각하는 방식으로 풀이해 보도록 하겠다.


일단 문제 원문


Problem

You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).

Input

The first line of input gives the number of cases, NN test cases follow. For each test case there will be:

  • One line containing the value C, the amount of credit you have at the store.
  • One line containing the value I, the number of items in the store.
  • One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.
  • Each test case will have exactly one solution.

Output

For each test case, output one line containing "Case #x: " followed by the indices of the two items whose price adds up to the store credit. The lower index should be output first.

Limits

5 ≤ C ≤ 1000
1 ≤ P ≤ 1000

Small dataset

N = 10
3 ≤ I ≤ 100

Large dataset

N = 50
3 ≤ I ≤ 2000

Sample


Input 

Output 
3
100
3
5 75 25
200
7
150 24 79 50 88 345 3
8
8
2 1 9 4 4 56 90 3
Case #1: 2 3
Case #2: 1 4
Case #3: 4 5




영어가 안되는 분들을 위해 혹시나 해석을 해주신 한 블로거 분의 링크. (http://blog.naver.com/gozilra2000?Redirect=Log&logNo=100125776889)


C 만큼의 돈이 있는데 상점에 진열된 I 개의 물건들 중에서 두 가지의 물건 


을 찾는거다. 그냥 10000만원 있는데 물건 두개사서 돈 합이 10000이 되는 물건 두개를 찾아라! ㅎㅎ; 라는 말이다.



 Solution


 정말 아무런 생각이 없는 답이다. 그냥 의 조합 경우의 수를 일일이 체크 해주면 된다. 0점 짜리 답변.




* Key Observation for Solution *


사실 뭔가 insight 이라 부르기도 뭐하다.  어떤  정렬된 집합이 주어 졌을 때


우리가 찾고자 하는게,  요놈이다.  이 경우  라는 두개의 포인터를 


 에 가르키도록 한다. 만약  라면 당연히 우리가 찾고자 하는  는  이다.


그러므로  를 오른쪽으로 한칸 이동 시킨다. 반대의 경우  를 한 element 만큼 왼쪽으로 감소 시킨다. 


최악의 경우에  가  스텝 만큼 이동하므로,  안에 답을 찾을 수 있다.







 Solution




  그럼 이제, 잘 알려진 sorting algorithm 들을 사용하여 정렬 한뒤, 위의 방식대로 풀면 된다. 코드는 너무 간단 하겠음으로 


생략..






이 문제를 약간 바꾸어, 3 가지 물품을 사서 가격의 합이 C 만큼 되는 경우를 찾으면 어떻게 해야 할까?


물론, 이것도...엄청 간단하다.  코드잼 꿈나무들은 답을 생각해 보시길.

 



설정

트랙백

댓글

Spanning Tree. 스패닝 트리의 갯수.

알고스팟/알고리즘 2013.10.16 05:35




어떤 graph  가 주어졌을 때  모두 가지는 를 의 spanning tree 라고 한다. 


랜덤한 그래프 에 대해서 이런 spanning tree의 갯수는 몇개 일까?


이걸 증명하는데 가장 eigenvalue/determinant의 개념없이 (http://sensprofond.tistory.com/entry/Matrix-Tree-Theorem 이와 관련된


글은 여기 간단히 정리되어 있어서 언급.)  증명하는 방법이 double counting 이다.


spanning tree의 갯수를 두가지 관점으로 센 다음, 식으로 도출 하는건데 제일 깔끔하고 이쁘다.


Pitman의 증명이라 불리는건데, 역시 버클리 대학원 출신인듯 하다,


먼저 spanning tree 갯수를 세는 처음 방식은  개의 unrooted tree, 즉 root이 아직 결정 되지 않은 tree를 하나 뽑는다. 


개의 vertices 중에서 하나를 root 으로 잡아서 정하고 각각의 edge를 뻗어 나가면서 만나는 vertices를 label 할 수 있는 


경우의 수가  이다. 


즉  이다.




이제 두번째 방식으로, 처음 부터 vertices를 하나씩 잡아서, labeling을 하면서 가지를 하나씩 붙여 나가는 structure theorem for 


tress 방식 ( http://luxs1t.tistory.com/211을  생각해 보자.


 개의 노드에  개의 가지를 이미 붙였다고 가정 해보자. (여기선 사실 labeling 보다는, 


어떤 가지를 먼저 붙이느냐가 uniqueness를 결정 짓는다. 사실 labeling을 가지 잇는 순서대로 붙이면 똑같은 말이다.


 


이 경우,   개의 rooted tree 를 가진 forest 가 만들어 진다. (그림 같은 경우, 12개의 노드에 8개의 가지가 이어져 있다. 


그러 므로 4개의 rooted tree).


이제 그 다음 가지를 이을 차례인데, 이 edge는 시작을 아무  개의 초이스 중에서     roots 중 하나로 끝나는 


가지만 이으면 된다. ( roots (자기 자신이 속한 tree의 root 제외. 왜? cycle을 만드니깐) 중 하나를 이어야만 중복된 


트리 세는걸 방지. ****)


그러므로 각각의 단계에서의 초이스 들을 다 곱하면


\prod_{k=2}^{n} n(k-1) = n^{n-1} (n-1)! = n^{n-2} n!.




도출된 두식의 양변의  을 상쇄하고 나면 드디어


 가 나오게 된다.


하지만 이렇게 세어진 스패닝 트리의 갯수는 아래 그림에서 보이는것 처럼


레이블링(distinct nodes)이 어떻게 되느냐에 따라 다른 트리로 보고 갯수를 세기 때문에 정말 고유한 모양의 트리를 세려면 


이 부분을 감안해서 계산해야 된다.









double counting 방식 말고 일반적인 prufer's code를 이용해서 증명한


정리가 잘된 포스팅이 있어 주소를 언급한다. 자세한 설명은 아래 참조.


출처 http://blog.daum.net/eternaljk/6176142





출처 -






설정

트랙백

댓글

Structure Theorem for Trees.

알고스팟/알고리즘 2013.10.15 23:22



어떤 n 개의 vertices를 가진 Tree  가 있을 때 직관적으로 생각해보면 가지를 하나씩 이어 가면, 결국엔 T를 만들 수 있다


이걸 정리한게 아래 명제 이다. 




and 


1)  노드 하나 달랑 있는 앙상한 트리.


2) 


이건 말이 엄청 어려워 보이는데, 사실 별거 없다. 어떤 트리  는 에서 노드 하나 더하고 가지 하나 더해서 


만들어 진다는 것이다.


아주 직관적인데, 간단히 induction을 이용해서 증명하면 베이스 케이스는 trivial 하니 제껴두고



 인  , 를 가정한다. 이 트리의 leaf를 라고 하자. 그럼  는 


(http://luxs1t.tistory.com/admin/entry/post/?id=209) 에 증명된 보조 정리에 의해서 여전히 트리이고  이다.


induction hypothesis에 의해서,  이 이미 존재한다.


고로, leaf  를 다시 붙이면 


 가 성립하므로 증명끝. QED












설정

트랙백

댓글

트리의 노드(vertices) 수가 n개 이면 가지(edges) 수는 n-1 개 이다.

알고스팟/알고리즘 2013.10.15 22:03


어찌 보면 아주 자명한 property 들이다. 하나 하나 씩 증명을 해서 나중에 큰 정리를 할 때 쓰느 거니깐 가볍게 


읽어 봤으면 한다. 이 명제 같은 경우엔 induction 으로 쉽게 증명 가능하다.


일단 base case)


 노드가 1개라면 가지가 없어서 1 - 1 = 0 개 이고. 2개 라면 2 - 1 = 1 개 이다.


이제 induction hypothesis 가  까지 참이라고 가정하자.   의 경우에도 가지수가 


 임을 보여 주면 된다. 




먼저 이전의 보조 증명을 이용하여  개의 vertices 를 가진  의 leaf 하나를 땐다. 


보조 정리에 의해 여전히 tree 이다. 


(http://luxs1t.tistory.com/admin/entry/post/?id=209) 헉 근데 이 트리는 induction hypothesis에 의해 vertices의 


개수가  개 이므로  개의 가지를 가지고 있네? 


아하 그럼 여기다가 아까 때어낸 leaf를 다시 붙여도 (가지 +1개) 총 가지의 수는  이구나.


induction hypothesis 증명 끝.

설정

트랙백

댓글

트리에서 잎(leaf)을 빼도 여전히 트리이다.

알고스팟/알고리즘 2013.10.15 20:17


 

어찌 보면 정말 간단한 증명이다. tree 카테고리의 증명을 쭉 읽어 왔다면, 이해 하기 쉽겠지만


트리에서 잎을 하나 빼면 잎이랑 인접한 노드가 새로운 잎이 되고 트리는 여전히 트리 이다.


주어진 T가 갑자기 그래프 G가 되지 않고 여전히 트리로 남음을 보여 주려면 2가지를 부수적으로 보여야 한다.


1)  이 여전히 acyclic 하다는 점.


2)  이 이어져 있다는 점. (connected).



일단 1)에 관해서는 처음 시작하는  가 cycle 이 없는 상태기 때문에 잎을 하나 제거 한다고 해서 갑자기  에 cycle 이 


생기진 않는다.  이 점은 따로 증명할게 없다.


2) 번을 보여 주기 위해서  의 랜덤한 두 vertices  를 가정 해 보자.


 원래 트리에 속하는 두 점 이다. ( 왜냐 가  속하기 때문이다.)


그럼 두개의 vertices  를 잊는 path  가 존재 한다.


 이기 때문에  은 모두 


 에 여전히 존재 한다. 


다시 말하면  를 잊는 유일한 path 가 여전히   에도 존재 하기 때문에  의 connectedness 부분이 증명 된다. 


QED



설정

트랙백

댓글

every tree has at least two leaves.

알고스팟/알고리즘 2013.10.15 19:56



모든 트리는 적어도 2개의 leaf를 가진다는 명제이다.


생각해보면 바로 이전 포스트에서도 증명 한 것 처럼 


http://luxs1t.tistory.com/207


 이 성립하려면 시작과 끝이 있어야 되는데, 이 시작과 끝점들이 바로 leaves 인 것이다.


시작이 있고 끝이 없으면 똑같은 방식으로 가정법을 이용하여 모순을 도출해 낼 수 있다.


 모든 tree에 leaf 노드가 하나만 존재 한다고 가정하자. 그럼 이 하나의 유일한 leaf 노드  에서 시작해서 


 을 따라 가다 보면 http://luxs1t.tistory.com/207 에서 증명한 것 처럼  을 제외 하고는  이기 때문에 어느 시점에서  가 생겨 버린다.


그럼  는 cycle 이니 모순.


즉 every tree has at least two leavs. 증명 끝




 


설정

트랙백

댓글

Tree의 최소 degree는 1 이다.

알고스팟/알고리즘 2013.10.15 19:42



한 vertex의 degree란 그 vertex에 인접한 가지(edge)의 갯수를 말한다. 어떤 그래프 G의 최소 degree란 


G의 전체 vertex set V에 대해서   를 말한다.


증명 하고자 하는 명제는 "graph G가 트리의 경우 이 최소 degree는 1" 이다.


사실 직관적으로 생각해보면 이 작은 property에 대해 3가지를 생각해 볼 수 있다.


1) 최소 1이기 때문에, 모든 vertex 가 서로 이어져 있다는 점 -> 트리의 정의인 connectedness 부분


2) 최소 degree 를 가지는 vertex (혹은 vertices)는 바로 트리의 leaf 라는 점.


3) 트리의 정의인 "a connected and acyclic graph" 를 만족 시켜 준다는 것이다.



 증명으로 넘어가서 이 property는 3)의 측면에서 쉽게 증명 할 수 있다.


일단 트리이기 때문에 최소한 connected 한 vertices의 집합이다. 그렇기 때문에 


자 이제 증명을 위해서  라고 가정 해보자.


 

어떠한 한 vertex  는  이기 때문에 하나의 neighbor  을 갇는다. 마찬가지로 도 


 를 갇는다. 즉 최소한 2개의 다른 인접한 vertices가 있기 때문에 해당 노드를 거쳐 들어 갔다가 나갈 


수 있는 것이다. 이렇게 반복하다보면 T는 유한하기 때문에 어느 순간  가 발견되게 


된다. (어느 특정한 순간에 방문햇던 vertex를 재 방문 하게 되는 것이다. 왜냐?  



그럼 여기서,  라는 cycle이 생겨 버리는 것이다.


Tree는 cycle이 없으므로 모순. 즉 증명하고자 하는 명제 . QED







설정

트랙백

댓글

tree path의 unique성 증명

알고스팟/알고리즘 2013.10.05 14:08

 

 

트리는 정의에 의하여 Connected 되고 Cycle이 존재 하지 않는 그래프를 말한다.

이런 트리  가 주어 졌을 때 트리의 두 노드  를 잊는 길이 오직 하나임을 증명해보자.

 

 트리 상의 두 노드  에 대하여 두가지 path가 존재한다고 가정하자.

 

 

 

 

 

이런 두개의 길이 존재한다고 가정 했을 때, 어떠한  에 대해서

 

   하지만  인 가 반드시 존재한다. (서로 다른 paths이기 때문에)

 

또한 이 두 paths 모두  로 끝나기 때문에

 

 

 

 이상의 node들은 서로 모드 같다.

 

그러므로  

 

인 cycle을 만들 수 있다.

 

이는 tree definition에대한 contradiction 이므로, 오직 unique한 하나의 path 만이 존재한다.

 

 

설정

트랙백

댓글