推 lovefo:嗯 我懂了 謝謝 03/23 21:21
※ 引述《lovefo (lovefo)》之銘言：
: Write a proof for the following statement:
: Given an undirected tree graph,when we add an edge to the graph,the graph
: then have a Hamiltonian cycle.Prove that that this tree graph is a chain graph.
: (A chain graph G(V,E) has V={V1,V2,......,Vn},E={(V1,V2),(V2,V3),...,(Vn-1,Vn)}
: 請問這題要怎麼證??
: 完全沒有頭緒
: 拜託了
先證Hamiltonian cycle就是整個圖形
因為是tree所以e=n-1
加入一個edge得到e=n
Hamiltonian cycle有n個edge
故可知即是整個圖
接下來就好辦了，simple cycle去掉任一edge即為chain
故推得原圖為一chain
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.25.160