的G的子图,记作G【E’】.或简称G〔E’】是G的边导出子图。
1.6 图的同构 设有两个图G1和G:,如果它们的顶点间有一一对应关系,并且在对应的两个顶点连接的边也一一对应时,称G1和G2同构(Isomorphism),记作Gl兰G2.如图1.4所示。
大连理工大学硕士学位论文 (1)G (2)subgraph of G (3)spanning subgraph of G 图1.3子图与生成子图 Fig.1.3 Subgraph and spanning subgraph 从图G=(矿,E)中删除顶点集S是指图G的y—S导出子图,即从矿中删除所有S中所有顶点和所有与S中顶点相关联的边而得到的子图,记作G—S. .厂 § f一一—一 (1)Gx L‖ (2)G2 图1。
4 G1和其同构图G2 Fig.1.4 Graph G1 and its isomorphism graph G21.7弦图、矿太阳图 设C是图G上的圈,l C|>4,如果C本身又是G的导出子图,则称C是G的无弦圈,特别称长度为m的无弦圈为纯m边形,如果G上不存在无弦圈,则称G是弦图。
设图G=(y,E),V={xl,X2,…,以;I,E,…K},玎≥3其中G【x1,X2….,以〕兰C”,仁,E….,艺)是独立集,且E(G)=亿Xt,Z置+,I i=1,2,...,挖),(注:下标对刀取模),则称图G为n.太阳图。
若干图的等全着色及彩虹支配问题的研究 2 图的等全着色和彩虹支配问题进展 2.1 图的等全着色问题及进展 2.1.1 着色的起源及发展 图的着色问题源于一个图论历史中的一个著名问题——四色猜想即四色问题。
是世 界近代三大数学难题之一。
四色问题的内容是:“任何一张地图只用四种颜色就能使具有共同边界的国家着上 不同的颜色。
”用数学语言表示,即“将平面任意地细分为不相重迭的区域,每一个区域 总可以用1,2,3,4这四个数字之一来标记,而不会使相邻的两个区域得到相同的数字。
” 这里所指的相邻区域,是指有一整段边界是公共的。
如果两个区域只相遇于一点或有限多点,就不叫相邻的,因为用相同的颜色给它们着色不会引起混淆。
四色猜想的提出来自英国。
1852年,毕业于伦敦大学的弗南西斯·格思里来到一家科研单位搞地图着色工作时,发现了一种有趣的现象:“每幅地图都可以用四种颜色着色,使得有共同边界的国家都被着上不同的颜色。
”这个现象能不能从数学上加以严格证明呢?他和在大学读书的弟弟格里斯决心试一试。
兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠,可是研究工作没有进展。
1852年10月23日,他的弟弟就这个问题的证明请教了他的老师、著名数学家德·摩尔根,摩尔根也没有能找到解决这个问题的途径,于是写信向自己的好友、著名数学家汉密尔顿爵士请教。
汉密尔顿接到摩尔根的信后,对四色问题进行论证。
但直到1865年汉密尔顿逝世为止,问题也没有能够解决。
1872年,英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题,于是四色猜想成了世界数学界关注的问题。
世界上许多一流的数学家都纷纷参加了四色猜想的大会战。
1878”--”1880年两年间,著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文,宣布证明了四色定理,大家都认为四色猜想从此也就解决了。
肯普【5】的证明是这样的:首先指出如果没有一个国家包围其他国家,或没有三个以上的国家相遇于一点,这种地图就说是“正规的”。
如为正规地图,否则为非正规地图。
一张地图往往是由正规地图和非正规地图联系在一起,但非正规地图所需颜色种数一般不超过正规地图所需的颜色,如果有一张需要五种颜色的地图,那就是指它的正规地图是五色的,要证明四色猜想成立,只要证明不存在一张正规五色地图就足够了。
肯普是用归谬法来证明的,大意是如果有一张正规的五色地图,就会存在一张国数最少的“极小正规五色地图”,如果极小正规五色地图中有一个国家的邻国数少于六个, 大连理工大学硕士学位论文 就会存在一张国数较少的正规地图仍为五色的,这样一来就不会有极小五色地图的国 数,也就不存在正规五色地图了。
这样肯普就认为他已经证明了“四色问题”,但是后来 人们发现他错了。
不过肯普的证明阐明了两个重要的概念,对以后问题的解决提供了途径。
第一个概 念是“构形”。
他证明了在每一张正规地图中至少有一国具有两个、三个、四个或五个邻 国,不存在每个国家都有六个或更多个邻国的正规地图,也就是说,由两个邻国,三个 邻国、四个或五个邻国组成的一组“构形”是不可避免的,每张地图至少含有这四种构形 中的一个。
肯普提出的另一个概念是“可约”性。
“可约”这个词的使用是来自肯普的论证。
他证 明了只要五色地图中有一国具有四个邻国,就会有国数减少的五色地图。
自从引入“构 形”,“可约”概念后,逐步发展了检查构形以决定是否可约的一些标准方法,能够寻求 可约构形的不可避免组,是证明“四色问题”的重要依据。
但要证明大的构形可约,需要 检查大量的细节,这是相当复杂的。
11年后,即1890年,在牛津大学就读的年仅29岁的赫伍德161以自己的精确计算指 出了肯普在证明上的漏洞。
他指出肯普说没有极小五色地图能有一国具有五个邻国的理 由有破绽。
不久,泰勒的证明也被人们否定了。
人们发现他们实际上证明了一个较弱的命题——五色定理。
就是说对地图着色,用五种颜色就够了。
后来,越来越多的数学家虽然对此绞尽脑汁,但一无所获。
于是,人们开始认识到,这个貌似容易的题目,其实是一个可与费马猜想相媲美的难题。
进入20世纪以来,科学家们对四色猜想的证明基本上是按照肯普的想法在进行。
1913年,美国著名数学家、哈佛大学的伯克霍夫利用肯普的想法,结合自己新的设想;证明了某些大的构形可约。
后来美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。
1950年,有人从22国推进到35国。
1960年,有人又证明了39国以下的地图可以只用阴种颜色着色;随后又推进到了50国。
看来这种推进仍然十分缓慢。
高速数字计算机的发明,促使更多数学家对“四色问题”的研究。
从1936年就开始研究四色猜想的海克,公开宣称四色猜想可用寻找可约图形的不可避免组来证明。
他的学生丢雷写了一个计算程序,海克不仅能用这程序产生的数据来证明构形可约,而且描绘可约构形的方法是从改造地图成为数学上称为“对偶”形着手。
他把每个国家的首都标出来,然后把相邻国家的首都用一条越过边界的铁路连接起来,除首都(称为顶点)及铁路(称为弧或边)外,擦掉其他所有的线,剩下的称为原图的对偶图。
到了六十年代后期,海克引进一个类似于在电网络中移动电荷的方法来求构形的不可避免组。
在海克的研究 若干图的等全着色及彩虹支配问题的研究 中第一次以颇不成熟的形式出现的“放电法”,这对以后关于不可避免组的研究是个关 键,也是证明四色定理的中心要素。
电子计算机问世以后,由于演算速度迅速提高,加之人机对话的出现,大大加快了 对四色猜想证明的进程。
美国伊利诺大学哈肯在1970年着手改进“放电过程”,后与阿 佩尔合作编制一个很好的程序。
就在1976年6月,他们在美国伊利诺斯大学的两台不 同的电子计算机上,用了1200个小时,作了100亿判断,终于完成了四色定理的证明, 轰动了世界【71。
这是一百多年来吸引许多数学家与数学爱好者的大事,当两位数学家将他们的研究 成果发表的时候,当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳,以庆祝这一难题
上一篇:
数控车床全闭环控制系统的研究
下一篇:
商业银行发展绿色信贷业务的对策探讨