發(fā)布時(shí)間：2018-10-08 15:59

【摘要】：整數(shù)流和子圖覆蓋是當(dāng)今圖論領(lǐng)域的兩個(gè)重要研究方向,與著名的四色問題密切相關(guān).四色問題等價(jià)于平面圖的整數(shù)4-流問題.一個(gè)圖有整數(shù)k-流,當(dāng)且僅當(dāng)對(duì)該圖的某個(gè)定向,存在從邊集合到k階交換群的一個(gè)函數(shù),使得對(duì)圖中每個(gè)點(diǎn),進(jìn)入該點(diǎn)的邊函數(shù)值之和等于離開該點(diǎn)的邊函數(shù)值之和.整數(shù)流理論與數(shù)學(xué)其他領(lǐng)域一些著名問題有一定的關(guān)聯(lián),如組合學(xué)的孤獨(dú)跑步者、數(shù)論的丟番圖逼近、幾何學(xué)的視線阻礙和線性空間堆壘基等.四色問題還等價(jià)于平面圖的偶子圖覆蓋問題:是否存在3個(gè)偶子圖,覆蓋一個(gè)2-邊連通平面圖的每條邊恰好兩次.著名的Fulkerson猜想認(rèn)為,對(duì)每個(gè)2-邊連通圖(不必是平面圖),存在6個(gè)偶子圖,覆蓋該圖的每條邊恰好4次.本文對(duì)整數(shù)流和子圖覆蓋這兩個(gè)研究方向及相關(guān)問題的歷史和現(xiàn)狀作一個(gè)綜述.
[Abstract]:Integer flow and subgraph coverage are two important research directions in the field of graph theory and are closely related to the famous four-color problem. The four-color problem is equivalent to the integer 4-flow problem of planar graphs. A graph has an integer k-stream if and only if there is a function from the edge set to the k-order commutative group for some direction of the graph such that the sum of the values of the edge functions entering the point is equal to the sum of the values of the edge functions leaving the point. The theory of integer flow is related to some famous problems in other fields of mathematics, such as solitary runners in combinatorial theory, Diophantine approximation in number theory, visual obstruction in geometry, and stacking of bases in linear space, and so on. The four-color problem is also equivalent to the dual subgraph covering problem of a planar graph: whether there are three pairs of subgraphs covering each edge of a 2-edge-connected planar graph is exactly twice. The famous Fulkerson conjecture holds that for every 2-edge-connected graph (not necessarily a planar graph), there are six even subgraphs covering each edge of the graph exactly four times. In this paper, the history and present situation of integer flow and subgraph covering are reviewed.
【作者單位】： 福州大學(xué)離散數(shù)學(xué)研究中心;
【基金】：國家自然科學(xué)基金(批準(zhǔn)號(hào):11331003)資助項(xiàng)目
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 孫亮;葉淼林;;圖的子圖匹配數(shù)與圖的標(biāo)準(zhǔn)化拉普拉斯譜[J];安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2011年04期

2 陳賜平;;帶虧數(shù)的[1,n]-子圖[J];北京農(nóng)業(yè)工程大學(xué)學(xué)報(bào);1987年03期

3 李學(xué)良;;有向1-因子圖[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);1988年02期

4 李傳湘;層次結(jié)構(gòu)中封閉子圖的映射[J];數(shù)學(xué)物理學(xué)報(bào);1990年04期

5 郭思平;;立方圖中一類具有極大邊數(shù)子圖的性質(zhì)[J];云南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);1991年04期

6 謝力同,范紅兵;關(guān)于局部子圖可重構(gòu)性的一個(gè)新結(jié)果(英文)[J];數(shù)學(xué)進(jìn)展;1997年05期

7 龍和平,謝力同,顏謹(jǐn),劉桂真;邊型帶權(quán)核子圖的邊可重構(gòu)性[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2002年02期

8 李慰萱;;圖的結(jié)構(gòu)多項(xiàng)式與子圖恒等式[J];長沙鐵道學(xué)院學(xué)報(bào);1979年03期

9 郭知熠;關(guān)于完全k-邊可染子圖[J];華中工學(xué)院學(xué)報(bào);1985年06期

10 辛林，，徐恭勤;子圖個(gè)數(shù)的計(jì)算問題[J];教學(xué)與教材研究;1994年03期

相關(guān)會(huì)議論文 前4條

1 徐以凡;;層分解和子圖識(shí)別問題[A];2001年全國數(shù)學(xué)規(guī)劃及運(yùn)籌研討會(huì)論文集[C];2001年

2 陶劍文;丁佩芬;趙杰煜;;csgIndex:一種可擴(kuò)展的對(duì)比子圖索引模型[A];第二十七屆中國控制會(huì)議論文集[C];2008年

3 吳衛(wèi)江;李國和;;Apriori算法思想在頻繁子圖挖掘中應(yīng)用的研究[A];第六屆全國信息獲取與處理學(xué)術(shù)會(huì)議論文集（2）[C];2008年

4 吳穎華;周皓峰;袁晴晴;洪銘勝;汪衛(wèi);施伯樂;;Topology:一個(gè)快速的頻繁連通子圖的挖掘算法[A];第二十屆全國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（技術(shù)報(bào)告篇）[C];2003年

相關(guān)博士學(xué)位論文 前4條

1 藺厚元;禁用子圖與圖的哈密爾頓性[D];華中師范大學(xué);2012年

2 毛玲;基于層次因子圖的心電圖自動(dòng)診斷方法研究[D];國防科學(xué)技術(shù)大學(xué);2009年

3 崔慶;Tutte子圖方法及其應(yīng)用[D];南開大學(xué);2009年

4 吳云建;一致星因子圖與籠的連通性[D];南開大學(xué);2009年

相關(guān)碩士學(xué)位論文 前10條

1 范淦;高效的龐大圖的頻繁子圖挖掘方法研究[D];遼寧大學(xué);2015年

2 魏真真;大規(guī)模不確定圖緊密子圖挖掘算法研究[D];燕山大學(xué);2015年

3 齊寶雷;面向不確定圖數(shù)據(jù)的子圖模式挖掘算法的研究與實(shí)現(xiàn)[D];東北大學(xué);2013年

4 王會(huì)會(huì);精確子圖數(shù)據(jù)庫查詢技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2014年

5 白楊;復(fù)雜網(wǎng)絡(luò)圖中高密度子圖檢測方法與實(shí)現(xiàn)[D];西安電子科技大學(xué);2014年

6 王鵬;基于局部鄰域的最大密度子圖檢測方法研究與實(shí)現(xiàn)[D];西安電子科技大學(xué);2014年

7 趙路;圖的Q-特征值與圖結(jié)構(gòu)[D];青海師范大學(xué);2015年

8 王璐璐;不確定圖上Top-k子圖相似性查詢技術(shù)研究[D];東北大學(xué);2014年

9 張?zhí)烀?大圖上頻繁子圖挖掘算法的研究[D];東北大學(xué);2014年

10 王峰;基于眾核平臺(tái)子圖匹配算法研究[D];北京理工大學(xué);2016年

本文編號(hào)：2257368