生成樹中頂點數(shù)和邊數(shù)分別為n,n-1.
這個問題十分簡單,上面兩位已給出了正確答案,如果你還不滿意,我給你再解釋一下,生成樹首先是一個生成子圖,其次它是一個樹,所謂生成子圖是包含圖中所有頂點的子圖,原圖有n個頂點,故生成樹也應有n個頂點,關于樹的定義很多,通常定義為沒有回路的連通圖,或者定義為最小連通圖,(即刪去任意一條邊就會不連通的連通圖),n個頂點的最小連通圖至少有n-1條邊,如果少于n-1條邊一定不會是連通的,如兩個頂點的圖必有1條邊才能確保它連通,3個頂點的圖必有2條邊才能確保它連通,等等,又n個頂點的最小連通圖至多有n-1條邊,否則一定會有回路,如果有了回路,刪去回路中的任意一條邊仍會連通,這樣它就不是最小連通圖了,故生成樹不多不少恰有n-1條邊.
上面給了你直觀的解釋,嚴格證明圖論書中均有,希你看看.