离散数学17.ppt

现在学****第七个知识点: 1、图的基本概念 2、通路、回路和连通性 3、图的矩阵表示 4、欧拉图和哈密顿图 5、偶图与匹配 6、平面图 7、树 1、图的基本概念 2、通路、回路和连通性 3、图的矩阵表示 4、欧拉图和哈密顿图 5、偶图与匹配 6、平面图 7、树一、无向树 1、无向树的定义定义 不含简单回路的连通无向图称为树,树中度数为 1 的顶点称为树叶,其它顶点称为分支点。每个连通分支都是树的无向图称为森林。 树树也是一种特殊的图。 2、树的等价命题 ,定理 3、无向树的性质定理 设树,则 T 中至少有两片树叶。请自学 P255 的证明。 2,,??VEVT二、生成树 1、生成树的定义定义 设无向图 G 的生成子图 T 是树,则称 T 是 G 的生成树或支撑树。生成树 T 中的边称为树枝, G 中不在生成树 T 中的边称为 T 的弦。?例题讲解?例题讲解下图中(b) 和(c) 均是(a) 生成树。 2、连通图与生成树的关系定理 一个连通图 G 中至少存在一棵生成树。定理 无向图 G 具有生成树当且仅当 G是连通的。