[問題][數學]graph theory

[問題][數學]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.    

咩咩
初學者
初學者
 
文章: 1
註冊時間: 2005-09-20

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"?

chanjunhong
實習生
實習生
 
文章: 93
註冊時間: 2005-07-25

訪客 於 星期一 十月 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.

訪客

 

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

chanjunhong
實習生
實習生
 
文章: 93
註冊時間: 2005-07-25






大學以上數學問題