2011-06-25

離 CH6

靠近最下面的地方G1G2是acycle
因為G是acycle，但是這個不是要證明的結果嗎
還沒證明怎麼可以拿來用?

 (1)的部分 |V| 不用 大於等於2嗎

為什麼不用證明 不具 degree 0 和 n 的情形呢
因為很明顯可以用鴿籠證明出來嗎

(2) 如果有三角形 (最小cycle長度是3)
那e > 2v -4 也不能保證是非平面圖嗎

6-1 從題目哪裡可以得知
任兩點至多一個邊相連?
於

2 則留言:

  1. 線代離散助教(wynne)2011年6月26日 凌晨2:05

    1. 這裡的"G是acyclic"是trivial, 是根據tree的定義而來的(connected, acyclic), 所以嚴格來講不是沒證而是證完了, 證完的話就可以拿來用, 這邊主要要證的只有|E|=|V|-1那個式子而已

    2. 如果說G具H.C., 這樣就已經imply了|V_1|和|V_2|一定都大於等於 2 了, 所以不用寫也沒關係

    3. 這題有勘誤過, 請至離散勘誤區看一下

    4. 是的, 反例可取 K_4

    5. 一般若題目沒有特別說明, G指的都是simple graph, 所以任兩點間至多只會有一個邊相連

    回覆刪除
  2. hahaha2011年6月26日 中午12:20

    感謝您~~

    回覆刪除