| [ QuizWit ] in KIDS 글 쓴 이(By): Convex (4ever 0~) 날 짜 (Date): 2001년 1월 13일 토요일 오후 12시 31분 48초 제 목(Title): Re: 그래프.. 원래 3n-6 가 planar graph 의 edge 수 bound 입니다. 환상님이 말한건 Delaunay's Triangle(DT). Voronoi Diagram의 Dual이 됨. 점이 좌표가 fix 되어있다는 가정하에 DT를 그리는 것이기 때문에 edge수가 3n -6 보다 훨 적을 수가 있음. 고로 원래의 문제인 edge 수 maximize 하는 것의 solution이 될 수 없음. 직선이 아닌 edge 를 그어줘야 함. (0,0), (0,1), (1,0), (1,1) 의 4점으로 비교해 볼 것. 원래의 문제가 점 위치는 중요하지 않고 edge수가 최대가 되도록 한다는 문제였다면 planar embedding 문제가 되는데 그거 3n-6 되도록 적당히 배열하면 됨. (원래 edge가 주어진 문제였고 토폴로지를 유지해야 한다면 poly time solution 없다고 생각되고, 여기선 edge가 있는 것이 아니고 점 갯수만 주어진거니깐 삼각형부터 시작하여 insertion method로 가능) --,--`-<@ 매일 그대와 아침햇살 받으며 매일 그대와 눈을 뜨고파.. 잠이 들고파.. Till the rivers flow up stream | Love is real \|||/ @@@ Till lovers cease to dream | Love is touch @|~j~|@ @^j^@ Till then, I'm yours, be mine | Love is free | ~ | @@ ~ @@ |