최소신장트리를 크루스칼이나 프림으로 만들었을 때
최적해를 보장하는 것을 매트로이드로 증명해야하는데
매트로이드에 대한 자료들은 영어가 대다수고, 국내 자료 읽어도 쉽게 이해 못하겠다 ㅠ
이게 매트로이드의 정의라고 하는데, 하나씩 집합으로 이해해볼 순 있어도
어떻게 그래프랑 접목시켜야 하고, 최소신장트리인걸 증명해야할지 감이 안옴.
알고 있는 지식 조금이라도 풀어주면 많은 도움 될 거 같다 ㅠㅠ
증명 제외하고 개념만이라도 제대로 알고싶으니, 최대한 쉽게 설명해주면 감사하겠음 ㅠㅠ
선형대수에 대한 이해가 필요할까?.. 알고리즘을 증명하기만 하면 되는 거긴한데
증명은 뭘로 함?
증명보조기 씀?
글쎄.. 증명이란 걸 해본 게 없어서. 모르겠다. 완전 엄밀하게 하진 않고, 발표 구색 맞춰서 어느정도 납득갈만큼만 하면됨
그냥 청중들이 알기 쉽게 말로 풀어서 하는 수준?
우선 matroid 정의에서 empty set이 I에 들어간다가 빠진거같네요 그래프 G가 있으면 E(G) 위에 edge set F가 spanning forest를 만들면 independent하다고 하면 이거는 matroid가 됩니다(graphic matroid)
공집합이 I에 들어간다는 건 어떤 의미인가요?
Matroid의 동치 정의가 여럿 있는데 그 중 하나가 대충말해서 어떤 weight를 가져오건 greedy algorithm이 maximum weight independent set를 찾는다는겁니다.
지금보니 2에서 부등식도 뭔가 이상하네요. |A|가 |B|보다 작을 때 여야 합니다
감사합니다...
한가지만 더 여쭤봐도 될까요? ㅠㅠ independent라는 개념이 핵심인 것 같은데, 해당 개념을 잘 모르겠습니다. 만약 독립적이지 않을 경우엔 어떻게 되나요?
그냥 matroid에서 X의 subset중에 I에 있는 애들을 'independent'하다고 부르는 겁니다. definition이에요
Oxley의 Matroid Theory 책에서 1.1이랑 1.8을 보시거나, 아래 링크의 글을 보시면 원하시는걸 아마 얻으실 수 있을겁니다.
https://jeremykun.com/2014/08/26/when-greedy-algorithms-are-perfect-the-matroid/
진짜 고맙습니다. 공부 해보겠습니다.