离散数学第3章图的基本概念.ppt

计算机数学基础(上) 第2编 图 论 第三章 图的基本概念 3.1 图的概念与性质 一、图的定义与表示 1。图 由结点的集合V和边的集合E组成的有序对 称为图G。 2。有向图、无向图 每条边都是有向边的图称为有向图，每条边都是 无向边的图称为无向图，否则称为混合图。 3。孤立点、零图 不与其它结点相关联的结点称为孤立点，全部由 孤立点构成的图叫做零图。 4。边的重数 具有相同始点和终点的边称为平行边，平行边的 条数称为边的重数。 5。n 阶图 具有n个结点的图称为n阶图，具有n个结点和m 条边的图称为(n,m)图 6。结点的度数 图中与某结点v相关联的边数(自回路算两条边)， 称为该结点的度数，记作deg(v)。其中以v为始点的边 数称为出度deg+(v)，以v为终点的边数成为入度deg-(v) 因此有 图G中结点的最大、最小度数记做(G)、(G) 二、图的基本概念与握手定理 1。握手定理 图G中所有结点的度数之和等于边数的二倍。 推论1 在任何图中，度数为奇数的结点数必为偶数。 推论2 在有向图中，所有结点的入度之和等于所有结 点的出度之和。 例题1： 已知图G中有1个1度结点，2个2度结点，3个3度结 点，4个4度结点，则G的边数是 。 解： 例题2： 设图G=，则下列结论成立的是 。 A) B) C) D) 例题3： 设简单连通无向图G有12条边，G中有2个1度结点, 2个2度结点，3个4度结点，其余结点度数为3，求G中 有多少个结点。试作一个满足该条件的简单无向图。 解:设G中有x个结点，则3度的结点有x-7。 根据握手定理有， 解得 ,故G中有9个结点。 满足条件的图如下： 2。简单图 不含平行边和环(自回路)的图称为简单图。 在简单图中，任何结点的度数都小于等于n-1。这 是判断一个度数序列能否构成简单图的主要依据。 3。二部图 若将无向图G的结点集分为两部分，而每一部分中 任何两个结点之间都没有边相连，则G称为二部图。 4。完全图 每一对结点之间都有边相连的无向简单图称为无 向完全图，每一对结点之间都有方向相反的两条边相 连的有向简单图称为有向完全图。 具有n个结点的无向完全图Kn的边数为： 例题4： 设图G是有n个结点的无向完全图，则G的边数为 。 A) n(n-1) B) n(n+1) C) D) C 5。正则图 若无向简单图G中每个结点的度数都为k，则G称 为k-正则图。 6。赋权图 若图G中的每一条边都有一个表示长度的实数， 则图G称为赋权图或网络。图G为无向图称为无向赋权 图，图G为有向图称为有向赋权图。 7。补图 由图G中的所有结点和构成完全图需添加的边所 组成的图称为G的补图，记作 。 例题5： 已知图的结点集 以及图G和图D的 边集合分别为： 试作图G和图D，写出各结点的度数，回答图G、图D 是简单图还是多重图？ 解：a d a d b c b c 图G 图D 图G： 图D： 图G不是简单无向图，图D是简单有向图。 8、子图 1。已知图G=，如果 则G=称为G的子图。 2。如果 ，则称G为G的真子图。 3。如果 ，则称G为G的生成子图。 三、图的同构 如果图G中的结点集V与图G中的结点集V具有 一一对应的关系，并且对应的边都具有相同的重数， 则称G与G同构，记作 。 因此，两图同构必须满足下列条件： 结点数相同， 边数相同， 度数相同的结点数相同。 上述条件是两图同构的必要条件，但不是充分条 件，也就是说，两个图即使满足上述条件也不一定同 构。如果把其中一个图中的结点重新排列，边跟着结 点移动，并且可以任意弯曲，能够与另一图完全 重合，那么这两个图是同构的。 四、通路与回路 1。通路、回路 在G=中，如果从结点v0依次经过边和结 点可以到达vn，则称v0与vn间存在通路，或v0与vn连 通，记作v0vn ，如v0vn则称为回路。通路经过 的边数称为通路的的长度。 2。简单通路、简单回路 没有重复边的通路称为简单通路，没有重复边 的回路称为简单回路。 3。基本通路、基本回路 没有重复结点的通路称为基本通路，没有重复 结点的回路称为基本回路。 例题6： 设G如图，已知通路 试回答它们各是简单通路、简单回路、基本通路 和基本回路。 解：是简单通路，基本通路，是简单回路，但不 是基本回路，是简单回路，基本回路，是简单通 路，但不是基本通路。 v1 v2 v5 v3 v4 一、连通性 若在无向图G中，任何两个不同的结点都是连通的 则称G是连通图。 无向图中结点的连通关系具有自反性、对称性和 传递性，所以结点的连通关系是等价关系。 若图G不是连通图，但如果把G分成几个部分，每 一个部分都是连通的，则每一个部分称为一个连通子 图，每一个连通子图G称为G的一个连通分支。 G中相互连通的结点一定在同一连通分支中。 无向图G的连通分支数记作W(G)。 3.2 图的连通性 例如G： G不是连通图，但可以划分为三个连通分支。 是一个连通分支， 是一个连 通分支， 是一个连通分支。 称为V的一个划分。 二、有向连通图 1。强连通图、单侧连通图、弱连通图 在有向简单图D中， (1) 若任何两个结点间都可以到达则称为强连通图 (2) 若任何两个结点间，总有一个结点可以到达另一 个结点，则称为单侧连通图， (3) 若在不考虑边的方向的情况下图是连通的，则称 为弱连通图。 连通图举例 强连通图 单侧连通图 弱连通图 2。两个定理 定理6 一个有向图是强连通的充分必要条件是存 在一条至少经过每个结点一次的回路。 定理7 在有向图中，它的每个结点必位于且仅位 于一个强分图中。 例题7： 设Va,b,c,d,与V能构成强连通图的边集E( ) (A) , (B) , (C) , (D) , 三、连通度 1。点割集 在无向连通图G=中，若删除结点集V(包括 所有与V中的结点关联的边)，得到子图GV。若V 是使GV不连通的最小点集，则称V是G的一个点 割集。若V中只有一个结点则称为割点。 换句话说，点割集是指使图G从连通图变成不连 通图需要删除的最小点集。 例如，G： 删除v1后G1 删除v3后G2 删除v1,v3后G3 因此，v1不是点割集，W(G1)=1， v3是点割集，又是割点，W(G2)=2 v1,v3不是点割集，因为它不是最小点集。 例题8： 给定图G，则图G的点割集 是 。 2。边割集 在无向连通图G=中，若删除边集E，得到 子图GE。若E是使GE不连通的最小边集，则称 E是G的一个边割集。若E中仅一条边则称为割边。 换句话说，边割集是指使图G的从连通图变成不 连通图需要删除的最小边集。 例如，G： 删除边(v1,v2)后G1 删除(v1,v2),(v2,v3)后G2 删除(v3,v5)后G3 因此，(v1,v2)不是边割集，W(G1)=1， (v1,v2),(v2,v3)是边割集，W(G2)=2， (v3,v5)是边割集，也是割边， W(G3)=2。 3。连通度 (一)点连通度 若G是无向连通图，V是G的结点数最少的点割集 或GV是平凡图(孤点)，则V中的结点数称为G的点 连通度，记作 。 因此， (1) 若G是平凡图，则V=， ， (2) 若G是完全图，去掉n-1个结点才能成为平凡 图，所以 ， (3) 若G存在割点，则 ， (4) 若G是非连通图，则 。 (二)边连通度 若G是无向连通图，E是G的边数最少的边割集， 则E中的边数称为G的边连通度，记作 。 因此， (1) 若G是平凡图，则E=， ， (2) 若G存在割边，则 ， (3) 若G是非连通图，则 。 (三) 之间的关系 在无向图G中，一定有： 即点连通度不大于边连通度，边连通度不大于结 点的最小度数。 3.3 图的矩阵表示 一、无向图的邻接矩阵 对于无向图G=，若|V|=n，作n阶方阵A(G) 其中的 表示 相关联的边数。 例如图G如下， 可以看出，A(G)是对称矩阵。 主对角线上的元素表示各结点的自回路数。 二、有向图的邻接矩阵 对于有向图D=，若|V|=n，作n阶方阵A(D) 其中的 表示从 的边数。 从下例中可以看出A(D)不再是对称矩阵。 矩阵中所有元素之和等于有向图中的边数。 第 行元素之和表示结点 的出度， 第 列元素之和表示结点 的入度， 图D： 例题9： 设有向图D的邻接矩阵为 A(D)= ， 那么E 。 例题10： 有向图的邻接矩阵(D)= 中第 行元素的 和 是中的结点 的 。 三、计算边数 在邻接矩阵A(D)中， 为长度为1的边数。 在A2(D)中， 为长度为2的边数。 一般地说，在 中， 为长度为 的边 数。 位置 上的数表示从 长度为 的边数。 在A(D)+A2(D)+ +Ak(D)中， 为长度小于等 于k的边数之和，位置 上的数表示从 长度小 于等于k的边数之和。 例如，在前例中