【现货速发】线、页和图的着 图形图像 尹文生

本体论在数学上可以用图论来表示，即世界上万事万物都可以抽象为节点及其之间的联系。人类对图形的研究源远流长，其中几何学集大成于一体，然而图论却只有不到300年的历史。1738年，瑞士数学家莱昂哈德·欧拉(Leonhard Euler)解决了哥尼斯堡七桥问题，标志着图论的诞生。哥尼斯堡七桥问题是这样的，在哥尼斯堡有一条河称为普莱格尔河，在这条河上建有七座桥，将河中间的两个岛和河岸连接起来。有人提出：能不能每座桥都只走一遍，*后又回到原来的位置。这个问题看起来既简单又特别有趣，但是要得到一个明确、理想的答案却非常困难。问题传到欧拉那里，欧拉很快就用一种独特的方法给出了解答。这种方法就是，把两座小岛和河的两岸分别看作四个点，而把七座桥看作这四个点之间的连线，这样问题就简化成能不能用一笔画出这个图形的问题，当然问题就迎刃而解了。当人们将节点和节点之间的关系问题采用几何元素和几何图形来表示时，惊喜地发现很多问题都可以轻松地加以解决。几何图形不仅可以清楚地表达复杂关系的问题，还可以解决复杂关系的问题，在运筹学、计算机应用领域起着非常重要的作用。这是图论产生的原因，也是图论具有强大生命力的原因。在几何学中，点、线、圆是基本元素，用这些基本元素可以构建极其复杂的几何图形。同样，在图论中，点、线、圆（在图论中称为圈或回路）也是基本元素，用这些基本元素也可以构建极其复杂的几何图形。但是不同于几何，图论构建这些几何图形的目的并不是精确反映几何位置关系，而是反映节点之间的相互联系，利用图形来解决节点及其之间关系所表示的非几何问题。因为图论特别重视节点之间的相互关系而忽略节点及其连线的精确位置，所以图论中的基本元素和几何中的基本元素是不同的。此外，图论中还需要定义一些新的基本元素，其中*重要的是树和圈。树用于描述层次关系，而圈用于描述封闭关系。值得注意的是，图论中的点、线、圆不同于几何中的点、线、圆，它们具有拓扑意义，不注重精确位置，所以它们可以分别称为节点、连线、圈，它们的图示方法可以多种多样。当节点之间相互关系用图形表示时，很多问题就变得非常清晰、明确且便于求解。例如，哥尼斯堡七桥问题被欧拉在引入图的方法进行抽象表示后转化成一笔画问题，而英国数学家哈密顿将著名的“周游世界问题”转化成了图论中的寻找哈密顿回路问题。图论成为解决问题*重要的方法之一。当需要解决一个复杂关系的问题时，人们常常将其画在纸上，然后调整它的形状，再对该图形进行分析，*后获得问题的求解。一般来说，一个实际问题在图论中主要表现为一个连通块问题，而连通块问题又可以抽象为两类问题：一类是无圈问题，另一类是有圈问题。对于无圈问题，总可以用一棵树将其连接在一起，特殊情况下这棵树可以退化成一条线。树是图论的重要元素，是对层次化关系的描述，对解决各种实际问题具有重要意义。对于有圈问题，由于相互关联多，就不可能像无圈问题那么容易解决，所以在解决有圈问题时必须尽可能与树建立联系。然而遗憾的是，树具有排他性，即一个图如果用一棵生成树来表示，那么就不能再同时用另外一棵树来表示，这样在处理问题时就只能先构成一棵静态的生成树，然后在这棵静态树上进行操作。例如，国际互联网系统就是一个有圈问题。为了对国际互联网进行有效管理，需要构建一个静态的树状结构，这就是域名系统。这个域名系统可以较好地对国际互联网系统各个节点的组成关系进行管理，但是如果需要对其他关系进行管理时，该域名系统可能不一定合适，此时需要建立另外一套树状结构，但这可能会引发两套结构数据一致性的问题。同样，在产品管理中，产品的部件和零件构成了一棵产品组成树，但是产品的装配需要描述部件和零件的配合关系，它们是不能直接嵌入产品组成树中的。这是图论中简单的树，即同类节点组成的树所无法解决的问题，而必须用到广义的树，这种能包含不同类型节点的树，作者称之为广义环图树。事实上，现在各种计算机应用系统中均使用这种广义的树作为该系统的数据管理工具，并用树窗口的形式表现出来，而在复杂系统中不使用这种广义树的计算机系统几乎不存在。通过对图论中基本元素的观察，不难发现图论中对线的应用太简略，一般仅局限于连接两个节点的直线或曲线，虽然也定义过连线的概念，但那仅仅反映节点之间相连的关系；也存在将线水平放置的进度图，但在这种图中允许存在线的交叉；还有用书页来解决图论问题的，但是没有人提出页面树的结构，更没有发现线及页面树在着色方面的研究。所以，线的概念和应用比较欠缺。当我们将图中的节点依次连接并垂直放置时，就可以得到一条连线，简称线。如果假定这条线可以无限延长，那么就可以将平面分隔成两部分，即两个半平面。每部分都是由线和线上的跨弧组成，可以称为页。页包含线和半平面上的全部跨弧，其中线可以作为页的轴。如果是平面图，则在每页中跨弧都不相交，跨弧之间只有包含和并列两种关系，这样就可以用树来描述每页中的跨弧或者节点关系。如果是非平面图，则两个这样的页面无法避免跨弧的相交，所以需要增加新的页面，增加的页面也是以线为轴的半平面，这样所有以线为轴的页面共轴组合在一起形成一个类似仙人球的结构。如果图中所有的节点可以连成一条线或一条回路，则形成哈密顿路或回路，每页线上的节点正好是全部图中的节点。如果不能连成一条线或回路，那么将形成多条线，其中首先形成的线称为主线，围绕主线上的点构成的另外的线称为副线。全部主线和副线构成一个树状结构，它们包含图中全部的节点。如果将主线定义为册，副线定义为分册，则图的结构可以用一套书的结构来描述。实际上，线、页、册的概念在自然界和人类社会早就得到了广泛应用。例如，自然界中的一棵树，不仅有着图论中所描述的树状结构，还有页面树的结构，即树的分支实际上是围绕某个中心生长的。而花、果等表现得更加明显，它们都形成环状或球状结构。树也有分册的结构，即嵌套结构，内部还有相似的结构。例如，脐橙中大橙子里面还有小橙子等。人类社会也是如此，各门学科的知识管理就是典型的线、页、册的应用。线、页、册结构不仅有利于知识或数据的管理，更重要的是有利于问题的求解。例如，普通的树状结构仅仅描述了节点之间的层次关系，当用它处理有圈问题时只能表示一个孤立的静态结构。但是线、页、册结构不同，它可以全面描述节点之间的关系。其特点是采用线和页描述整个图的层次关系，而用每页中的页面树描述该页中的内部层次关系。当我们用线、页、册看待问题时，就可以得到很多启迪。例如，封建社会使用西周的宗法制或者蒙古的幼子守灶制进行权力的交接，因为这样可以形成长子继承结构，容易保证社会的稳定和管理。现代企业不仅保留了传统的职能直线制，同时还使用矩阵、事业部等形式进行组织管理，这是因为从多个页面来管理更利于企业的发展。而互联网系统使用域名系统也是将复杂的、相互平等的节点关系转变成清晰的层次化关系，使信息的交流更加流畅。使用线、页、册结构能够方便解决问题的关键是对图的整体和局部进行层次化。层次化可以包含三个层次：主册与分册划分、页面划分和页面树建立。其核心是构建线和页面树。当将图转化成线图时，页和册的结构就自动建立起来了，这样对实际问题的求解就转化成了页面树及页面树之间节点关系的求解问题。本书主要讨论平面图着色问题。首先将平面图转化成线图，使平面图的着色问题转化成两个页面树上对应节点之间的着色问题，即怎样对这两个页面树上的节点进行着色和调整，使整个线图只需四种颜色就完成着色。显然，当两个页面树都是长子继承结构时，整个线图呈现出非常简单的形态，这样无论节点数有多大，都可以轻易地完成着色，人工都可以胜任这项工作。当页面树不是长子继承时，层次结构变得比较复杂，页面之间节点的关系就更加复杂了。但是，由于每个页面都是按照树的形式组织的，所以比起原图来显然清晰得多。事实上，由于平面图着色问题*后转化成两个页面树上节点的对应问题，所以可以使用的解决方法就不止一种了。本书主要介绍了两种方法。一种方法是原色调整方法，即先为一页着色，称为原色着色，然后再解决另一页上发生的颜色冲突。因为对于任何一页，只要三种颜色即可完成页的着色，而当另一页发生颜色冲突时将发生冲突的节点用第四种颜色更换即可。如果又发生颜色冲突，并且与前面已使用第四种颜色的节点也发生冲突，则对第三页上的部分节点进行原色调整。另一种方法是可用色方法，即计算每个未着色节点可以使用的颜色，选取其中的一种颜色进行着色。它的关键是，选中的颜色不仅应该保证当前着色过程不会出现无解情况，而且应该保证在后续的着色过程中即使出现无解情况也不会回溯到当前着色过程，即着色过程总是可以向前推进并完成的。除了这两种方法，还可以使用扩展包容体方法等。限于篇幅，本书就不介绍了。对平面图所使用的着色方法可以推广到非平面图中。为此需要在册的结构中增加两页，即第*页和第二页，第*页仅记录全部节点，第二页则添加全部节点连接的线。这样页数就和图的色数建立了一种对应关系，可以根据极大平面线图的色数关系推测得到非平面图的色数关系，即极大线图的色数等于该线图的页数。关于图的线图化和着色方法等也可以应用于其他图论问题的求解。例如，可以实现图论教科书中的大部分算法，还可以应用于哈密顿圈、旅行商等问题的求解。本书获得国家自然科学基金项目“基于工程联接知识的装配序列规划”(51175200)资助。谨以此书献给我的家人，特别是我的父母。他们一直给予我鼓励，鼓励我积极探索，不怕困难。限于作者的学识水平，对图论的本质认识比较肤浅，书中疏漏及不当之处在所难免，望广大读者批评指正。

