크르스칼 알고리즘 정당성 증명에서 질문 있습니다.

  • infoefficiency
    infoefficiency

    탐욕적 선택 속성을 증명할 때

    귀류법으로 증명하는 부분이

    정확하게 이해가 가질 않는데

    좀더 자세하게 설명해주실수 있을까요? ㅠㅠ

    귀류법이라고 하면 부정해서 모순한 점을 찾는 것있데

    어떤 부분이 그러한지 정확하게 잘 모르겠습니다 ㅠㅠ

    제 생각엔 귀납법이라고 수정해야 하지 않을까 싶은데...ㅎㅎ

    답변 부탁드리겠습니다 ㅎㅎ

    감사합니다 ^^


    10년 전
5개의 댓글이 있습니다.
  • Neon
    Neon

    안녕하세요. 크루스칼 알고리즘의 귀류법 증명이라 하시면... 일단 온라인에서 쉽게 볼 수 있는 위키피디아 링크(http://ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)를 기준으로 설명해드리는 게 좋을 것 같네요.

    귀류법 증명이란, 어떤 명제 A를 주장하고 싶을 때, 일단 A가 참이 아니라고 가정하자, ... 모순! 그러므로 A는 참이다! 의 꼴로 이루어진 증명입니다.

    문서에서 '정확성 증명' 챕터를 보시면 kruskal 알고리즘으로 생성된 스패닝 트리 Y가 minimum spanning tree가 아니라고 가정하자. ... 모순! 그러므로 Y는 MST이다. 의 꼴로 이루어져 있습니다. 흔한 귀류법 증명의 한 모습이죠.


    10년 전 link
  • Neon
    Neon

    물론 어떤 명제를 증명하는 방법이 하나만 있는 것은 아니므로 귀납법을 통해 kruskal을 증명할 수도 있습니다. 참고하신 문헌(JM북인가요?)을 알려주시면 좀 더 자세하게 확인해드릴 수 있을 것 같네요.


    10년 전 link
  • Neon
    Neon

    위 링크가 깨졌는데. http://ko.wikipedia.org/wiki/크러스컬_알고리즘 입니다.


    10년 전 link
  • JongMan
    JongMan

    해당 증명은 다음과 같은 구성을 갖습니다.

    1. 찾은 스패닝 트리가 MST가 아니라고 가정합시다.
    2. 그러면 찾은 간선 중 MST에 포함되지 않는 간선들이 반드시 있겠죠?
    3. 그러면 그 중 제일 빨리 선택한 간선 (u,v)를 찾읍시다.
    4. 생각해 보니, (u,v)가 있어도 MST로군요.

    쓰고 보니, 여기서 제일 빨리 선택한 간선이란 표현이 좀 부적절한거 같네요. 더 이상 MST가 될 수 없도록 하는 첫 번째 간선 (u,v)라고 하면 좀 더 이해가 쉬울 것 같네요.


    10년 전 link
  • infoefficiency
    infoefficiency

    감사합니다 ^^


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.