標題: 圖的圈覆蓋
Cycle Cover of Graphs
作者: 連敏筠
傅恆霖
Hung-Lin Fu
應用數學系所
關鍵字: 圈覆蓋;cycle cover
公開日期: 2007
摘要: ㄧ個圖G的圈覆蓋(cycle cover)是收集一些G裡面的圈(cycle),使得G裡面的邊都被覆蓋住(cover)。ㄧ個整數流(integer flow)是在圖上賦予方向,且給定一個整數函數phi對應到G上所有的邊,使得對所有G裡的點v都滿足由v流出的量等於流入的量。 當所有的phi(e),都滿足-k<phi(e)<k,則phi稱為一個k-整數流(k-flow),如果對所有G上的邊,給的值都不為零, 則phi稱為處處不為零的k-整數流(nowhere-zero k-flow)。在這篇論文中,我們證明:如果Tutte的3-整數流猜測(Tutte's 3-flow conjecture)是對的,則當k是奇數時,對所有的(k-1)-邊連通圖滿足最小度數為k,會有一個處處不為零的6-整數流(6-flow) phi,使得那些給定奇數值的邊數會大於等於(k-1)/k的總邊數,這會推得圖G有一個圈覆蓋最多只需要(13k+5)/(9k)的總邊數。 當k是偶數時,對所有的(k-1)-邊連通圖滿足最小度數為k,會有一個處處不為零的6-整數流(6-flow) phi,使得那些給定奇數值的邊數會大於等於(k-2)/(k-1)的總邊數,這會推得圖G有一個圈覆蓋最多只需要(13k-8)/(9(k-1))的總邊數。
A cycle cover of a graph G is a collection of cycles of G which covers all edges of G. The size of a cycle cover is the sum of the lengths of the cycles in the cover. A flow in G under orientation D is an integer-valued function on E(G) such that the output value is equal to the input value for each v in V(G). The support of ph(i) is defined by S(ph(i)) = {e in E(G) : phi(e) not equalto 0}. For a positive integer k, if −k < (e) < k for every e in E(G), then is called a k-flow, and furthermore, if S(phi) = E(G), then is called a nowhere-zero k-flow. In this thesis we prove: (1) if Tutte’s 3-Flow Conjecture is true, then every (k − 1)-edge-connected graph G with ?minimum degree = k has a nowhere-zero 6-flow such that when k is odd |Eodd(phi)| not less than (k-1)\k |E(G)| and when k is even |Eodd(phi)| not less than (k-2)\(k-1) |E(G)| ; (2) If a (k−1)-edge-connected graph G with minimum degree = k has a nowhere-zero 6-flow such that when k is odd |Eodd(phi)| not less than (k-1)\k |E(G)|, then G has a cycle cover in which the size of the cycle cover is at most (13k+5)\9k |E(G)| and when k is even |Eodd(phi)| not less than (k-2)\(k-1) |E(G)|, then G has a cycle cover in which the size of the cycle cover is at most (13k−8)\9(k−1) |E(G)|, where Eodd(phi)={e in E(G) : phi(e) is odd }.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009422539
http://hdl.handle.net/11536/81317
顯示於類別:畢業論文


文件中的檔案:

  1. 253901.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。