本书是对图论及平面图着色方面的研究。提出了线的概念，在线的基础上提出了页的概念，然后利用线和页所构成的线图对平面图的着色问题特别是四色着色问题进行研究。全书共包括十三章。第*章简要介绍图的基本概念。第二章提出了线的定义。第三章介绍了几种常用图的线表示。第四章讨论了图的平面映射和嵌入。第五章介绍了线图的基本构建方法，主要介绍了极大平面线图的构建方法。第六章分析了线图的特征。第七章提出了页和册的概念。第八章讨论线图的人工着色。第九章描述了极大平面线图的总体着色过程。第十章介绍了极大平面线图的着色结构特征，主要介绍涉及着色的一些术语和结构。第十一章至第十三章均介绍了极大平面线图的着色方法，其中第十一章介绍了直接着色方法，给出了六色定理的证明，而第十二章讨论了原色调整方法，第十三章讨论了可用色着色方法，给出了四色定理的两种不同的证明。

1998年在华中理工大学机械科学与工程学院获工学博士学位1988年在上海交通大学船舶动力工程系获工学硕士学位1985年在上海交通大学船舶动力工程系获工学学士学位开发了华中科技大学CAD中心暨天喻软件公司三维设计系统InteSolid中装配模型系统。开发了面向问题分析与决策专家系统软件系统及在公路工程和水运工程的2个应用系统。

