[대학교이상] 닥 한문제만 도와주세오 ㅠㅠㅜㅜ

[육토리(kjhoon2002)]

꼭짓점 개수가 n인 임의의 연결그래프의 임의의 두 점 x, y 사이에 모든 꼭짓점을 지나는 길이가 2n 미만인 walk가 있음을 보이시오 

Walk 시작점이 x고 끝점이 y에오

한번만살려주세오ㅜㅜㅜ

- dc official App

[익명(223.38)]

과제풀이하냐?

[익명(59.11)]

트리 잡아서 x-y의 경로의 간선은 한번 나머지는 두번 지나서 모든 꼭짓점을 방문할수있음을 보이면됨

[육토리(kjhoon2002)]

트리에서만 보이면 되는 이유는 먼가욥? - dc App

[익명(106.101)]

walk가 같은점 두번지나면 안되는거엿냐?

[익명(106.101)]

그게 아니면 그냥 n에대해 induction쓰면 바로되고

[육토리(kjhoon2002)]

Walk는 그냥 조때로가면 댐 - dc App

[육토리(kjhoon2002)]

Induction어케 써야함? - dc App

[익명(106.101)]

induction쓰면 될꺼같은데 시도는해봄?

[육토리(kjhoon2002)]

해봤는데 어떻게 써가야할ㄷ지모르겠암 - dc App

[익명(106.101)]

점이 n개잇으면 n-1개를 잇는 길이가 2n-2이하인 walk가잇잖아 connected니까 n-1개점들중에 어떤하나가 나머지점이랑 연결되잇고 그럼 거기서 왓다갔다하면 길이가 2n이하지

[육토리(kjhoon2002)]

그럼 회로가 있는 그래프에선 변을 지워도 꼭짓점 수는 안변하니까 수형도에서만 확인하고, 이 경우에 출발점이 도착점과 같을 때 walk의 길이가 가장 기니까 - dc App

[육토리(kjhoon2002)]

점 n개 중에 1개를 뺀 n-1 개의 임의의 점 하나를 walk의 출발점이자 도착점으로 잡은 다음, 거기서 나머지 하나의 점을 한 번 왕복하면 모든 경우에대해 성립한다 - dc App

[육토리(kjhoon2002)]

어떰? - dc App

[익명(222.107)]

spanning tree의 edge는 n-1개니까 x를 root로 잡고 y가 있는 branch를 마지막으로 방문하게 dfs하면서 y를 만나면 leaf까지 내려갔다 y까지만 오게 하면 됨

[익명(39.7)]

spanning tree(부분그래프로서 수형도인것T)만 생각해주면 n=2일때는 자명하고 n>2일때 T에 x,y외에 1)잎이 있으면 그거빼고도 수형도이므로 induction 가정에서 그거빼고 2n-2번미만 walk잡은후 다시 그거포함시켜서 2n번미만 walk를 잡음.

[익명(39.7)]

2)잎이 없으면 x,y 모두 잎이고 x와 인접한 점을 z라하면 n>2이니 z는 y가 아님. 따라서 T에서 x를 z에서 y까지는 다시 수형도이고 induction 가정으로 2n-2번미만 walk잡고 여기에 xz포함하면 2n번미만의 walk를 잡게됨 끝.

[육토리(kjhoon2002)]

감삼돠 근데, 내가 위 댓글에 쓴 것 처럼 조건에 따른 길의 길이가 가장 길 때는 시작점과 끝점이 같을 때 라는 걸 이용해도 문제없을까? - dc App

[육토리(kjhoon2002)]

이때가 길의 길이가 최대니까, 이 상황이 만족되면 나머지도 다 만족하는 거니까.. - dc App