최소 스패닝 트리가주기 속성이 지정한 가장자리 만 사용할 수 없습니까?[복제]

Question

>

이 질문은 이미 여기에 답을 가지고 있습니다 :

어떤 모서리가 어떤 모서리가 아닌지 (1 답변)

Closed 4 개월 전

방금 "최소 스패닝 트리"(MSTS)를 이해하기 시작했으며주기 재산을 가로 지르 셨습니다. Jon Kleinberg와 Eva Tardos의 책 - 알고리즘 디자인을 언급하고 있습니다. 이 책에서 작성된 재산의 진술은 다음과 같습니다 :

모든 가장자리 비용은 별개의 것으로 가정합니다. C가 G에서 어떤 사이클 일 수 있고, 가장자리 e= (v, w)가 C에 속한 가장 값 비싼 가장자리가된다. 그 다음 e는 최소한의 스패닝 트리에 속하지 않는다.

이제 나의 의심의 여지가있는 것입니다 : 그래프의 가장자리 (뚜렷한 양의 가중치를 가진 가장자리가없는 그래프)는주기 속성을 만족시키지 않는 유일한 것들을 만족시키지 않거나 다른 가장자리가있을 것입니다. MST에 속하지 않고이 속성이 적용되지 않습니다.

그러한 가장자리가 존재하는지 여부에 대해 논쟁하기 위해 증거를 일으킬 수 없습니다. 일부는 이것을 증명할 수 있습니까?

Answer 1

$ G $ 에서 $ e $ bad < / $ G $ 에서 $ e $ 의 사이클이 최대 무게가 있습니다.

$ {\ cal b}={e ~ | ~ e $ 은 $ g \} $ 모든 나쁜 가장자리의 컬렉션이됩니다.

귀하의 질문은 그래프 $ (g - {\ cal b}) $ $ g $ (모든 가장자리 무게가 별개의 것으로 가정). 대답은 예입니다!

이를 증명하기 위해 $ (g-\ chal b}) $ 은 acyclic입니다.

$ (g-\ chal b}) $ 은주기가 포함되어 있다고 가정합니다. $ c $ . $ C $ 은 $ g $ 에도주기를 관찰합니다. $ ^ * $ 사이클 $ C $ 의 최대 무게의 가장자리가되도록하십시오. 이제 $ ^ * $ 은 bad 가장자리이므로 그래프 $ 첫 번째 장소 $ . 이는 $ (g-{\ cal b}) $ 은 acyclic입니다.

Answer 2

죄송합니다. 귀하의 질문을 이해하지 못했지만,이 가장자리가주기가 아닌 경우 가장자리가 아니라면 가장자리가 아니라는 것이 가능하지 않은 것입니다.

여기 내 대답이 있습니다.

그래프 G에 가장자리 (u, v)가 있다고 가정 해 봅시다. 이것은주기의 일부가 아닙니다.이것은 v에서 v가 가장자리 (u, v)가 아니라는 경로가 없다는 것을 의미합니다. 가장자리 (u, v)가 MST에 없으면이 MST에서 u에서 v로부터 경로가 없어도 MST가 분리되므로 모든 MST가 전혀 연결되지 않음을 의미합니다. 따라서 가장자리가 사이클의 일부가 아니면 그래프의 MST에 있어야합니다.