图论与代数系统.ppt

第五章 图论,杨圣洪,3.6 关系的描述关系图：令RAB，则将A、B的元素均画成一个点，如果序偶R，则从点x画一条有向边到点y A={1,2,3,4,5}， R={,,,,,, , , , , }， 则其关系图如下,5.1图的概念与描述,由结点和连结两个结点的连线所组成的对象称为“图” 至于结点的位置及连线的长度无紧要,图的表示：三元组(V(G),E(G),M(E,V))称为图其中V(G)为点的集合(非空集)，E(G)是边集，M(E,V)=边与点连接关系常简化为二元组 (V(G),E(G))称为图简记为G=(V,E)3.6 关系的描述关系图：令RAB，则将A、B的元素均画成一个点，如果序偶R，则从点x画一条有向边到点y 点集A={1,2,3,4,5}， 边集R={,,,,,, , , , , }， 则其关系图如下,,3.6 关系的描述关系图：令RAB，则将A、B的元素均画成一个点，如果序偶R，则从点x画一条有向边到点y 右边是关系矩阵图论中称为 邻接矩阵,,5.1图的-邻接矩阵 VS 关系矩阵 有向图 VS 关系图,对于有向图，如果从结点vi到结点vj之间有一条边，则a(i,j)=1，否则为0。

由于结点vi到vj有一条边，反过来vj到vi之间不一定有一条，故不一定对称对于无向图，如果结点vi到Vj有一条边，则a(i,j)=1，否则为0由于Vi到Vj有一条边时，反过来Vj到Vi肯定也有一条边故它是对称的可表示自环，不能表示重边,,无向图只有边相联，不考虑方向,5.1点与边—关联矩阵！,关联矩阵表示结点与边之间的关联关系 对于有向图：若点Vi是边ej的起点，则b(i,j)=1若点Vi是边ej的终点，则b(i,j)=-1如果以上两种情况不存在，则b(i,j)=0 对于无向图：如果Vi是ej某个端点，则b(i,j)=1否则 b(i,j)=0 该矩阵的行对应为“点”，列对应“边”， n×m.,,,,ej,Vi,,,,ej,Vi,,,ej,Vi,,,,ej,,Vi,,,,,重边可表示，自环不可能表示,A,B,C,D,e1,e2,e3,e4,e5,e6,e7,a,b,c,d,e1,e2,e3,e4,e5,e6,V={a, b, c, d} E={e1,e2,e3,e4,e5,e6} |V|称为结点数，记为n 该值有限，有限图 |E|称为边数，记为m.该值有限。

有限图 无限图,如果每条边都有方向的，则为有向图 如果每条边都没有方向，则为无向图 某些边有方向，某些边没有方向，混合图,有向图 无向图,点与点邻接,有向边e1=，A与D相邻,e1与A、D相关联A称为D的直接前趋(父结点)，D为A后继点与点相邻, 点与边关联无向边e1=(a, b), a与b相邻，e1与a、b相关联 只与一个结点关联的自环/自旋某两个点之间有多条边为重边(多重图)无环无重边简单图,,,,,,点的度-有趣的概念,,,,,,,某结点关联边的条数，称为该点的度数： D(A)=5,d入(A) =1,d出(A) =4, 有向图 d入(A) +d出(A) =d(A)=5 “入”进入某结点的边，也称为“负边”，负度 “出”离开某结点的边，也称为“正边”，正度,各点度数和=边数的2倍,∑deg(v)=2|E|=2m (为偶数) 证明： 先去掉所有的边，每个点、整个图的度数为0增加一条边e=(u,v)，使结点u与v的度数的各增加1 每增加一条边使整个图的度数增加2∑deg(v)=2|E| =2m(为偶数)握手定理23个人每个人握手9次，有可能吗？,例题某会有23人，主席说每个人恰好只与其他9个人握手，请问主席的话可信吗？解：将以上问题用图表示，23个人则23个点表示，i号同学对应结点i，如果某两位握手，则对应的结点间用一条边相连。

