發表回覆

主題 通關密語 訪客發文, 請參考 這裡 輸入通關密語.

顯示表情符號

站內上傳圖檔     Upload.cc免費圖片上傳

數學塗鴉工具     常用數學符號表    

用Latex打數學方程式

 


 

+ / -檢視主題

發表 chanjunhong 於 星期二 十月 04, 2005 7:39 am

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,考慮在這個步驟中,
是否會有迴圈的產生?(不會)因為圖中無奇數的迴圈,如果在這個步驟中產生迴圈,
必定有奇數的迴圈產生。重複步驟,直到所頂點分配完畢。

發表 訪客 於 星期一 十月 03, 2005 11:41 am

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.

Re: [問題][數學]graph theory

發表 chanjunhong 於 星期五 九月 30, 2005 2:59 pm

咩咩 寫到:有沒人有會證明 以下有關圖論的敘述

A graph  G is a bipartite graph if and only if G has no subgraph that is isomorphic with any cycle graph order.    


could you explain "cycle graph order"?

[問題][數學]graph theory

發表 咩咩 於 星期四 九月 29, 2005 9:42 am

有沒人有會證明 以下有關圖論的敘述

A graph  G is a bipartite graph if and only if G has no subgraph that is isomorphic with any cycle graph order.