알고리즘 - 그래프 - MST 최소신장트리 - 3가지 성질

[@kkkl7074]

유튜브에서 양질의 강의를 시청 할 수 있게 올려주셔서 너무 감사합니다. 이해가 너무 잘됩니다

[@forheuristiclifeksh7836]

22:00

[@mindolll]

교수님 트리의 성질중에서 새로운 엣지를 삽입할 때 엣지를 포함한 사이클이 생성된다는 게 잘 이해가 안가는데 무슨 의미인지 알 수 있을까요? 트리에는 사이클이 생길 수 없지 않나요?

[@ChanSuShin]

트리 자체는 사이클이 없지만 에지를 하나 추가하면 사이클이 생길 수 있다는 의미입니다. 그러면 사이클에 포함된 에지를 골라 다시 제거해야 다시 트리가 됩니다. 이왕이면 가중치가 작은 에지를 제거해야 좋겠죠^^

[@mindolll]

@@ChanSuShin 감사합니다~