[일반] 너무 당연한 증명 질문

[기괴공학도(mecheng98)]

유향 그래프 G = (V, E)가 주어졌을 때, 다음 주장을 증명하라:

G의 임의의 두 정점 간에 보행(walk)이 존재하면,

이 두 정점 사이에는 길이가 |V| - 1 이하인 경로(path)가 존재한다.

이런 건 어떻게 증명해야 하나요? 1시간 넘게 고민 중이에요.

[sertygg(sourkiwi0708)]

|V| 에 대한 귀납?

[기괴공학도(mecheng98)]

그러네요.

[ㅅㄲㅁㅇ(as1392)]

없다고 가정하면 길이가 최소인 경로를 잡고 비둘기집으로 같은 점을 두번방문하는게 생기니까 길이를 줄일 수 있으므로 모순

[기괴공학도(mecheng98)]

[lp(24.3)]

보행이 존재한다면 경로가 존재함을 보행에 대한 귀납으로 증명하고, 모든 경로의 길이는 |V| - 1 이하임을 경로에 대한 귀납으로 증명하면 되지 않을까요?

[기괴공학도(mecheng98)]

죄송하지만 "보행이 존재한다면 경로가 존재함을 보행에 대한 귀납으로 증명하고"를 어떻게 하는지 모르겠습니다. 원래 선생님처럼 풀려고 했는데 잘 안 돼서요.

[익명(49.143)]

보행의 길이에 대해서 수학적 귀납법을 써서 증명하면 됨. 주어진 보행이 경로라면 자명하고, 경로가 아니라면 어떤 점에서 쭉 보행을 따라서 진행하다가 다시 그 점으로 돌아오는 경우가 항상 존재하는데, 그 닫힌 보행을 제거하면 길이가 더 짧은 보행이 되므로, 귀납가정을 사용할수 있음.

[기괴공학도(mecheng98)]

그렇군요 감사합니다

[coco(175.196)]

시골 사람이 처음 서울와서 서울역에서 택시를 타고 청량리를 가는데 아까 봤던 건물이 또 보이면 택시기사가 시골사람을 속이는것임. 이때 그 건물에서 다시 그 건물로 오는길은 보행에서 제거 할 수 있음. 이렇게 계속하면 경로가 만들어 짐.

[기괴공학도(mecheng98)]

네, 감사합니다. - λ