[질문] 매트로이드라는 개념 아는 사람?

[과제충(211.183)]

최소신장트리를 크루스칼이나 프림으로 만들었을 때

최적해를 보장하는 것을 매트로이드로 증명해야하는데

매트로이드에 대한 자료들은 영어가 대다수고, 국내 자료 읽어도 쉽게 이해 못하겠다 ㅠ

이게 매트로이드의 정의라고 하는데, 하나씩 집합으로 이해해볼 순 있어도

어떻게 그래프랑 접목시켜야 하고, 최소신장트리인걸 증명해야할지 감이 안옴.

알고 있는 지식 조금이라도 풀어주면 많은 도움 될 거 같다 ㅠㅠ

[익명(210.103)]

이건 수잘갤 가서 물어봐야 됨. 근데 거기 형들도 영어 자료 던져줄거임

[ㅁ(119.202)]

너가 말하는게 Graphic Matroid일텐데 Independent Set을 E의 부분집합중 사이클이 안생기는 간선집합의 집합으로 정의해봐. edge set에 사이클이 없으면 그 부분집합도 사이클이 없다는건 자명이니 1번은 걍 되고, 2번은 수학적 귀납법으로 증명 가능했던것 같음.

[ㅁ(119.202)]

그러면 사이클이 없는 edge set의 집합이 independent가 되니까 Maximal Independent Set을 찾는 크루스컬 알고리즘이 사용 가능하고, 사이클이 없는 edge set중 최대크기가 spanning tree일거라는건 직관상 당연하니 최대 가중치 합을 가지는 spanning tree를 찾을 수 있음. 여기서 가중치만 -로 바꿔주면 비슷하게 최소 가중치 합을 가지는 spanning tree를 찾을 수 있고, 따라서 크루스컬로 MST를 찾을 수 있음.

[ㅁ(119.202)]

크루스컬 알고리즘이 최대 가중치를 가지는 원소만 그리디하게 뽑아서 independent 유지할때까지 쭉 뽑으면 그게 maximal set이 된다는 건데, 증명은 나도 몰라. matroid 성질 잘 쓰면 될텐데 주의깊게 안봄 그래서 크루스컬 자체의 타당성은 못말해준다 ㅈㅅ

[익명(125.31)]

그거 증명을 Rado-Edmonds Theorem이라고 하니까 찾아보셈

[과제충(211.183)]

진짜 고마워 ㅠㅠ 조금씩 희망이 보이기 시작한다. 여기서 independent 하다는 개념을 잘 몰라서 그러는데, 선형대수에 대한 이해가 필요해? 독립적인 것이 그래프상에서 의미하는 게 뭔지 모르겠다. 독립적이지 않으면 어떻게 돼?

[익명(175.223)]

incidence matrix라고 정점이랑 간선의 연결관계를 행렬로 나타난 게 있는데, 여기서 사이클이 생기면 이 행렬에 일차종속인 열벡터가 생김(열끼리 더했을 때 0이 나오니까)

[과제충(211.183)]

와.. 조금씩 감이 잡힌다. 고마워.. 매트로이드 정의 2번에서 a u {x}로 시작하는 부분은 어떻게 이해 해야돼?

[ㅁ(119.202)]

1,2 성질의 모티베이션을 말하는거면 난 모름..... 그정도로 전문가가 아니라.... 저 위에 유동이 더 잘아는듯 하니 저 유동한테 물어봐바

[익명(175.223)]

matroid는 기본 모티브가 벡터의 독립 개념을 +, 스칼라배같은 벡터 연산 없이 집합 연산만으로 어떻게 추상화시킬 건가 중점을 두고 있는건데 A, B를 기저 집합으로 바라보면 단순히 차원이 높은 B가 A의 원소와 독립인 기저 원소를 하나 준 걸로 생각할 수 있음

[익명(211.246)]

이거 그리디 알고리즘 쓸 수 있는 이유: 메트로이드가 옵티멀 서브스트럭쳐랑 그리디 프로퍼티 만족하는 거라고 증명 배웟는데 까먹음

[레전드(211.183)]

오 그 두 개념이 매트로이드랑 연결되는거야? 어떤 방식으로 이어지는거지?

[익명(211.246)]

아 이거 커넥티드 컴포넌트에 계속 작은 거 더해가는 걸로 증명하던데

[익명(110.35)]

여기 도대체 무슨말 하는거냐

[EN_SA(encludingsalt)]

찐알고리즘얘기

[익명(128.134)]

http://www.secmem.org/blog/2019/05/15/introduction-to-matroid/

[작성자(211.183)]

고맙다 ㅠㅠㅠㅠ 몇 없는 국내자료다