离散数学的图_第7章.ppt

第7章 图 本章学习目标 在前面章节中介绍过二元关系的图形表示，即关系图。在关系图中，我们主要关心研究对象之间是否有连线（图论中称为边），这样的图正是图论的主要研究对象。图论中还根据实际需要，将此类图进行了推广，并且把它当作一个抽象的数学系统来进行研究。通过本章学习，读者应该掌握以下内容： 本章学习目标 （1）无向图、有向图的定义，图的基本术语 （2）子图、生成子图的概念 （3）补图、图的同构的概念 （4）通路、简单通路、初级通路的概念及相关定理 （5）回路、简单回路、初级回路的概念及相关定理 （6）无向连通图及有向连通图的有关概念 （7）图的矩阵表示 （8）带权图及其应用：最短路径问题和关键路径问题 主要内容 7.1 图的基本概念 7.2 通路与回路 7.3 图的连通性 7.4 图的矩阵表示 7.5 图的应用 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.1 图的基本概念 7.2 通路与回路 7.2 通路与回路 7.2 通路与回路 7.2 通路与回路 7.2 通路与回路 7.2 通路与回路 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.3 图的连通性 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.4 图的矩阵表示 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 7.5 图的应用 本章小结 7.4.2 图的关联矩阵 定义7.4.3 设 是一个无环有向图，其中 ， ， 令 称 为D的关联矩阵，记作 。 7.4.2 图的关联矩阵 例如，图7.4-3所示有向图的关联矩阵为： M（D）= 有向图M(D)的关联矩阵有如下性质： 7.4.2 图的关联矩阵 例如，图7.4-3所示有向图的关联矩阵为： M（D）= 有向图M(D)的关联矩阵有如下性质： 7.4.2 图的关联矩阵 （1） ，从而 ，这说明M(D)中所有元素之和为0； （2）M(D)中-1的个数与1的个数相等，都等于边数m； （3）第i行中1的个数等于 ，-1的个数等于 ，而第i行元素绝对值之和等于 ； （4）平行边所对应的列相同。 7.4.2 图的关联矩阵