1. 首頁
  2. 問答
  3. 圖算法

圖算法

2012-05-22 42 views
1

設G是具有n個頂點，其中沒有一個是孤立的， 和n-1條邊，曲線圖，其中n≥2顯示使得G包含至少兩個頂點度 1.圖算法

我已經通過使用屬性總和度= 2 | E |。 使用鴿子洞原理可以解決這個問題嗎？

來源

2012-05-22 Saurabh

回答

1

我想不出使用鴿巢原理來解決這個一種合適的方式，我會做這樣的：

總和度= 2 - 2 = 2 | E |由於沒有頂點可能被隔離，所有的頂點都必須至少有1個度，所以有n-2個「備用」邊緣要連接。 N-2的東西融入n位意味着至少2必須爲空（這類似於鴿巢原理，但那種對面）這樣至少2個頂點必須有度1

我想你」 d最好在這裏問這樣的問題：https://math.stackexchange.com/

來源

2012-05-29 07:43:45 Helen

相關問題

 相關問題