离散数学 图论-通路与回路

2)有向图关联矩阵的性质 （1） ∑mij= 0，j＝1，2，…，m，从而∑∑mij = 0，这说明M(D)中所有元 素之和为0． (2) M(D)中，负1的个数等于正1的个数，都等于边数m，这正是有向图握手定 理的内容（入度之和等于出度之和）． （3）第i行中，正1的个数等于d+(vi)（结点的入度），负1的个数等于d-(vi) （结点的出度）． （4）平行边所对应的列相同 3、有向图的邻接矩阵 1）定义：设有向图D＝<V，E>，V＝{v1，v2，…，vn}，E＝{e1，e2，…，em} 令： aij为顶点vi邻接到顶点vj边的条数 称(aij))nxn为D的邻接矩阵，记作A(D)，或简记为A． 2）邻接矩阵的性质 （1）每列元素之和为结点的入度，即 ∑aij ＝ d+(vi)，i＝1，2，…，n 所有列的和 ∑∑aij ＝ ∑d+(vi) ＝ m ，等于边数 每行元素之和为结点的出度，所有行的和也等于边数 （2）邻接矩阵中元素 aij 反映了有向图中结点vi到vj通路长度为1的条数
§14.4
图的矩阵表示
一、图的矩阵表示 用矩阵表示图之前，必须将图的顶点或边标定成顺序，使其成为标定图 1、无向图的关联矩阵 1）定义14．24 设无向图G＝<V，E>，V＝{v1,v2,…，vn}。 E={e1,e2,e3，…em}，令mij为顶点vi与边ej的关联次数，则称(mij)nxm为G的 关联矩阵，记作 M(G)． 2）关联矩阵的性质: 关联矩阵是n行（结点数）m列（边数）的矩阵
2、结点的相互可达 若vi → vj 且vj → vi 则称vi与vj是相互可达的，记作: vi ↔ vj 规定vi ↔ vi ． 3、 结点的可达关系为V上的二元关系，但不是等价关系（不满足对称性）。 相互可达关系为V上的二元关系，且是V上的等价关系． 有向图中顶点之间的可达关系既无对称性，也无反对称性 4、有向图中结点的距离 定义：设D＝<V，E>为有向图 ∀ vi,vj ∈V，若 vi → vj，称vi到vi长度最短的通路为vi到vj的短程线 短程线的长度为vi到vj的距离，记作d<vi，vj> 注：该定义与无向图中顶点vi与vj之间的距离d(vi，vj)的区别：无对称性 一般地：d<vi，vj> ≠ d<vj，vi> （可能d<vi，vj> 不存在） 5、弱连通图、单向连通图和强连通图 定义1 设D＝{V，E)为一个有向图． 若D的作为无向图是连通图，则称D是弱连通图，简称为连通图． 定义2 设D＝{V，E)为一个有向图， 若∀ vi,vj ∈V , vi → vj与vj→ vi至少成立其一，则称D是单向连通图． 若∀ vi,vj ∈V，均有vi ↔ vj，则称D是强连通图 注：三种图的关系：强连通图一定是单向连通图，反之不成立 单向连通图一定是弱连通图．反之不成立
离散数学
通路与回路
§14.2
1、通路
通路、回路
1）定义：给定有向图D中的任何一个边序列L，如果其中的任何一条边的终点， 都是继之出现的边(如果存在的话)的始点，则称这样的边的序列是图G的通 路。 若序列中首尾结点相同，则称L为回路。 2）定义：有向图D中，边序列中的各条边全都是互不相同的通路，称为简单通 路。（无重复边） 3）定义：相同，则称通路为初级回路或圈。（无重复点） 4）定义：序列中边的条数称为它的长度
2、简单通路和初级通路的关系
有向图中的每一条初级通路，也都必定是简单通路。 反之不成立 回路也可分为简单回路和初级回路。
3、通路的表示：
可仅用通路中的边序列表示：e1e2…ek 也可仅用通路中所经过的结点的序列表示：v1v2v3…vk
4、性质： 1）定理 在n阶图D中，若从顶点vi到vj(vi≠vj)存在通路，则从vi到vj存在 长度小于或等于(n—1)的通路 若大于n-1，则存在相同节点（有回路），将回路删去可得 2）在n阶图D中，若从顶点vi到vj存在通路，则vi到vj一定存在长度小于或等 于n—1的初级通路(路径) 3）定理 在一个n阶图D中，若存在vi到自身的回路，则一定存在vi到自身长 度小于或等于n的回路． 4）在一个n阶图D中，若存在vi到自身的简单回路，则一定存在长度小于或等 于n的初级回路．
6、有关强连通图与单向连通图的判定 （1）定理： 设有向图D＝<V，E>，V＝{v1，v2，…，vn}． D是强连通图当且仅当D中存在经过每个顶点至少一次的回路． (2) 定理 设D是n阶有向图 D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路．
例2．设有向图D是单向连通图，但不是强连通图，问在D中至少加几条边所 得图D’就能成为强连通图? 作业：P292 16、17、18、39、40（1、2）、43
返回
结点数相同边数相同 结点的度相同 但是两个图 不同构 返回
（b),(c) 互为补图
自补图
返回
4、有向图的可达矩阵 1）定义：设D＝<V，E>为有向图, V＝{v1，v2，…，vn} 令 1 vi可达vi pij ＝ 0 否则 称(pij)nxn为D的可达矩阵，记作P(D)，简记为P 2）可达矩阵的性质 （1）主对角线元素均为1 （每个结点自身可达） （2）可通过图的邻接矩阵A的n-1次幂Bn-1得到（将其非零元素换为1，主 对角线元素均设为1即可）
以上概念均可用在无向图G中 §14.3 图的连通性
一、无向图的连通性 1、结点的连通： 设无向图G＝<V，E>，∀ u,v ∈V，若u，v之间存在通 路，则称u,v是连通的，记作u ～ v，∀ u ∈V，规定u～u 2、结点的连通关系是等价关系 若定义：～ ＝{<u，v> ┃u，v∈V且 u与v之间有通路} 此关系是自反，对称的，传递的，因而～是V上的等价关系
(1）M(G)每列元素之和均为2，这正说明每条边关联两个顶点(环所关联的两个端 点重合)． ∑mij = 2 (j = 1，2，…，m) (2）M(G)第i行元素之和为结点vi的度数，i＝1，2，…n (3) 所有行的和（即矩阵所有元素之和）等于边数的2倍（该例10＝边数5的2倍 ）。 ∑d(vi)＝∑∑mij= ∑2 ＝ 2m，这个结果正是握手定理的内容（即各顶 点的度数之和等于边数的2倍） ． （4）第j列与第k列相同，当且仅当边ej与ek是平行边． (5) 某行i的和为0（即 ∑mij = 0）,当且仅当vi是孤立点． 2、有向图的关联矩阵 定义：设有向图D＝<V，E>中无环，V＝{v1，v2，…，vn}。 E＝{el，e2,…，em}， 令 1 vi为边ej的起点 mij = 0 vi为边ej不关联 －1 vi为边ej的终点 则称(mij)nxm，为D的关联矩阵，记作M(D）
（3）A(D)中所有元素之和为D中长度为1的（边）通路总条数。 主对角线的元素值为图中结点vi长度为1 的环的条数 利用A(D)确定出D中长度为L的通路数和回路数,就需要用到邻接矩阵的幂次运算 （4）A2中的元素值bij是结点vi到vj长度为2 的通路条数： 说明：由矩阵的乘积定义 bij = ∑k aik * akj 由此可推断，A3矩阵中的Cij元素值，表示了从到长度恰为3的通路条数目 （5）定理14．11 设A为有向图D的邻接矩阵，V＝{v1，v2，…，vn} 为D的顶 点集， 则A的L次幂AL(L≥1)中元素cij为D中vi到vj长度为L的通路数， 其中cii为vi到自身长度为L的回路数 ∑∑cij(所有元素之和)为D中长度为L的通路总数， 其中 ∑cii为D中长度为L的回路总数． 推论 设BL＝A + A2十…+AL (L≥1)， 则BL中元素 bij为D中长度小于或等于L的通路数， 其中主对角线上元素值为D中长度小于或等于L的回路数
3、无向图的连通图 定义14．13 若无向图G是平凡图或G中任何两个顶点都是连通的，则称G 为连通图，否则称G为非连通图或分离图 4、结点之间的距离 1）定义：设u，v为无向图G中任意两个顶点 若u ～ v，称u，v之间长度最短的通路为u，v之间的短程线 短程线的长度称为u，v之间的距离，记作 d(u，v) 当u，v不连通时，规定d(u，v)＝ ∞ ． 2）无向图结点的距离有以下性质： 1．d(u，v) ≥ 0，u = u时，等号成立． 2．具有对称性：d(u，v )＝d( v，u)． 3．满足三角不等式：∀ u,v ，w ∈ V(G)，则 d(u，v)+d(v，w) ≥ d(u，w) 二、有向图的连通性 1、结点的可达性 定义： 设D＝<V，E>为一个有向图．∀ vi,vj ∈V，若从vi到vj存在通路 则称vi可达vj, 记作vi → vj 。 规定vi总是可达自身的，即vi → vi．
无向图G： V={v1，v2， v3 } E ={ (v1,v2), (v1,v2), (v2,v2), (v2,v2), (v3,v2), (v3,v2), (v1,v3), }
有向图D： V={v1，v2， v3 } E ={ <v1,v2>, <v2,v1>, <v2,v1>, <v2,v3>, <v3,v3>, <v3,v3>, }