第1章图(1)

1.1图的基本概念(1)

1.2图的图形(2)

1.3图的一些基本术语(6)

1.4树(8)

1.5平面图(11)

1.6哈密顿图(13)

1.7本章小结(14)

第2章线(15)

2.1线的定义(15)

2.2实线和虚线(18)

2.3本章小结(19)

第3章几种常用图的线表示(20)

3.1线图的构成(20)

3.2完全图的线表示(20)

3.3哈密顿图的线表示(22)

3.4本章小结(25)

第4章图的平面映射和嵌入(26)

4.1图的平面嵌入方法(26)

4.2单圈的平面性(27)

4.3面块点(29)

4.4两个圈之间的关系(30)

4.5平面图的判断(31)

4.6本章小结(33)

第5章线图构建方法(34)

5.1线图的构建(34)

5.2平面图的线表示(35)

5.3极大平面图的线表示(37)

5.4本章小结(40)

第6章线图的特征(41)

6.1线图的形成(41)

6.2单线图和复合线图(44)

6.3附着点(44)

6.4TL算法的问题和修正(45)

6.5包容性(57)

6.6相似性(58)

6.7隔离性(59)

6.8平面性(59)

6.9中心性(60)

6.10完整性(61)

6.11线图的语义(62)

6.12本章小结(62)

