→ Sfly :2.是鴿籠原理的直接推論 06/30 07:50
→ arcadian3 :能請樓上說明清楚一點嗎?謝謝 06/30 15:08
1. prove that a connected graph has k vertices of odd degree (k>0)
there are k/2 paths, no two of which have common edge that cover
all edges in the graph.
這題我看曉園出的解答是這樣的
by corollary: in any graph, there is an even number of vertices that
have odd degrees. 所以 k 必為偶數.
加入 k/2 個邊到圖形中, 將所有奇次數端點以配對方式連接起來, 在此結果下找
出圖中一Euler circuit, 然後再將所加入的邊去掉,結果共需 k/2 路徑
但是老師卻問我: how to pick up the k/2 paths without common edges
請問各位高手該如何解釋呢?
2. let G be a graph of order n. If d(G)大於等於(n-1)/2, show that G is
connected. 其中 d(G) is the minimum degree of a graph G, defined by
d(G)=min { deg(v): v belongs to V(G) }
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.230.37