1.
0---0 (這是圖)
為什麼他是biconnect
因為他不能切嗎?
2.
為什麼Kn* is called a tournament
可以舉個例子嗎(他哪裡像競賽)
3.
let Kn* be a directed graph with n nodes.
A directed graph(V,E) is transive if "(a,b) 屬於 E" ^ "(b,c) 屬於 E"
implies "(a,c) 屬於 E"
There are __N!__ transitive tournaments on n players.
3-1. 為什麼一個tournament具transitive <=> 他具唯一Hamilton Path
以上3個問題
謝謝
6 則留言:
因為Kn*為directed complete graph 有方向就可表示競賽狀況 例如有四個隊在比賽 比賽前為K4 比賽後就為K4*
3Q^^
1. biconnected的定義是不含cut point, 也就是至少要去掉2個點, 它才有可能不連通, 若將你所說的圖去掉1個點, 剩下的一個點自己會跟自己連通, 所以符合條件
3.我的想法是, 你先找一條Hamilton path出來, 假設途中經過...->a->b->c->..., 如果此時跳過b不走, 改走a->c, 想要走出另一條H.P., 則會發現不管你怎麼走都走不回b了, 因為若存在一個在b之後的點x可以走回b, 即存在x->b, 然而因為原先取的path是H.P.且G具transitive =>b可走到b之後的每個點 =>存在b->x, 則此時的G會不符合任兩點恰有一邊相連 =>G不為Kn* -><-
有吸收到..thanks 問題與詳解
第三個問題補一個從右邊到左邊, 我的想法是:
先找出那一條唯一的Hamilton Path P:v1,...,vn, 先討論v1與vn的點如何相連, 假如vn->v1存在, 則v1->...->vn->v1形成cycle導致H.P.不唯一, 所以存在v1->vn, 接著討論v2與vn相連的邊, 若存在vn->v2, 則會存在一條path: v1->vn->v2->...->vn-1導致H.P.不唯一, 所以存在v2->vn, 用以上的方式討論到最後會發現, 任意的a,b,c三個點, 若a->b, b->c, 則存在a->c =>G具transitive
恩恩 謝謝解答
都懂了^^
張貼留言