$ G $ 그래프가 있다고 가정 해 보겠습니다. 여기에서 가장자리 하나 (모든 가장자리)를 선택합니다. 엣지가 포함되어 있습니까?
답은 예라고 생각합니다. 왜냐하면 우리가 무엇을하든 우리가 선택한 바로 그 엣지가 포함되도록 항상 스패닝 트리를 만들 수 있기 때문입니다. 물론 더 공식적인 증명은 필요합니까?
댓글
- 당신은 ' 비공식적 인 증거도 작성하지 않았습니다. 본질적으로, ' " 답은 예이므로 예라고 답했습니다. "
답변
초기 그래프 $ G $를 연결해야하거나 스패닝 트리가 전혀 없습니다. (각 구성 요소에 동일한 인수가 적용되면 모든 그래프에 선택한 에지를 포함하는 스패닝 포리스트가 있음을 보여줍니다.)
Let $ G = (V, E) $ 연결된 그래프, $ T $는 임의의 스패닝 하위 트리이고 $ e $는 모든 edgein $ E $이되도록합니다. $ e $를 포함하는 스패닝 트리가 있다고 주장합니다. $ e \ in T $이면 완료됩니다. 그렇지 않으면 $ T + e $에는주기가 포함됩니다. 이주기에는 반드시 하나 이상의 에지 $ e “\ neq e $ (실제로는 최소 2 개 포함)가 포함됩니다. $ T + ee”$는 $를 포함하는 스패닝 트리입니다. e $.
$ T + ee “$가 실제로 스패닝 트리임을 스스로 증명해야합니다.
답변
나무에 가장자리를 추가하면 고유 한주기가 발생합니다.이주기에서 가장자리 (추가 한 가장자리와 다름)를 제거하여 나무를 되 찾을 수 있습니다.이 새 나무에는 추가 된 가장자리가 포함됩니다.
댓글
- ' 정확히 제가 말한 내용입니다!
- 예,하지만 나는 더 적은 단어로 말했다. 🙂
- 내 7 개의 문장이 정말 3 개로 요약되어야하기 때문입니다. 5 개가 있습니다. 사이트에 답변되지 않은 수천 개의 질문 이 있습니다. 이러한 질문 중 일부에 답변하는 것이 필요하지 않은 질문에 대해 중복 답변을 게시하는 것보다 '
- 그런 다음 기존 답변을 읽으십시오. s를 게시하기 전에.
- 아무것도 필요하지 않습니다 -어쨌든 어떻게 시행 할 수 있습니까? 그러나 일반적으로 답변은 새로운 것을 제공해야하며, ' 모르는 경우 ' 그것을 어떻게 알 수 있습니까? ' 이미 말한 내용은 '입니까? 모두 같은 말을하는 답변이 여러 개 있으면 페이지가 복잡해 지지만 ' 2 개만으로는 큰 문제가 아닙니다. 짧은 요약 형식의 답변을 게시하는 것은 기존 답변이 길 때 확실히 가치가있을 수 있습니다. 나는 단지 '이 특별한 경우에 아무것도 추가하지 않는다고 생각합니다.