[2017年整理]《离散数学》第6章 图的基本概念.pptVIP

一、通路，回路。 1、通路 (回路) 中顶点和边的交替序列 —— ，其中 (无向图)， 或 (有向图)， ——始点， ——终点，称 为 到 的通路。当 时， 为回路。 2、简单通路，简单回路。 简单通路 (迹) 简单回路 (闭迹) 复杂通路 (回路) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3、初级通路，初级回路。 初级通路 (路径) 初级回路 (圈) 初级通路 (回路) 简单通路 (回路)， 但反之不真。 4、通路，回路 的长度—— 中边的数目。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例1、(1) 图(1)中，从 的通路有： 到 ………… 长度3 长度6 长度6 初级通路 简单通路 复杂通路 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. (2) ………… 长度3 长度4 长度7 图(2)中过 )有： 的回路 (从 到 初级回路(圈) 初级回路(圈) 复杂回路 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 5、图中最短的回路。 如图： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 6、性质。 定理3： 阶图中，若从顶点 到 存在 通路 ，则从 到 存在长度小于等于 在一个 的通路。 推论： 阶图中，若从顶点 到 存在 通路 ，则从 到 存在长度小于等于 在一个 的初级通路。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 定理4： 阶图中，若 到自身存在回路， 则从 到自身存在长度小于等于 的回路。 在一个 推论： 阶图中，若 到自身存在一个 简单回路，则从 到自身存在长度小于等于 的初级回路。 在一个 由以上定理可知，在 阶图中， 任何一条初级通路的长度 任何一条初级回路的长度 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 二、图的连通性。 1、连通，可达。 无向图中，从 到 存在通路，称 到 是 连通的(双向)。 有向图中，从 到 存在通路，称 可达 (注意方向) 。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2、短程线，距离。 短程线——连通或可达的两点间长度最短的 通路。 距离——短程线的长度， 记 无向图 有向图 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 若 之间无通路(或不可达)，规定 距离 满足： (1) ， 时，等号成立。 (2) 若是无向图，还具有对称性， 。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 3、无向图的连通。 为连通图—— 是平凡图，或 都是连通的。 中任两点 为非连通图—— 中至少有两点不连通。 Evaluation only