|
:: 게시판
:: 이전 게시판
|
- 모두가 건전하게 즐길 수 있는 유머글을 올려주세요.
- 유게에서는 정치/종교 관련 등 논란성 글 및 개인 비방은 금지되어 있습니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
15/06/04 19:16
헤헤 마지막줄만 읽고 외워야지 하다가 야곱의 여우? 성경에 나오는 일화인가 하고 검색..
http://math.mit.edu/~fox/
15/06/04 19:33
원본입니다.
Connected matchings in graphs of independence number 2 by Sara Kim https://math.mit.edu/research/highschool/primes/materials/2014/conf/4-2-Kim.pdf
15/06/04 19:58
음 대단한 소녀군요,,
일단 간단히 설명을 드리자면 dsjlfkadjsvusiofuiowejfkldflksajdkfl 이라서 dovuasjfdlkwdvlksoiwefjsdklvnowieif 이 성립되고 dkjfdlksjflkasdjflaksdaksdf 의 증명이 자연스럽게 유도되는 것입니다,, 간단히 설명하기 어렵네요 휴... 간단히 설명 드렸고 다른 분이 자세히 설명해 주실겁니다.
15/06/04 20:18
음 근데 어제 이게 그렇게 대단한 증명은 아니라는 수학 전공자 분 리플도 봤던 것 같은데
확실히 아는 분이 등장해서 설명해주셨으면 좋겠네요
15/06/04 20:27
수알못이지만 그래프에 관한 거고 라우팅에 응용할 수 있나보네요. 그래서 저커버그가 관심을 가진 것 같고. 라우팅 알고리즘 배울 때 그래프 뭐시기도 본 것 같은데 흐흐 ㅠㅠ 뭔가 획기적인 이론인가보네요.
우리 딸도 보스톤 보내는게 꿈인데... 부럽다 흐흐
15/06/04 20:30
그럼 저 이론이 맞다고 가정하고 처리하면 아프리카 오지까지 와이파이 연결할 수 있는거 아닌가요? 그걸 실현하기위해 증명과정이 필요한건가요?
뭐만 증명되면 뭐 된다. 라는게 많은데 그럼 그걸 가정하고 뭐하면 되는거 아닌가요?
15/06/04 20:32
스탠포드와 하버드의 교수들이 서로 데려갈려고 한 소녀의 논문이군요...결국 반반 다녀보고 어디서 졸업 할지 결정하라고 하고 또 주크버그가 러브콜도 했다던데...아무튼 대단한 소녀입니다.
논문 잘 봤네요.....
15/06/04 21:09
상당히 흥미롭군요. 벡터함수의 조합과 집합기호를 활용한 시놉시스로 이어진 공식인데,
n-1의 수렴하는 약간의 오류만 수정하면 졸업논문으로 손색이 없어 보입니다.....
15/06/04 21:29
이해하면 의외로 간단합니다.
맨처음 그림은 아마존에 와이파이가 터지는 그림입니다. 이후 전개를 보면 각각의 점이 기지국. 그것들이 세워지면서 서로 연결되어가는 과정을 보여주고 있죠. 연결되는 점들은 sk, kt같은 통신사 기지국이 서로 연결되는 과정이구요. 결론. 기지국 하나 이상, 열 세개 이하면 아마존에도 와이파이가 터진다는 겁니다. Q.E.D.
15/06/04 23:15
이것만 보고는 이해를 못하구요
https://math.mit.edu/research/highschool/primes/materials/2014/conf/4-2-Kim.pdf 이거 읽으시면 다들 이해하실듯
15/06/05 02:05
겨우 이런거 가지고~
간단한걸 너무 어렵게 증명했네요.... 제가 증명해 보이고 싶지만,,, 댓글란이 좁아서 생략합니다....???
15/06/05 02:33
4n-1 vertices 그래프를 이야기하면서 conjecture 페이지 그림은 왜 5각형이지? 크크
영어만 읽을 수 있으면 보통 중고등학생도 2시간 정도 투자하면 충분히 이해할 수 있을 수준이니 굳이 설명충으로 변신할 필요는 없겠군요!
15/06/05 04:21
Graph theory 문제 중의 하나로 수학하시는 분은 많이 하시는 것 같고, 공학에서도 학부 고년차 올라가면 배우는 CAD나 알고리즘 관련 수업에서 집중적으로 가르치는 분야입니다. 어떤 문제 풀이를 할 때 (예를 들어 n명의 서로 사이좋고 사이나쁜 사람이 있고 k<n개의 테이블이 있으면 어떻게 앉혀야 가장 사이나쁜 사람들이 같은 테이블에 앉을 숫자를 줄일 수 있을까?) 그래프로 치환해보면 이미 증명이 나와있는 경우도 있고, 풀기도 쉽고해서 이런 쪽으로 응용하곤 합니다.
우선 문제 풀이를 하자면... 그래프는 그냥 도형이라고 생각하시면 됩니다. 점 (vertex; 복수형은 vertices)와 선 (edge; edges)가 있습니다. 점들이 다 연결되어야할 필요는 없습니다... 보통 그래프는 앞글자 따서 G라고 보통 호칭하고 G가 V와 E라는 각각 점과 선의 집합의 pair, G = (V, E)라고 부르곤 합니다. 예를 들어 삼각형이 있고 각 점을 A, B, C라고 부른다면 V = {A, B, C}이고 E = {AB, BC, AC}입니다. independence set은 V의 부분집합이면서 (그러니까 점들의 집합이겠죠) 각 점들이 서로 연결되지 않은 상태를 이야기합니다. 그리고 independence number는 가능한 independence set들 중 가장 큰 것의 크기입니다. 예를 들어 삼각형의 independence number는 1입니다. A를 고르든, B를 고르든, C를 고르든, 고른 점과 선으로 연결되지 않은 다른 점은 삼각형내에 없습니다. 고로 1입니다. 반대로 사각형은 2입니다. 첫번째 그림에서 5각형 두개가 있는 것은 4n-1에 해당하는 그래프는 아니지만, independence number가 2인 그래프를 예시로 보여준 것 같습니다. 다시한 번 말씀드리지만 모든 점들이 연결되어있어야 할 필요는 없고, 오각형 2개가 함께 하나의 그래프입니다. 점 A, B, C, D, E가 다 연결되어있고, F, G, H, I, J가 또 서로 연결되어있기 때문에, independence set은 반드시 {(A, B, C, D, E 중의 하나), (F, G, H, I, J 중의 하나)}가 될 수 밖에 없습니다. 고로 independence number는 2입니다. 단 하나 아쉬운 점은 이런 슬라이드에서는 1<=n<=13에 대해 증명을 기왕 했다면 4n-1개의 점을 가지면서 independence number도 2인 좋은 예시를 하나 찾아서 넣었을 수도 있었겠는데.. n=1 proof는 자명하고, n=2 proof는 딱 봐서는 모르겠지만 맞는 것 같습니다. General case를 두고 증명을 하는데 Case 3가 n-2개의 maximum degree가 있는 경우를 이야기하므로 n=1, n=2에 대해서 먼저 증명을 한 것 같습니다. 아니면 Case 3는 음수를 두고 증명을 하게 되니까요. 이 슬라이드에서 alpha(G)는 G의 independence number를 이야기합니다. delta는 설명된대로 maximum degree인데, degree는 간단히 말해서 한 점에 연결된 선들의 숫자를 이야기합니다. maximum degree는 가장 선이 많이 연결된 점에 연결된 선 숫자를 이야기하고요. 삼각형은 각 점이 degree가 2입니다. 한 점에 두개씩 선이 연결되어있으니까요. 사각형도 모든 점의 degree는 2입니다. 고로 삼각형 사각형 모두 maximum degree는 2입니다. 그리고 이 슬라이드에서 delta는 G의 maximum degree가 아니라 /G의 maximum degree입니다. /G는 선들이 역전된 상태를 이야기합니다. 간단히 말해 점들끼리 이미 선이 연결되어있다면 지우고, 선이 연결되어있지 않았다면 선을 연결한 상태의 그래프입니다. 삼각형의 경우 역전된 형태는 선이 아무 것도 없는 점 세 개가 /G입니다. 사각형은 X 형태겠네요. Hall's theorem은 Hall's marriage theorem이라고 해서 bipartite graph와 관련된 증명입니다. 이건 생략합니다. 문제는 말로 설명하면 재미있습니다. Proof 부분은 /G가 역전된 상태임을 고려해서 각 case 별로 P와 Q set의 크기가 얼마인지를 고려해서 푼 것 같습니다. 한 가지 이해가 안 가는 부분은 Case1의 proof 부분입니다. 분명히 G는 4n-1 vertices를 갖고 있다고 했는데 P 사이즈가 n, Q 사이즈가 2n이고 (일단 그림에서 보면) vertex v 가 따로 떨어져있으니 총 vertices 숫자가 n+2n+1=3n+1인데, 잘 이해가 안 갑니다. 분명히 그 전 슬라이드 보면 P, Q, {v}가 완전히 disjoint (서로 부분집합이 없는 상태)이고 이 셋의 합집합이 G인데... 그리고 슬라이드를 보니까 증명 부분만 그림 파일로 되어있고 앞부분은 다 txt로 되어있는 것을 보니 따로 슬라이드를 각각 작업해서 하나로 붙인 것 같습니다; 이렇게 되면 본인에게 물어보지 않으면 왜 이렇게 적었는지 알 수가 없겠네요. 아마 발표까지 된 슬라이드라면 증명은 확실히 맞겠지만 (거기다가 지도 연구원이 있다면) 뭔가 생략된 부분이 많아서 이해하기가 어렵네요. 그런 점을 차치하더라도 훌륭한 학생인 것 같습니다. 학부생들도 그래프 배우고 이렇게 문제 하나 풀어서 증명하기 쉽지 않을 것 같습니다.
15/06/05 09:10
귀류법으로 포섭하는 과정에서 논리가 틀린 것 같고, 이 문제를 푸는데 있어서 매듭을 자르는 칼도 아니네요. 고등학생이 이런걸 한다는 것은
진짜 놀라운 일인것 같아요. 난 그 나이 때 정석책 달달 외우면서 수능 수학 성적 안나온다고 스트레스 받고 있었는데 말이죠. ㅜㅜ
15/06/05 10:06
네, graph theory 이해를 하고 무언가 풀려고 하는 것이 좋은 모습이라고 생각합니다.
Case 3 증명은 다시보니까 이해가 가네요. 전체 vertices 숫자가 4n-1이고 Case 3의 가정이 delta <= n-2인 경우니까, |P_v|의 maximum은 n-2가 되고 |Q_v|의 minimum은 전체 vertices 숫자 - |P_v|의 maximum - v라는 vertex = 4n-1 - (n-2) -1 = 3n이 되네요. 그러면 (inequality가 맞겠네요. |P_v|가 작아지면 |Q_v|가 커지고 그러면 좌측이 작아지니까... 마지막 문장은 Hall's theorem 이용해서 푼 것 같습니다. Case 1이 delta >=n 인 경우고 Case 2가 delta = n-1인 경우니까 결론적으로는 모든 delta의 경우에 대해 n<=13이면 증명이 되는 것 같습니다.
|
||||||||||||