第7章页和册(63)

7.1页和册的定义(63)

7.2极大平面线图和极大页面线图(64)

7.3线图的册表示(64)

7.4页和第二页(65)

7.5极大平面线图中的跨弧(66)

7.6图的分页(66)

7.7页面树(71)

7.8主册和分册(72)

7.9本章小结(73)

第8章典型平面图的人工着色(75)

8.1着色对象的选择(75)

8.2正多面体及人工着色(76)

8.3经典算例(81)

8.4逐页着色(82)

8.5Heawood反例图的人工着色(86)

8.6人工着色分析(108)

8.7本章小结(109)

第9章极大平面线图的着色(110)

9.1着色流程(110)

9.2页和第二页的着色(111)

9.3第三页的着色过程(112)

9.4第四页的着色过程(113)

9.5着色三角形(116)

9.6分册的着色过程(121)

9.7极大平面图和平面图的色数(122)

9.8本章小结(123)

第10章极大平面线图的着色结构及其特征(124)

10.1着色基本术语(124)

10.2主要节点类型(127)

10.3着色特性(130)

10.4着色结构(134)

10.5包容体(138)

10.6本章小结(141)

第11章直接着色方法(142)

11.1基本方法(142)

11.2原色冲突的产生及特征(143)

11.3第四页的原色冲突(144)

11.4第三页的新增色(148)

11.5第三页对第四页的反作用(152)

11.6本章小结(158)

第12章原色调整着色方法(160)

12.1原色调整的基本方法(160)

12.2原色冲突节点和第三页结构关系(168)

12.3整体原色调整的特征(170)

12.4原色冲突跨弧三角形的原色调整(175)

12.5一般原色冲突跨弧的原色调整(180)

12.6四面体和类四面体法则(186)

12.7局部原色调整(190)

12.8包容体的分割(198)

12.9新增色点的作用(203)

12.10包容体的调色(219)

12.11着色算法(227)

12.12原色调整着色定理(230)

12.13本章小结(231)

第13章可用色着色方法(232)

13.1可用色和相邻色(232)

13.2无解的判断和基本消除方法(235)

13.3解和无解的形成(240)

13.4单个无解三角形的消除(249)

13.5无解三角形的相连(255)

13.6相连无解三角形的消除(261)

13.7当前着色点的位置影响(265)

13.8无解三角形消除定理(267)

13.9回溯爆炸的原因(268)

13.10可用色着色算法(268)

13.11可用色着色定理(271)

13.12本章小结(271)

参考文献(273) 

本书是对图论及平面图着色方面的研究。提出了线的概念，在线的基础上提出了页的概念，然后利用线和页所构成的线图对平面图的着色问题特别是四色着色问题进行研究。全书共包括十三章。第*章简要介绍图的基本概念。第二章提出了线的定义。第三章介绍了几种常用图的线表示。第四章讨论了图的平面映射和嵌入。第五章介绍了线图的基本构建方法，主要介绍了极大平面线图的构建方法。第六章分析了线图的特征。第七章提出了页和册的概念。第八章讨论线图的人工着色。第九章描述了极大平面线图的总体着色过程。第十章介绍了极大平面线图的着色结构特征，主要介绍涉及着色的一些术语和结构。第十一章至第十三章均介绍了极大平面线图的着色方法，其中第十一章介绍了直接着色方法，给出了六色定理的证明，而第十二章讨论了原色调整方法，第十三章讨论了可用色着色方法，给出了四色定理的两种不同的证明。

1998年在华中理工大学机械科学与工程学院获工学博士学位1988年在上海交通大学船舶动力工程系获工学硕士学位1985年在上海交通大学船舶动力工程系获工学学士学位开发了华中科技大学CAD中心暨天喻软件公司三维设计系统InteSolid中装配模型系统。开发了面向问题分析与决策专家系统软件系统及在公路工程和水运工程的2个应用系统。