7图的基本概念.pptVIP

qunliu, northeastern Univ. 图论绪 图论绪 7.1 无向图及有向图 图论中的一些概念 7.2通路、回路、图的连通性 7.3 图的矩阵表示 7.3图的矩阵表示 7.3图的矩阵表示 7.3图的矩阵表示 * Graphs/图论 * 图形可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。 一个图是由一些结点和连接两个结点之间的连线（即边）所组成的，与连线的长度及结点的位置无关 此两图是相同的，因为点与边的对应关系相同 边 顶点 Ｖ中的元素称为顶点，用带标记的点表示，也称为结点。 定理7-1.2 在任何图中度数为奇数的结点必定是偶数个。 定理7-1.3 在任何有向图中，所有结点的入度之和等于 所有结点的出度之和，且等于边数。 例 证明：在任意六个人的集会上，要么有三人似曾相识， 要么有三人不曾相识。 两图同构的必要条件（非充分） 1、结点数相同 2、边数相同 3、度数相同的结点数相同 通路 Ｇ中相邻边的序列（Ｖ0，Ｖ1），（Ｖ1，Ｖ2），…（Ｖk-1，Ｖk）称为一条通路。此通路的长度为ｋ。也可以用（Ｖ0，Ｖ1，…，Ｖk）表示通路，Ｖ0为起点，Ｖk为终点。 当Ｖ0=Ｖk时，该通路称为回路。 简单通路 一条通路中没有两条边是相同的，称此通路为简单通路（迹）。当其是回路时，称为简单回路。 初级通路 一条通路中，除了起点和终点可以相同，没有其他相同顶点出现，称此通路为初级通路（基本通路或路径）。当其是回路时，称为初级回路（基本回路或圈）。 7.2通路、回路、图的连通性 （ｅ5，ｅ1 ，ｅ2 ，ｅ3，ｅ4）是简单通路，不是初级通路，因为（ｃ，ａ，ｂ，ｃ，ｄ，ｂ）中ｃ出现了两次。但（c，d，b，c）是初级回路。 7.2通路、回路、图的连通性 7.2通路、回路、图的连通性 连通性 设Ｇ＝（Ｖ，Ｅ）， （Ｖ0，Ｖ1，…，Ｖk） 是G中的一条通路，则称Ｖ0到Ｖk连通或可达。 说明：对无向图而言，若Ｖ0到Ｖk可达，则Ｖk到Ｖ0也可达。对有向图而言则未必。 7.2通路、回路、图的连通性 连通分支 无向图Ｇ可分为几个不相连通的子图，每一子图本身都是连通的。称这几个子图为Ｇ的连通分支。 无向图的连通性 若Ｇ＝（Ｖ，Ｅ）中任两个顶点都连通，则称此无向图是连通的。 7.2通路、回路、图的连通性 任意一个连通无向图的任两个不同顶点都存在一条简单通路。 有向图的连通性 (1)弱连通： 若Ｇ＝（Ｖ，Ｅ）对应的无向图是连通图，则称Ｇ为弱连通。 (2）强连通： 若Ｇ＝（Ｖ，Ｅ）中任两点间都有路，即对ａ与ｂ，ａ到ｂ可达，ｂ到ａ可达，称Ｇ为强连通。 7.2通路、回路、图的连通性 7.2通路、回路、图的连通性 1.无向图的关联矩阵 设无向图G=V,E, 为顶点 与边 的关联次数,则称矩阵 为G的关联矩阵,记为 M(G) . 显然, 的可能取值为0( 与 不关联),1( 与 关联1次), 2( 与 关联2次) 即 的以 为端点的环. 从关联矩阵中得到下列性质 1、 （第i行元素之和为 的度数） 2、 ，当且仅当 为孤立点。 3、若第j列与第k列相同，则说明 与 为平行边。 2.有向图的关联矩阵 若有向图D中无环存在,设D=V,E, 令 则称 为D的关联矩阵, 记为M(D) 从关联矩阵中得到下面性质 7.3图的矩阵表示 由邻接矩阵可以看出 1、图中是否有环 2、图是否是零图或完全图 3、每行元素之和即为此行对应结点的出度，每列 元素之和即为此列对应结点的入度。 7.3图的矩阵表示 4、若两结点通过其他点中转，也有可能连通。作邻接矩阵的普通矩阵乘法： ｂij的值表示Ｖi到Ｖj路长为２的道路条数 7.3图的矩阵表示 定理 Ａm的元素ｍij表示Ｖi到Ｖj长度为ｍ的道路的条数。 * *