第10章几种典型图 设G=〈V,E,w)〉是一带权图,l是G的一条回路,称 为l的双α国邮递员问题就是在带非负权的连通图中 ∈l 找到一条权最小的行遍所有边的回路,称此回路为最 佳周游 若G是欧拉图,则G中的任何一条欧拉回路均是最 佳周游,而寻找欧拉回路的 Fleury算法为解决这一问题 提供了切实可行的方法。对于非欧拉图,也有相应的 算法,限于篇幅不再介绍
第10章 几种典型图 设G=〈V,E,w〉是一带权图，l是G的一条回路，称 为l的权。中国邮递员问题就是在带非负权的连通图中 找到一条权最小的行遍所有边的回路，称此回路为最 佳周游。 若G是欧拉图，则G中的任何一条欧拉回路均是最 佳周游，而寻找欧拉回路的Fleury算法为解决这一问题 提供了切实可行的方法。对于非欧拉图，也有相应的 算法，限于篇幅不再介绍。 ( ) i i e l e
第10章几种典型图 2欧拉有向图 定义10.1.2设G是连通有向图,若G中有经过所有 边一次且仅一次的有向通路(起点、终点不重合), 则称为有向欧拉通路,具有有向欧拉通路的图称为半 欧拉有向图;若G中有经过所有边一次且仅一次的有向 回路,则称为有向欧拉回路,具有有向欧拉回路的图 称为欧拉有向图 显然,如果G是欧拉有向图,则G必是强连通图
第10章 几种典型图 2.欧拉有向图 定义10.1.2 设G是连通有向图，若G中有经过所有 边一次且仅一次的有向通路（起点、终点不重合）， 则称为有向欧拉通路，具有有向欧拉通路的图称为半 欧拉有向图；若G中有经过所有边一次且仅一次的有向 回路，则称为有向欧拉回路，具有有向欧拉回路的图 称为欧拉有向图。 显然，如果G是欧拉有向图，则G必是强连通图
第10章几种典型图 类似于定理10.1.1、10.1.2,可得下面定理: 定理10.1.3设G是连通有向图,则G是欧拉有向图 当且仅当G中的每个顶点ν均有d+(ν)=d-(ν) 定理10.14设G是连通有向图,则G是半欧拉有向 图当且仅当G中恰有两个奇度数顶点,其中一个入度比 出度大1,另一个出度比入度大1,而其他顶点的出度 等于入度。 例如,图10.1.3中(a)是欧拉有向图,图(b)是 半欧拉有向图,图(c)既非欧拉有向图也非半欧拉有 向图
第10章 几种典型图 类似于定理10.1.1、10.1.2，可得下面定理： 定理10.1.3 设G是连通有向图，则G是欧拉有向图 当且仅当G中的每个顶点v均有d+（v）=d-（v）。 定理10.1.4 设G是连通有向图，则G是半欧拉有向 图当且仅当G中恰有两个奇度数顶点，其中一个入度比 出度大1，另一个出度比入度大1，而其他顶点的出度 等于入度。 例如，图10.1.3中（a）是欧拉有向图，图（b）是 半欧拉有向图，图（c）既非欧拉有向图也非半欧拉有 向图
第10章几种典型图 (b) 图10.1.3
第10章 几种典型图 图 10.1.3 (a) (b) (c)
第10章几种典型图 【例10.1.2】计算机鼓轮设计问题 设计旋转鼓轮,要将鼓轮表面分成16个扇区,如 图10.14(a)所示,每块扇区用导体(阴影区)或绝 缘体(空白区)制成,如图10.14(b)所示,四个触 点a、b、c和a与扇区接触时,接触导体输出1,接触绝 缘体输岀0。鼓轮顺时针旋转,触点每转过一个扇区就 输出一个二进制信号。问鼓轮上的16个扇区应如何安 排导体或绝缘体,使得鼓轮旋转一周,触点输出一组 不同的二进制信号?
第10章 几种典型图 【例10.1.2】 计算机鼓轮设计问题: 设计旋转鼓轮，要将鼓轮表面分成16个扇区，如 图10.1.4（a）所示，每块扇区用导体（阴影区）或绝 缘体（空白区）制成，如图10.1.4（b）所示，四个触 点a、b、c和d与扇区接触时，接触导体输出1，接触绝 缘体输出0。鼓轮顺时针旋转，触点每转过一个扇区就 输出一个二进制信号。问鼓轮上的16个扇区应如何安 排导体或绝缘体，使得鼓轮旋转一周，触点输出一组 不同的二进制信号？