Anonymous 寫到:sorry~~~~一時筆誤,應該是指 cycle graph of odd order.
cycle graph means a graph G is a closed walk with no vertex repeated (except 1 st and the last one )
有沒人有會證明 以下有關圖論的敘述
A graph G is a bipartite graph if and only if G has no subgraph that is isomorphic with any cycle graph of odd order.
其實想法很簡單,
分成(1)二分圖(Bigraph)中不包含奇數的迴圈(cycle)
(2)給定一個圖,圖中沒有奇數的迴圈,必定可以分割成不相交的兩群。
(1):利用反證法,假設在二分圖中,存在一個奇數的迴圈
再不失去一般性,假定:
假如 i is odd
假如 j is even
但是,
不符合二分圖邊的定義。所以假設錯誤,在二分圖中不存在奇數的迴圈。
你介意第二部分,我將書的證明掃瞄給你嗎?想法是很簡單,(我的想法)
奇數一堆,偶數一堆的概念,但是面臨抽象化問題,不好說明控制(寫成證明的型式)。
從圖中任意一點A出發,將A隸屬於集合1,與A相鄰的頂點,隸屬於集合2,
再將與集合2中的頂點,相鄰的頂點隸屬於集合1,考慮在這個步驟中,
是否會有迴圈的產生?(不會)因為圖中無奇數的迴圈,如果在這個步驟中產生迴圈,
必定有奇數的迴圈產生。重複步驟,直到所頂點分配完畢。