说每个人恰好只与其他9个握手”，每点度数为9，，23人度数和=23*9=207，由握手定理有207=2m，一个奇数不可能等于一个偶数，显然矛盾，故主席的话不可信用图论来解决问题，关键是将问题中的对象表示为结点或边左图=3+2+3+2=10,边数=5，度数和10=边数的2倍(2*5)右图=3+3+3+3=12 ，边数=6度数和12=边数2倍(2*6),图中度数为奇的结点有偶数个,用Vo表示度数为奇(odd)的结点集合，Ve为偶(even)的结点的集合,则有： ∑edeg(v)+ ∑odeg(v)= ∑deg(v)=2m因Ve中每点度数均为偶数∑edeg(v)为偶数，不妨记为2k∑odeg(v)=2m-2k=2(m-k) ，由于Vo中每个结点的度数为奇数，不妨依次记为2n1-1,2n2-1,…,2nt-1，t为个数其和为 2(n1+n2+…nt)-1-1-…-1=2n'-t 2n‘-t=2(m-k) 个数 t=2(m-k)-2n'=2(m-k-n'),例题某会有23人，主席说每个人恰好只与其他9个人握手，请问主席的话可信吗？解：度数为奇数9的结点，只能是偶数，不可能是奇数，故23不可能！,,,,,左图度数为奇的点有:A(5) B(3)共2个 右图度数为奇的点有:B(3),D(3)共2个,有向图握手定理 出度(正度)和=入度(负度)和,在有向图中，每条边都有起点、与终点。

每加一条边使起点的出度增加1，整图的出度增加1， 每加一条边使终点的入度增加1，整图的入度增加1 每边使整图的出度、入度各增加1  所有的边加起来，增加的出度和=入度和正度(出度)=4+1+1+2=8 负度(入度)=1+2+3+2=8 正度和=负度和,例n个结点完全图Kn的边数=n(n-1)/2,Kn:n个结点的完全图 该图的任何两个结点之间都有边相连 每个点都与其它n-1个点之间有边相连 每个点度数为(n-1)，n个点的度数和n(n-1),而整图的度数和为n(n-1)=边数2倍=2m n(n-1)=2m，故边数m=n(n-1)/2任何两个结点之间都有边相连 ， 由组合学可知 m=C(n,2)证明了c(n,2)=n(n-1)/2 说明：简单图中点的度(n-1)，边数n(n-1)/2,边数= n(n-1)/2,例 非空简单图一定存在度相同的结点,证明:图G的结点数记为n由于它是简单图,无重复边与自环, 每点的度数取值范围是0～n-1.当没有度数为0的结点时,每点度数的取值范围是1～n-1，根据鸽巢原则，这n个点中至少有2个点的度数相同当有度数为0的结点时,剔除所有度数为0的结点,对剩下来的结点所组成的图使用前面的证明这是伟大的四色定理的芽头！,3、2、2、3 3、3、3、3,5.2 图的连通性 VS 传递闭包,定义 一个有向图中，从任意结点出发，若沿着边的箭头所指方向，连续不断向前走，能到达所有的结点，则此图连通。

下,否,是,5.2 图的连通性 VS 传递闭包,定义一个无向图中，从任意结点出发，沿着边连续不断向前走，能到达所有的结点，则此图是连通的 传递闭包直观含义,是,5.2 图的连通性,看图判断连通性，仅对结点数比较少的图可行，结点数较多时需要寻求更高效的方法前面求传递闭包时，如果某两个结点之间通过传递可达，则在这两点之间加上一条边(称为复合边)因此求完传递闭包后，如果某二个点之间有边相连，则表明这二个结点：要么未求闭包之前是直接相连的，要么这两个点之前不是直接连接,是通过传递可达图与其邻接矩阵，相当于关系图与其关系矩阵，传递闭包的方法 判断图的连通性，WarShall、邻接矩阵的逻辑幂次方运算由邻接矩阵A计算可达性矩阵P方法： 1、B=A+A2+A3…+An 2、将B中不为零的元素均改换为1，为 零的元素不变，即为可达性矩阵P由邻接矩阵A计算可达性矩阵P方法： 1、B=A+A2+A3…+An 2、将B中不为零的元素均改换为1，为 零的元素不变，即为可达性矩阵PA=,A2=,由邻接矩阵A计算可达性矩阵P方法： 1、B=A+A2+A3…+An 2、将B中不为零的元素均改换为1，为 零的元素不变，即为可达性矩阵P。

A201化, A301化,.,例题 判断下图是是否连通,a(1,3)=0从结点1不能走到结点3，看图可知,其他0类似 a(1,5)=1从结点1出发可达结点5，看图可知,其他1类似,WarShall算法： For I=1 TO N //从第1列到第N列 For J=1 To N //每列从1行到第N行If A[J,I]=1 Then 第J行=第J行∨第I行EndifEndFor //行号J值加1 EndFor // 列号I值加1,,,,,,,,,例题 求跨越1条边、2条边、…、n-1条边的路的条数，即：A、A2、A3、…、An-15.3Euler问题,七桥问题：每桥仅走一次，回到家里,定义5.3.1 如果从某点出发，沿边前行回到起点，称沿途经过的边构成一个回路边可能重复如下图中，a-b-d，a-b-a，a-b-d-c-a 定义5.3.2 如果从某点出发，沿边前行不重走可走遍所有边，是否回到起点不要求，为欧拉路 定义5.3.3如果从某点出发，沿边前行不重走能走遍所有的边，并回到起点则称为欧拉回路有欧拉回路的图也称为欧拉图 欧拉回路是比欧拉路条件更苛刻！,定理5.3.1 无向图G有欧拉回路所有结点度数为偶数. 定理5.3.2无向图G有欧拉路所有结点度数为偶数，或者只有2个结点度数为奇数。

左图：deg(a)=5、deg(b)=3、deg(c)=3、deg(d)=3，故没有欧拉回路，故七桥问题无解中图：deg(a)=deg(d)=3，有欧拉路没无回路 一笔画右图：deg(1)=2 deg(2)=4 deg(3)=4 deg (4)=2 deg(5)=2 故有欧拉回路，为欧拉图一笔画，从度数为奇的结点出发：不重复依次画出每条边，走到另一个奇结点判断下面图能否可以一笔画出,Goes trough each door once?,定义给定有向图G，通过图中每边一次且仅一次的一条单向路(回路)，称作单向Euler路(回路)定理有向图G具有单向Euler回路G连通的、每点入度=出度有向图G具有单向Euler路G连通的、除两个端点外，每点入度=出度一个端点的入度-出度=1，另一个端点的出度-入度=1出度=入度，则该点的度数为偶数，出度与入度相差为1，则该点度数为单例题 计算机鼓轮的设计设有旋转鼓轮其表面被等分成16等份，如图示,阴影为导体输出1，空白为绝缘体输出0，图中输出为1101顺转一格为1010、再一格为0101，连转16次会得出16个不同的二进制数问鼓轮上16部分怎样安排导体与绝缘体，才能转完大圈后，4个触点能得到16个不同的4位2进制数？,建立8结点的有向图，结点编号为{000,001,010, 011,100,101, 110, 111}。

边:结点100引出的边为1000与1001终点为000, 001即为边的后3位 结点001引出的边0010,0011，分别到达010与011二点！ 有向Euler图,因为图中16条边的编号是互不相同的，鼓轮转动，连续得到的16个数，相当于在右图中连续行走所走过的边而图中每个结点的入度=出度，必存在一条Euler路，e0e1 e3e7e15 e14e12e9 e2e5 e11e6e13e10e4e8.,定义5.3.2 如果从某点出发，沿边前行不重走可走遍所有边，是否回到起点不要求，为欧拉路定义5.3.3如果从某点出发，沿边前行不重走能走遍所有的边，并回到起点则称为欧拉回路有欧拉回路的图也称为欧拉图 欧拉回路是比欧拉路条件更苛刻！,5.4 哈密尔顿图,1859年，英国数学家哈密顿：用一个规则的实心十二面体，标出世界著名的20个城市,5.4 哈密尔顿图,定义5.4.1 如果图中存在一条，经过所有结点一次也仅一次的路，则称为哈密尔顿路如果回到起点称为哈密尔顿回路存在哈密尔顿回路的图称为哈密尔顿图 定义5.4.2 如果图中没有一个结点上有自旋，任意二个结点间最多一条边，则称为简单图 定理5.4.1 设G是具有n结点的简单图，如果G中每一对结点度数和≥n-1，则G中存在一条哈密尔顿路。

即存在一条经过所有点一次的路 定理5.4.2 设G是具有n结点的简单图，如果G中每一对结点度数和≥n，则G中存在一条哈密尔顿回路即存在一条经过所有点一次的回路充分而不必要！,。