图论
最小生成树和最短路算法：
如下图：
最小生成树算法：把所有点连通的最小权值和，即用n-1条边连通所有顶点的最小路径和。Prim算法：
把顶点分成两组，A组为已加入生成树中的点，B组未加入任何点。先任取一个顶点，比和1号顶点，加入A组（只需置访问属性为true即可，其它未加入的访问属性都为false）。现在开始在B组中找与1号顶点相连的边权最小的边，把该边相连的另外的顶点x加入A 组，置访问属性为true。再又x点作为中间点，更新其它点至1号点的距离。如上图：初始时，dis[I]的值都为无穷大；再通过读入的边更新dis[1]=0，dis[2]=3,dis[5]=1。1号点加入A组；以1号点开始在B组中搜，得到5号点的边权最小；5号点入A组。以5号点更新其它点到1号点的距离：dis[2]=2 dis[3]=2;再在B组中搜，得到2号点入A组，更新dis[4]=6;再3号点入A组,更新dis[4]=3;再4号点入A组中，到此，最小生成树建好，边权总和为：4。
5 6
1 2 3
1 5 1
2 3 2
2 5 1
2 4 6
3 4 1
伪代码如下：
path:array[1..n,1..n]of longint;
flag:array[0..n]of Boolean;
dis:array[0..n]of longint
procedure init;
readln(n,e);
for I:=1 to e do
readln(a,b.w);
path[a,b]:=w;
path[b,a]:=w;
for I:=0 to n do
dis[I]:=maxlongint shr 1;
dis[1]:=0;
ans:=0;
while true do
begin
p:=0;//用来快速判断是否还有未访问的点
for I:=1 to n do//找边权值最小的点
if (not flag[p]) and ((p=0) or (dis[I] p:=I; if p=0 then break;//全部找到后，打断循环，退出 flag[p]:=true; inc(ans,dis[p]); for I:=1 to n do//更新到1号点的路径值，用边权值更新 dis[I]:=min(dis[I],path[p,I]); end; 算法复杂度为O（n^2）。对于顶点数不多，边多的图特适合。如果顶点数超过10000，而边又很少的情况下，即稀疏图，此时可又采用kruskal算法。 kruskal算法 由prim算法可知，在做最小生成树时，每次都是找最小的边。我们可又换个思路，用一个记录： tree=record a,b:longint; w:longint end tree记录中，a,b用来记录边的两个顶点，w用来记录边权。先把所有边按照边权从小到大排序，再结合并查集，从小到依次处理每条边。如上图：边权排序后： 1 5 1 2 5 1 3 4 1 2 3 2 1 2 3 2 6 4 初始时，father[I]:=I，置每个顶点的父亲顶点为I。先处理第一条边，1 5两个顶点合并，表示已加最小生成树中，相当于一个集合；再处理第2条边，2也加入最小生成树中，此时集合中有1 2 5；再处理第三条边3 4 1，3 4也加入集合。再处理第四条边2 3 2，由于2 3已在集合中，则此条边不用加入；再处理1 2 3，由于1 2已在集合中，不处理，再处理2 4 6，由于2 4已经在集合中，则不需要再处理了。判断是否在一个集合中，用并查集判断。Const Maxn=100000; Type Tree=record A,b,w:longint; End; Var Path:array[1..maxn] tree; F:array[1..maxn]of longint; function find_set(u:longint):longint; begin if (f[u]=u) then exit(u); f[u]:=find_set(f[u]); exit（f[u]）; end; procedure qs;(按边权快排) readln（n,e）; for I:=1 to e do read(path[I].a,path[I].b,path[I].w); qs(1,e); for I:=1 to e do begin if find_set(path[I].a) <> find_set(path[I].w) then inc(cnt); inc（ans,path[I].w）; if cnt=n-1 then break; f[find_set(path[I].a)]:=find_set(path[I].b); end; if cnt<>n-1 then writeln（“无法构一棵树”） else writeln(ans); 最短路： 一、求任意两点间的最短路，则用floyd； 二、求某个点到其它点的最短路，即单元最短路径，可用dijsktra和spfa算法 1.dijsktra 求1号点到其它点的最短路 思路： 在剩下的点中，找一个距离最短的点，5号顶点合乎条件。5号入A组。用再5号更新其它点到1号点的距离，dis[I]>dis[5]+path[5,I]，则更新。左边不等式称之为三角形不等式 按顺序找，依次2，3，4入A组，至此，分别求出了1号点到其它点的最短距离。 Read(N,e); For I:=1 to e do begin Read(a,b,w); Path[a,b]:=w; Path[b,a]:=w; End; For I:=1 to n do Dis[I]:=maxlongint shr 1; Dis[1]:=0; While true do Begin J:=0; For I:=1 to n do If (not flag[I]) and ( (j=0) or (dis[j]>dis[I])) then J:=I; If j=0 then break;//一旦找不到这样的点，就退出，主要可又考虑不连通的图Flag[j]:=true; For I:=1 to n do If (not flag[I]) then Dis[i]:=min(dis[I],dis[j]+path[j,I]); End; 如果求的是指定的两个点：S，T，则上述代码可以改为： Read(N,e,S,T); For I:=1 to e do begin Read(a,b,w); Path[a,b]:=w; Path[b,a]:=w; End; For I:=1 to n do Dis[I]:=maxlongint shr 1; Dis[S]:=0; While true do Begin J:=0; For I:=1 to n do If (not flag[I]) and ( (j=0) or (dis[j]>dis[I])) then J:=I; If (j=0)or (j=t) then break;//一旦找不到这样的点,或者已经到T了 Flag[j]:=true; For I:=1 to n do If (not flag[I]) then Dis[i]:=min(dis[I],dis[j]+path[j,I]); End; 此算法最坏的时间复杂度为：O(n^2) 2.SPFA spfa用类似于队列的方法。求1号点其它点的最短距离 1号点入队，置1号点为true，用1号点更新其它点的dis距离值。此时2，5入队。置2，5的flag(访问标志)为true。然后，再置1号点的访问标志为false，下次还允许它进队，因为以后进队的点也有可能更新到1号点 队列已空，由此算出了各个点到1号点的最短距离。 Readln(n,e); For I:=1 to e do Read(a,b,w); Path[a,b]:=w Path[b,a]:=w; Dis[1]:=0; Head:=1; Tail:=1; Q[1]:=1; Flag[1]:=true; While (head<=tail) do Begin U:=q[head]; Inc(head); For I:=1 to n do If dis[I]>dis[u]+path[u,I] then begin Dis[I]:=dis[u]+path[u,I];//更新点 If (not flag[I]) then//被更新的点不大队列中，则入阶 Begin Flag[I]:=true; Inc(tail); Q[tail]:=I; End; End; Flag[u]:=false;//u出队 End; 1、略 2、计算有向无圈图的根 输入一个有向无圈图DAG，计算和输出DAG的根r（即r到其他任何顶点都有一条路。若图中没有根，则输出“not found”）。 输入：顶点数n和边数e;以下为e行，每行为一条有向边的两个端点 输出：根r或者“not found” 算法分析 设 const mx=100;{顶点数的上限} var n,e,i,j,k,a,b:integer;{ 顶点数n、边数e} g:array[1..mx,1..mx]of boolean;{传递闭包} bn:boolean;{根存在标志} 1、输入信息，计算传递闭包 readln(n,e);{输入顶点数和边数} fillchar(g,sizeof(g),0);{ 有向无圈图初始化} for i:=1 to e do{输入信息，构造传递闭包的初始值} begin readln(a,b);g[a,b]:=true end; for k:=1 to n do{计算传递闭包} for i:=1 to n do for j:=1 to n do if g[i,j] or g[i,k] and g[k,j]then g[i,j]:=true; 2、计算DAG的根 然后枚举每一个顶点。根据传递闭包的信息，若当前顶点至其它所有顶点有路，则判定该顶点即为根。若没有一个顶点可作为DAG的根，则输出失败信息 for i:=1 to n do{枚举每一个可能的根} begin bn:=true;{设定I至其他所有顶点有路的标志} for j:=1 to n do{若I至任一个顶点无路，则返回bn为false} if (i<>j) and not g[i,j] then begin bn:=false; break end; if bn then break{若I至其他所有顶点有路，则输出根i} end; if bn then writeln(i) else writeln('not found'){若不存在根，则输出失败信息} 图论法用于供水管网水力计算的研究 图论法用于供水管网水力计算的研究 摘要：图论理论是网络分析的主要工具，现用于管网的水力平衡计算，既充分发挥了图论理论的优势，使计算变得简便、迅捷，又可将管网附件加入计算，使结果更准确、更符合实际。文中采用峰阵输入管网结构，使输入数据的工作量大大减少，易于编制程序，计算大型的复杂管网。 关键词：供水管网水力计算图论法 前言 供水管网的水力平衡计算是供水系统规划设计、经济评价和运行管理的基础。水力平衡计算的目的就是在确定管径的情况下求出满足连续方程和能量方程的各节点压力水头和各管段流量。目前常用的水力平衡计算方法有哈代-克罗斯法(Hardy-Cross)，牛顿-莱福逊法(New ton-Raphson)，线性理论法(Linear-Theory)，有限元法(Finite Element)等等。所有这些方法各有所长，适用范围各不相同，有的还需人工假设管段流量，使输入数据工作量增大，且未考虑管网附件的影响。本文介绍的图论法将复杂的管网处理为相应的“网络图”，并建立相应的数学模型，用峰阵输入原始数据来描述管网结构，输入的数据量最少，不易出错，易于计算大型的复杂管网。其计算过程可同 时考虑管网附件，如控制阀、加压泵、逆止阀、减压阀等，使计算结果更符合实际。 1 图论原理 将供水管网中的管段概化成一条线段(即图中的边)，将有附件的管段看成图中的特殊管段，边与边由节点相连。这样，一个供水系统的管网图就转化为图论中的网络图。而且管道中的水流是有方向的，所以管网图是有向图。 根据以上所述原则，可将图1所示管网系统，转化为图2所示的网络图。 图1 图2 图1中有一水库A，三个给水点B、C、D，Q1表示水库节点供水量，Q2\,Q3\,Q4分别表示B、C、D节点的用水量。管段视为网络图中的对应边，管段的直径、管长、管道流量、摩损系数等作为管段对应边的权。至此，与管网同构的网络图生成了。图中箭头表示各条边的方向，即管段中水流方向。 网络图中节点与边的关联函数可以用完全关联矩阵I4×5表示如式(1)所示。 顶点边的编号 离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝ 离散数学图论与系中有图题目 ————————————————————————————————作者：————————————————————————————————日期： 图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1) 习题一 作者---寒江独钓 1.证明：在n 阶连通图中 (1) 至少有n-1条边； (2) 如果边数大于n-1，则至少有一条闭迹； (3) 如果恰有n-1条边，则至少有一个奇度点。 证明: (1) 若G 中没有1度顶点，由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 若G 中有1度顶点u ，对G 的顶点数作数学归纳。 当n=2时，结论显然；设结论对n=k 时成立。 当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G 的边数≥k. (2) 考虑G 中途径： 121:n n W v v v v -→→→→L 若W 是路，则长为n-1;但由于G 的边数大于n-1,因此，存在v i 与v j ,它们相异，但邻接。于是： 1i i j i v v v v +→→→→L 为G 中一闭途径，于是 也就存在闭迹。 (3) 若不然，G 中顶点度数至少为2，于是由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 这与G 中恰有n-1条边矛盾！ 2.(1)2n ?12n 2?12n ?1 (2)2n?2?1 (3) 2n?2 。 证明 :u 1的两个邻接点与v 1的两个邻接点状况不同。所以， 两图不同构。 4.证明下面两图同构。 u 1 v 1 证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 5.指出4个顶点的非同构的所有简单图。 分析：四个顶点的简单图最少边数为0，最多边数为6，所以 可按边数进行枚举。 (a) v 2 v 3 u 4 u (b) 数学建模中的图论方法 一、引言 我们知道，数学建模竞赛中有问题A和问题B。一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A题入手快，而B题不好下手。 另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。 图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如： AMCM90B－扫雪问题； AMCM91B－寻找最优Steiner树； AMCM92B－紧急修复系统的研制(最小生成树) AMCM94B－计算机传输数据的最小时间(边染色问题) CMCM93B－足球队排名(特征向量法) CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性) CMCM98B－灾情巡视路线(最优回路) 等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。 本文将从图论的角度来说明如何将一个工程问题转化为合理而且可求解的数学模型，着重介绍图论中的典型算法。这里只是一些基础、简单的介绍，目的在于了解这方面的知识和应用，拓宽大家的思路，希望起到抛砖引玉的作用，要掌握更多还需要我们进一步的学习和实践。 一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题[1]。一般认为，欧拉的研究是图论的开端。 与一笔画问题相对应的一个图论问题是哈密顿问题。 目录[隐藏] 1 问题的提出 2 一笔画定理 2.1 定理一 2.2 定理二 3 例子 3.1 七桥问题 3.2 一个可以一笔画的例子 4 一笔画问题与哈密顿问题 5 参见 6 参考来源 [编辑] 问题的提出 一笔画问题是柯尼斯堡问题经抽象化后的推广，是图遍历问题的一种。在柯尼斯堡问题中，如果将桥所连接的地区视为点，将每座桥视为一条边，那么问题将变成：对于一个有着四个顶点和七条边的连通图G(S,E)，能否找到一个恰好包含了所有的边，并且没有重复的路径。欧拉将这个问题推广为：对于一个给定的连通图，怎样判断是否存在着一个恰好包含了所有的边，并且没有重复的路径？这就是一笔画问题。用图论的术语来说，就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径（一个圈或者一条链），如果路径闭合（一个圈），则称为欧拉回路[1]。 一笔画问题的推广是多笔画问题，即对于不能一笔画的图，探讨最少能用多少笔来画成。 [编辑] 一笔画定理 对于一笔画问题，有两个判断的准则，它们都由欧拉提出并证明[1]。 [编辑] 定理一 有限图G 是链或圈的充要条件是：G为连通图，且其中奇顶点的数目等于0或者2。有限连通图G 是圈当且仅当它没有奇顶点[2]。 证明[2][3]： 必要性：如果一个图能一笔画成，那么对每一个顶点，要么路径中“进入”这个点的边数等于“离开”这个点的边数：这时点的度为偶数。要么两者相差一：这时这个点必然是起点或终点之一。注意到有起点就必然有终点，因此奇顶点的数目要么是0，要么是2。 充分性： 如果图中没有奇顶点，那么随便选一个点出发，连一个圈C1。如果这个圈就是原图，那么 图论及其应用答案电子科 大 This model paper was revised by the Standardization Office on December 10, 2020 习题三： 证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通， 而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。 必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。 （2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} 习题十 1. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。 证明：（1）先证结论： 因为G是简单图，所以G的结点度上限 max(d(v)) ≤ n-1, G图的总点度上限为 max(Σ(d(v)) ≤ n﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G是完全图 因为G具有上限边数，假设有结点的点度小于n-1,那么G的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G的每个结点的点度都为n-1，G为完全图。 G是完全图 =〉 因为G是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G的边数。■ 2. 设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）≥3。证明：反证法，假设,则G的总点度上限为max(Σ(d(u)) ≤2 n，根据握手定理，图边的上限为max(m) ≤2n/2=n。与题设m = n+1，矛盾。因此，G中存在顶点u，d（u）≥3。■ 3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5） 解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。 可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1) 数理与信息工程学院 课程论文 课程名称图论及其应用 题目图论中邻接矩阵的应用 姓名沈海华朱国淼 学号06200123 06200129 专业信息与计算科学06（1）指导老师卜月华 浅谈图论中邻接矩阵的应用 [摘 要] 使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题，是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。 [关键字] 邻接矩阵、算法、连通性、最小生成树 1、引言 首先介绍图论中邻接矩阵的一个重要定理: G 是一个图,V (G)为 G 的顶点集, E(G)为 G 的边集。设G 中有 n 个顶点，v 1,v 2,…,v n ;A=(a ij )n ×n 为 G 的邻接距阵, 其中 n j i G E v v G E v v a j i j i ij ,...,2,1,) (0)(1=??????∈= 定理 1:设 A (G)为图 G 的邻接距阵,则 G 中从顶点 vi 到顶点 vj,长度为 k 的道路的A k 条数为中的 i 行 j 列元素。 证:对 k 用数学归纳法 k =1时,显然结论成立;假设 k 时,定理A l .A= A l+1 成立,考虑 k +1的情形。 记 A l 的 i 行 j 列元素为l ≥2,因为所以 nj l in j l i j l i l ij a a a a a a a +++=+...2211) 1( (1) 而从v i ,v j 到长 k +1的道路无非是从v i 经 k 步到某顶点v l (1≤l ≤n),再从v l 走一步到v j ; 由归纳假设从v l 到v j 长为 k 的道路共计 而从v l 到v j 长为 1的道路为a ij 条,所以长为k+1的v l 经过k 部到v i 再一步到v j 的道路共有 ∑-+= n l lj k il l ij a a a 1 )()1(条故从v i 经 k +1步到v j 的路径共有 1、 邻接矩阵现实问题中的运用 锁具装箱问题 某厂生产一种弹子锁具,每个锁具的钥匙有 5个槽,每个槽的高度从 {1, 2, 3, 4, 5, 6}6个数 (单位略 )中任取一数由于工艺及其他原因,制造锁具时对 5个槽的高度还有两个限制:至少有 3个不同的数,相邻两槽的高度之差不能为 5,满足以上条件制造出来的所有互不相同的锁具称为一批。销售部门在一批锁具中随意地取每 60个装一箱出售。问每一批具有多少个,装多少箱。 分析：锁具装箱这个问题是一个排列组合的数学问题,但在这里我们用图论中的邻接矩阵方法来解决这个问题。每把锁都有 5个槽,每个槽有 6个高度,至少有三个不同高度的槽。且相邻槽高差不为 。我们先求出无相邻高5差为 5的锁具数量,再减去仅有一个、两个槽高的锁具数目。 先计算由 1, 2, 3, 4, 5, 6构成无 1, 6相邻的情况的数目。为此,构造一个 6 离散数学图论部分综合练习 1 ．设图G ＝ 离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ 图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f 5经典图论问题 5.1 一笔画问题 一笔画算法即是从起点a开始选择关联边（第一这条边不是往回倒，第二这条边在前面延伸路上没有出现过）向前延伸，如果到达终点b，得到a—b迹，判断路上的的边数是否为图的总边数，是就终止，否则选择迹上某个关联边没有用完的顶点v，用同样方式再搜索v—v的闭迹，添加到a—b迹上，即得到a—v---v—b迹，如果这个迹的边数还没有达到总边数，则再选择迹上某个关联边没有用完的顶点。。。。。。逐步扩展即可。 二、弗罗莱（Fleury ）算法 任取v 0∈V(G)，令P 0=v 0； 设P i =v 0e 1v 1e 2…e i v i 已经行遍，按下面方法从中选取e i+1： （a ）e i+1与v i 相关联； （b ）除非无别的边可供行遍，否则e i+1不应该为G i =G-{e 1,e 2, …, e i }中的桥（所谓桥是一条删除后使连通图不再连通的边）； （c ）当（b ）不能再进行时，算法停止。 5.2 中国邮递员问题（CPP ） 规划模型： 设ij x 为经过边j i v v 的次数，则得如下模型。 ∑∈= E v v ij ij j i x z ?min ∑ ∑ E ∈E ∈∈=j i i k v v i v v ki ij V v x x , E ∈∈≤j i ij v v N x ,1 ..t s 5.3旅行推销员问题（TSP，货郎担问题）（NPC问题） 定义：包含图G的所有定点的路（圈）称为哈密顿路（圈），含有哈密顿圈得图称为哈密顿图。 分析：从一个哈密顿圈出发， 算法一：（哈密顿圈的充要条件：一包含所有顶点的连通子图，二每个顶点度数为2） 象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。 算法二： 算法三： 图论第一次作业 By byh |E(G)|,2|E(G)|2G υυ??≤ ??? ?? ??? 1.1 举出两个可以化成图论模型的实际问题 略 1.2 证明其中是单图 证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极 端情况为。 ?1.4 画出不同构的一切四顶单图 ?0条边：1条边： ?2条边：3条边： ?4条边：5条边：?6条边： 1.10G?H当且仅当存在可逆映射θ:V G→V H，使得uv∈E G?θuθv∈E H，其中G和H是单图。（证明充分性和必要性） ?必要性 ?若G?H，由定义可得，存在可逆映射θ:V G→V Hφ:E G→E(H)当且仅当ψ G e=uv时，ψHφe=θuθ(v)，所以uv∈E G? θuθv∈E H ?充分性 ?定义?:E G→E(H)，使得uv∈E G和θuθv∈E(H)一一对应，于是?可逆，且ψ e=uv的充要条件是ψHφe=θuθv，得G?H G 1.12求证(a)?K m ,n =mn，(b)G是完全二分图，则?G≤1 4 v G2 ?(a)对于K m ,n ，将顶集分为X和Y，使得X∪Y=V K m,n， X∩Y= ?，X=m，Y=n，对于X中的每一顶点，都和Y中所有顶点相连，所以?K m,n =mn ?(b)设G的顶划分为X,Y，X=m,Y=v?m，则?G≤ ??K m ,v-m =v?m m≤v2 4 ?证明： ?(a)第一个序列考虑度数7,第二个序列考虑6,6,1 ?(b)将顶点v分成两部分v’和v’’ ?v’ = {v|v= v i, 1≤ i≤ k}, ?v’’ = {v|v= v i, k< i≤ n} ?以v’点为顶的原图的导出子图度数之和小于 ?然后考虑剩下的点贡献给这k个点的度数之和最大可能为 浅谈图论中邻接矩阵的应用 [摘要] 使用邻接矩阵求解有关实际问题符合数学中数形结合的思想,对于更好地理解问题,思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的,它是数学的重要分支,使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题,是源于生活,高于生活。图论作为组合数学的一分支,与其他数学分支,如矩阵论,概率论,拓扑学数值分析都有着重要的联系。 [关键字] 邻接矩阵、算法、连通性、最小生成树 1、引言 首先介绍图论中邻接矩阵的一个重要定理: G是一个图,V (G)为G的顶点集, E(G)为G的边集。设G中有n个顶 点,v1,v2,…,vn;A=(aij)n ×n为G的邻接距阵, 其中 定理1:设A (G)为图G的邻接距阵,则G中从顶点vi 到顶点vj,长度为k的道路的Ak条数为中的i行j列元素。 证:对k用数学归纳法 k =1时,显然结论成立;假设k时,定理Al.A= Al+1成立,考虑k +1的情形。 记Al的i行j列元素为l≥2,因为所以 (1) 而从vi,vj到长k +1的道路无非是从vi 经k步到某顶点vl(1≤l≤n),再从vl走一步到vj; 由归纳假设从vl到vj长为k的道路共计而从vl到vj 长为1的道路为aij条,所以长为k+1的vl经过k部到vi再一步到vj的道路共有条故从 vi经k +1步到vj的路径共有 1、邻接矩阵现实问题中的运用 锁具装箱问题 某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从{1, 2, 3, 4, 5, 6}6个数(单位略)中任取一数由于工艺及其他原因,制造锁具时对5个槽的高度还有两个限制:至少有3个不同的数,相邻两槽的高度之差不能为5,满足以上条件制造出来的所有互不相同的锁具称为一批。销售部门在一批锁具中随意地取每60个装一箱出售。问每一批具有多少个,装多少箱。 分析:锁具装箱这个问题是一个排列组合的数学问题,但在这里我们用图论中的邻接矩阵方法来解决这个问题。每把锁都有5个槽,每个槽有6个高度,至少有三个不同高度的槽。且相邻槽高差不为。我们先求出无相邻高5差为5的锁具数量,再减去仅有一个、两个槽高的锁具数目。 先计算由1, 2, 3, 4, 5, 6构成无1, 6相邻的情况的数目。为此,构造一个6节点的图:将1, 2, 3, 4, 5, 6这6个数作为6个节点,当两个数字可以相邻时,这两个节点之间加一条边,每个节点有自己到自己的一条边。我们得到了锁具各槽之间的关系示意图(见图1)。 由图我们可以试着画出这个图的邻接矩阵来: 邻接矩阵A的所有元素之和表示两个槽高无1, 6相邻的锁具的个数,每个无1, 6相邻的5位数与图1中长度为4的一条链1 - 1对应,如12345, 11111, 22335等。A的k次方中各元素之和就是长度为k的链的个数。事实上,从这2个具体问题可以看出, A 中第i行第j列 的元素指从i开始经过两条边到达j的链数,即从i开始经过一条边到k,再 从k经过一条边达到j, i和j就决定了中间顶点k的数目。于是,利用Matlab就很容易得到。 离散数学（图论部分）1-4章习题课 1. 证明：在10个人中，或有3人互相认识，或有4人互不认识。 证：设x为10人中之任意某人，则在余下9人中：(1) x至少认识其中4人，或(2) x至多认识其中3人（即至少不认识其中6人），两者必居其一。 (1) 若此x认识的4人互不相识，命题得证；否则，互相认识的2人加上x 构成互相认识的3人，命题得证。 (2) 若此x不认识的6人中有3人互相认识，命题得证；否则，由 Ramsey(3,3)=6知，此6人中至少有3人互不认识，此3人加上x为互 不认识的4人，命题得证。 2. 设(a) V={a,b,c,d}，A={ 二、应用题 题0：（1996年全国数学联赛） 有n （n ≥6）个人聚会，已知每个人至少认识其中的[n /2]个人，而对任意的[n /2]个人，或者其中有两个人相互认识，或者余下的n -[n /2]个人中有两个人相互认识。证明这n 个人中必有3个人互相认识。 注：[n /2]表示不超过n /2的最大整数。 证明 将n 个人用n 个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G 。由条件可知，G 是具有n 个顶点的简单图，并且有 （1）对每个顶点x ， )(x N G ≥[n /2]； （2）对V 的任一个子集S ，只要S ＝[n /2]，S 中有两个顶点相邻或V-S 中有 两个顶点相邻。 需要证明G 中有三个顶点两两相邻。 反证，若G 中不存在三个两两相邻的顶点。在G 中取两个相邻的顶点x 1和y 1,记N G (x 1)＝{y 1,y 2,……,y t }和N G (y 1)={x 1,x 2,……,x k },则N G (x 1)和N G (y 1)不相交，并且N G (x 1)（N G (y 1)）中没有相邻的顶点对。 情况一；n=2r ：此时[n /2]＝r ，由（1）和上述假设，t=k=r 且N G (y 1)＝V-N G (x 1)，但N G (x 1)中没有相邻的顶点对，由（2），N G (y 1)中有相邻的顶点对，矛盾。 情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。故k ≠r+1，同理t ≠r+1。所以t=r,k=r 。记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。若x i0y j0?E ，则与x i0相邻的顶点只能是(N G (x 1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G (y 1)-{x j0})∪{w}。但与w 相邻的点至少是3，故N G (x 1)∪N G (y 1)中存在一个不同于x i0和y j0顶点z 与w 相邻，不妨设z ∈N G (x 1)，则z ，w ，x i0两两相邻，矛盾。 题1：已知图的结点集V ={a ,b ,c ,d }以及图G 和图D 的边集合分别为： E (G )={(a ,a ), (a ,b ), (b ,c ), (a ,c )} E (D)={, , 图论部分 一、选择题： 1．欧拉回路是（B ） A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路 2．哈密尔顿回路是（C ） A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路 3．设G 是简单有向图，可达矩阵P(G)刻划下列关系中的是（C ） A 、点与边 B 、边与点 C 、点与点 D 、边与边 4．下列哪一种图不一定是树（C ）。 A.无简单回路的连通图 B. 有n 个顶点n-1条边的连通图 C. 每对顶点间都有通路的图 D. 连通但删去一条边便不连通的图 5.下列哪个不是两个图同构的必要条件 A. 结点数目相等 B. 边数相等 C. 度数相同的结点数目相同 D. 两个图都是平面图 6．在有n 个结点的连通图中，其边数（B ） A. 最多有n-1条 B. 至少有n-1条 C. 最多有n 条 D. 至少有n 条 7．下列图为树的是（C ）。 A 、>><><><=<},,,,,{},,,,{1d c b a a a d c b a G B 、>><><><=<},,,,,{},,,,{2d c d b b a d c b a G C 、 >><><><=<},,,,,{},,,,{3a c d a b a d c b a G D 、>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 二、填充题： 1、n 阶无向完全图K n 的边数是( 2 ) 1(-n n )，每个结点的度数是(n-1)。 2、n 个结点的有向完全图边数是(n(n-1))，每个结点的度数是(2n-2)。 3、设有向图G = < V ，E >，},,,{4321v v v v V =的邻接矩阵?????? ? ? ?=00 010******* 1010A ， 则1v 的入度)(deg 1v - = 3 ，4v 的出度)(deg 4v + =1 ，从2v 到4v 的长度为2的路有 1 条。 4、一棵无向树的顶点数为n ，则其边数为n-1 ，其结点度数之和是2n-2。 5、一个无向图有生成树的充分必要条件是(它是连通图)。 6、设T=〈V,E 〉是一棵树，若|V|>1，则T 中至少存在(2)片树叶。 7、任何连通无向图G 至少有(1)棵生成树，当且仅当G 是(树)，G 的生成树只有一棵。 8、设T 是一棵树，则T 是一个连通且(无简单回路)的图。 9、设无向图G 有18条边且每个顶点的度数都是3，则图G 有(12)个顶点。 10、任一有向图中，度数为奇数的结点有(偶数)个。 11、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（9）。 三、问答题 1、设无向图G= 图论第三次作业 一、第六章 2.证明： 根据欧拉公式的推论，有m ≦l*(n-2)/(l-2), (1)若deg(f)≧4,则m ≦4*(n-2)/2=2n-4; (2)若deg(f)≧5,则m ≦5*(n-2)/3,即：3m ≦5n-10; (3)若deg(f)≧6,则m ≦6*(n-2)/4,即：2m ≦3n-6. 3.证明： ∵G 是简单连通图，∴根据欧拉公式推论，m ≦3n-6; 又，根据欧拉公式：n-m+φ=2,∴φ=2-n+m ≦2-n+3n-6=2n-4. 4.证明： (1)∵G 是极大平面图，∴每个面的次数为3， 由次数公式：2m==3φ, 由欧拉公式：φ=2-n+m, ∴m=2-n+m,即：m=3n-6. (2)又∵m=n+φ-2,∴φ=2n-4. (3)对于3n >的极大可平面图的的每个顶点v ，有()3d v ≥，即对任一一点或者 子图，至少有三个邻点与之相连，要使这个点或子图与图G 不连通，必须把与之相连的点去掉，所以至少需要去掉三个点才能使()(H)w G w G <-，由点连通度的定义知()3G κ≥。 5.证明： 假设图G 不是极大可平面图，那么G 不然至少还有两点之间可以添加一条边e ，使G+e 仍为可平面图，由于图G 满足36m n =-，那么对图G+e 有36m n '=-，而平面图的必要条件为36m n '≤-，两者矛盾，所以图G 是极大可平面图。 6.证明： (1)由()4G δ=知5n ≥当n=5时，图G 为5K ，而5K 为不可平面图，所以6n ≥，（由()4G δ=和握手定理有24m n ≥，再由极大可平面图的性质36m n =-，即可得6n ≥）对于可平面图有()5G δ≤，而6n ≥，所以至少有6个点的度数不超过5. (2)由()5G δ=和握手定理有25m n ≥，再由极大可平面图的性质36m n =-，即可得12n ≥，对于可平面图有()5G δ≤，而12n ≥，所以至少有12个点的度数不超过5. 二、第七章 2.证明： 设n=2k+1,∵G 是Δ正则单图，且Δ>0, ∴m(G)==>k Δ,由定理5可知χˊ(G)=Δ(G)+1.图论基础
图论法用于供水管网水力计算的研究
离散数学测验题--图论部分(优选.)
离散数学图论与系中有图题目
图论张先迪李正良课后习题答案
数学建模中的图论方法
一笔画问题是图论中一个著名的问题
图论及其应用答案电子科大
习题参考解答图论部分
图论学生论文
离散数学图论部分综合练习
离散数学图论部分经典试题及答案
经典图论问题
图论 王树禾 答案
浅谈图论中邻接矩阵的应用
离散数学(图论部分)1-4章习题课
图论习题参考答案
图论部分复习题
电子科大图论答案