图论在计算机中的应用

作     者：黄万徽 

出 版 物：《高等函授学报（自然科学版）》 (Journal of Higher Correspondence Education(Natural Sciences))

年 卷 期：1994年第7卷第6期

页      码：7-10,12页

摘      要：图论在计算机科学中的应用很广泛。例如在开关理论与逻辑设计、数据结构、形式语言、操作系统、编译程序，信息组织与检索都有很重要的应用。本文补充《离散数学基础》（洪帆编）教材之不足，给出以下内容，供读者加深对有关知识的理解。一、印刷电路的分层问题为了设计印刷电路板，先将电路画成图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中用同一颜色的...

主 题 词：图论 计算机 应用 印刷电路 鼓轮设计 最优前缀码 最优树 

学科分类：07[理学] 08[工学] 070104[070104] 0701[理学-数学类] 081202[081202] 0812[工学-测绘类] 

馆 藏 号：203304850...