Research Space for Linear Algebra & Discrete Mathematics
老師討論的並不是你想的那樣,他是以(1)假設每一個點都有至少有一個點與它相連(2)假設圖中至少有一個點與其他點皆不相連兩種情況去討論以(1)來說因為每個點至少有一個點與它相連,所以才說沒有孤立點,即沒有一個點的degree是0,代表每個點的degree均>=1,而每個點最大的degree為n-1,代表:1<=每個點的degree<=(n-1)而有n個點,根據鴿籠原理,一定會有至少兩個點之degree是相同的以(2)來說因為至少有一個點與其他點皆不相連,所以每個點最大的degree一定<n-1,即代表每個點的degree最多為n-2,又每個點的degree最小為0代表:0<=每個點的degree<=(n-2)而有n個點,根據鴿籠原理,一定會有至少兩個點之degree是相同的希望有解決你的困惑
感謝 邦 的回答大概瞭解了，因為我一直focus 有一點degree = n-1 或 0 。
張貼留言
2 則留言:
老師討論的並不是你想的那樣,他是以
(1)假設每一個點都有至少有一個點與它相連
(2)假設圖中至少有一個點與其他點皆不相連兩種情況去討論
以(1)來說因為每個點至少有一個點與它相連,所以才說沒有孤立點,即沒有一個點的degree是0,代表每個點的degree均>=1,而每個點最大的degree為n-1,
代表:1<=每個點的degree<=(n-1)
而有n個點,根據鴿籠原理,一定會有至少兩個點之degree是相同的
以(2)來說因為至少有一個點與其他點皆不相連,所以每個點最大的degree一定<n-1,即代表每個點的degree最多為n-2,
又每個點的degree最小為0
代表:0<=每個點的degree<=(n-2)
而有n個點,根據鴿籠原理,一定會有至少兩個點之degree是相同的
希望有解決你的困惑
感謝 邦 的回答
大概瞭解了，因為我一直focus 有一點degree = n-1 或 0 。
張貼留言