極大平面圖的結(jié)構(gòu)與著色理論(2)多米諾構(gòu)形與擴(kuò)縮運(yùn)算
doi: 10.11999/JEIT160224 cstr: 32379.14.JEIT160224
基金項(xiàng)目:
國(guó)家973規(guī)劃項(xiàng)目(2013CB329600)，國(guó)家自然科學(xué)基金(61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)
Theory on Structure and Coloring of Maximal Planar Graphs (2) Domino Configurations and Extending-Contracting Operations
Funds:
The National 973 Program of China (2013CB 329600), The National Natural Science Foundation of China (61372191, 61472012, 61472433, 61572046, 61502012, 61572492, 61572153, 61402437)
-
摘要: 業(yè)已證明四色猜想的數(shù)學(xué)證明可歸結(jié)為刻畫4-色漏斗型偽唯一4-色極大平面圖的特征。為刻畫此類極大平面圖的結(jié)構(gòu)特征，本文提出一種構(gòu)造極大平面圖的方法 擴(kuò)縮運(yùn)算。研究發(fā)現(xiàn)：此方法的關(guān)鍵問(wèn)題是需要清楚一種構(gòu)形，稱為多米諾構(gòu)形。文中構(gòu)造性地給出了多米諾構(gòu)形的充要條件；在此基礎(chǔ)上提出并建立了一個(gè)圖的祖先圖與子孫圖理論與構(gòu)造方法。特別證明了：任一最小度4的n(9)-階極大平面圖必含(n-2)-階或(n-3)-階祖先圖；給出極大平面圖的遞推構(gòu)造法，并用此方法構(gòu)造出6~12-階所有最小度的4極大平面圖。擴(kuò)縮運(yùn)算是本系列文章的基石。
-
關(guān)鍵詞:
- 極大平面圖 /
- 擴(kuò)縮運(yùn)算 /
- 多米諾構(gòu)形 /
- 祖先圖 /
- 子孫圖 /
- 遞推構(gòu)造法
Abstract: The first paper of this series of articles revealed that Four-Color Conjecture is hopefully proved mathematically by investigating a special class of graphs, called the 4-chromatic-funnel, pseudo uniquely-4- colorable maximal planar graphs. To characterize the properties of such class of graphs, a novel technique, extending-contracting operation, is proposed which can be used to construct maximal planar graphs. The essence of this technique is to study a special kind of configurations, domino configurations. In this paper, a necessary and sufficient condition for a planar graph to be a domino configuration is constructively given, on the basis of which it is proposed to construct the ancestor-graphs and descendent-graphs of a graph. Particularly, it is proved that every maximal planar graph with ordern(9) and minimum degree4 has an ancestor-graph of order(n-2) or (n-3). Moreover, an approach is put forward to construct maximal planar graphs recursively, by which all maximal planar graphs with order 6~12 and minimum degree 4 are constructed. The extending-contracting operation constitutes the foundation in this series of articles. -
APPEL K and HAKEN W. The solution of the four-color map problem[J]. Science American, 1977, 237(4): 108-121. doi: 10.1038/scientificamerican1077-108. APPEL K and HAKEN W. Every planar map is four colorable, I: Discharging[J]. Illinois Journal of Mathematics, 1977, 21(3): 429-490. APPEL K, HAKEN W, and KOCH J. Every planar map is four-colorable, II: Reducibility[J]. Illinois Journal of Mathematics, 1977, 21(3): 491-567. EBERHARD V. Zur Morphologie Der Polyeder, Mit Vielen Figuren Im Text[M]. Leipzig: Benedictus Gotthelf Teubner, 1891: 14-68. 王邵文. 構(gòu)造極大平面圖的圈加點(diǎn)法[J]. 北京機(jī)械工業(yè)學(xué)院學(xué)報(bào), 2000, 15(1): 26-29. WANG Shaowen. Method of cycle add-point to construct a maximum plate graph[J]. Journal of Beijing Institute of Machinery, 2000, 15(1): 26-29. 王邵文. 構(gòu)造極大平面圖的三種方法[J]. 北京機(jī)械工業(yè)學(xué)院學(xué)報(bào), 1999, 14(1): 16-22. WANG Shaowen. Three methods to construct maximum plain graph[J]. Journal of Beijing Institute of Machinery, 1999, 14(1): 16-22. BARNETTE D. On generating planar graphs[J]. Discrete Mathematics, 1974, 7(3-4): 199-208. doi: 10.1016/0012- 365X(74)90035-1. BUTLER J W. A generation procedure for the simple 3-polytopes with cyclically 5-connected graphs[J]. Journal of the Mechanical Behavior of Biomedical Materials, 1974, 26(2): 138-146. BATAGELJ V. An inductive definition of the class of all triangulations with no vertex of degree smaller than 5[C]. Proceedings of the Fourth Yugoslav Seminar on Graph Theory, Novi Sad, 1983: 15-24. WAGNER K. Bemerkungen zum vierfarbenproblem[J]. Jahresbericht der Deutschen Mathematiker-Vereinigung, 1936, 46: 26-32. BRINKMANN G and MCKAY B D. Construction of planar triangulations with minimum degree 5[J]. Discrete Mathematics, 2005, 301: 147-163. doi: 10.1016/j.disc.2005.06. 019. MCKAY B D. Isomorph-free exhaustive generation[J]. Journal of Algorithms, 1998, 26(2): 306-324. doi: 10.1006 /jagm.1997.0898. AVIS D. Generating rooted triangulations without repetitions[J]. Algorithmica, 1996, 16(6): 618-632. NAKANO S. Efficient generation of triconnected plane triangulations[J]. Computational Geometry, 2004, 27(2): 109-122. BRINKMANN G and MCKAY B. Fast generation of planar graphs[J]. MATCH Communications in Mathematical and in Computer Chemistry, 2007, 58(58): 323-357. NEGAMI S and NAKAMOTO A. Diagonal transformations of graphs on closed surfaces[J]. Science Reports of the Yokohama National University. Section I. Mathematics, Physics, Chemistry, 1994, 40(40): 71-96. KOMURO H. The diagonal flips of triangulations on the sphere[J]. Yokohama Mathematical Journal, 1997, 44(2): 115-122. MORI R, NAKAMOTO A, and OTA K. Diagonal flips in Hamiltonian triangulations on the sphere[J]. Graphs and Combinatorics, 2003, 19(3): 413-418. doi:?10.1007/s00373- 002-0508-6. GAO Z C, URRUTIA J, and WANG J Y. Diagonal flips in labeled planar triangulations[J]. Graphs and Combinatorics, 2004, 17(4): 647-656. doi: ?10.1007/s003730170006. BOSE P, JANSENS D, VAN RENSSEN A, et al. Making triangulations 4-connected using flips[C]. Proceedings of the 23rd Canadian Conference on Computational Geometry, Toronto, 2014, 47(2): 187-197 doi: 10.1016/j.comgeo.2012. 10.012. 許進(jìn). 極大平面圖的結(jié)構(gòu)與著色理論(1): 色多項(xiàng)式遞推公式與四色猜想[J]. 電子與信息學(xué)報(bào), 2016, 38(4): 763-779. doi: 10.11999/JEIT160072. XU Jin. Theory on the structure and coloring of maximal planar graphs(1): recursion formula of chromatic polynomial and four-color conjecture[J]. Journal of Electronics Information Technology, 2016, 38(4): 763-779. doi: 10.11999/ JEIT160072. BONDY J A and MURTY U S R. Graph Theory[M]. Springer, 2008: 5-46. XU Jin, LI Zepeng, and ZHU Enqiang. On purely tree- colorable planar graphs[J]. Information Processing Letters, 2016, 116(8): 532-536. doi: 10.1016/j.ipl.2016.03.011. -
計(jì)量
- 文章訪問(wèn)數(shù): 1939
- HTML全文瀏覽量: 154
- PDF下載量: 875
- 被引次數(shù): 0
下載:
