摘要：图论在计算机科学中的应用很广泛。例如在开关理论与逻辑设计、数据结构、形式语言、操作系统、编译程序，信息组织与检索都有很重要的应用。本文补充《离散数学基础》（洪帆编）教材之不足，给出以下内容，供读者加深对有关知识的理解。一、印刷电路的分层问题为了设计印刷电路板，先将电路画成图O如图1，G中边对应导线。顶点对应接点，设有导线连接的两个接点之间可能要装配元件。由于同一层印刷电路板上导线不允许相交（除接点之外），因此，如果G是平面图，则相应o就可以设计出一块草层印刷电路板；如果O不景平面图，则对应G必须设计一块多层印刷电路板，使每一层对应G的一个平面子图，对于图O如何设计具有层放最少的多层印刷电路板；作如图2所示的图G'。G'的顶点v1,v2,…，v9对应于图G中边顶点vi与vj之间有边相连当且仅当ei与ei在非接点处相交。例如达e2与边e3，e4，e6，e8相交于非接点处，对应于v2分别与有边相连。图G’的着色数为3，即可用3种颜色对图G'进行着色。图2中三种颜色用C1，C2，C3表示。如果顶点v1，vj与vj相邻，则vi与vj着不同颜色，对应于图G中边ei与ej相交时ei与ej着上不同的颜色，所以G中用同一颜色的...