推 mqazz1 :謝謝 10/30 21:55
※ 引述《mqazz1 (無法顯示)》之銘言：
: 標題: [圖論] connected graph
: 時間: Sat Oct 29 21:57:21 2011
:
: 1. G is a connected graph iff it consists of one single connected component
:
: 這題除了寫trivial 還有甚麼證法呢?
=>:
Suppose on the contrary that G contains two connected components, G_1, G_2.
Let v_1 and v_2 be vertices in G_1 and G_2 respectively.
Since G_1 and G_2 are connected componens of G, v_1 is not connected to v_2
and hence G is not connected, a contradiction.
<=:
For any two vertices v_1,v_2 in G, v_1 and v_2 are both in the
unique connected component of G and hence v_1 is connected to v_2.
Thus G is a connected graph.
:
: =====================
:
: 2. connected graph with |V|>1 contains either a vertex of degree 1 or a cycle
:
: 請問這題要怎麼證呢?
Let v_1->v_2->...->v_n be a maximal path P in G.
Consider the degree deg(v_1) of v_1.
If deg(v_1)>1, then v_1 is connected to some v_i, 3 小於等於 i 小於等於 n
by the maximality of the path P.
Hence v_1->v_2->...->v_{i-1}-> v_i->v_1 is a cycle. This shows the assertion.
:
:
:
: 謝謝
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 61.228.27.89
: → suhorng :第二題是什麼意思 ? 那樹呢 ? 10/29 22:03
: → suhorng :喔沒事....不要理我 10/29 22:04
: 推 GaussQQ :第一題還可以寫 Very Trivial 10/29 23:08
: → mqazz1 :要是第一題寫trivial 不知道老師會給幾分.. 10/29 23:15
零分吧，我想。 XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.70.177.37
※ 編輯: Eeon 來自: 219.70.177.37 (10/30 01:12)