图论法
图论算法
图论算法在计算机科学种扮演者很重要的角色，它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基本算法加以解决。遗传算法是解优化问题的有效算法，而并行遗传算法是遗传算法研究中的一个重要方向，受到了研究人员的高度重视。
特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization ）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network ）。与图和网络相关的最优化问题就是网络最优化或称网络优化 （netwok optimization ）问题。
哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回 到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。
深度优先搜索、广度优先搜索、无向图、有向图、最小生成树、最短路径。 求最短路迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。
(i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。
(ii) 对每个i S v ∈（i i S V S \=），用
)}()(),({min uv w u l v l i
S u +∈ 代替)(v l 。计算)}({min v l i
S v ∈，把达到这个最小值的一个顶点记为1+i u ，令}{11++=i i i u S S 。
(iii). 若1||-=V i ，停止；若1||- 算法结束时，从0u 到各顶点v 的距离由v 的最后一次的标号)(v l 给出。在v 进入i S 之前的标号)(v l 叫T 标号，v 进入i S 时的标号)(v l 叫P 标号。算法就是不断修改各项点的T 标号，直至获得P 标号。若在算法运行过程中，将每一顶点获得P 标号所由来的边在图上标明，则算法结束时，0u 至各项点的最短路也在图上标示出来了。 每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra 算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra 算法求出从该起点到其余顶点的最短路径，反复执行n 次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为)(3n O 。第二种解决这一问题的方法是由Floyd R W 提出的算法，称之为Floyd 算法。 假设图G 权的邻接矩阵为0A ， ????? ???????=nn n n n n a a a a a a a a a A 2122221 112110 来存放各边长度，其中： 0=ii a n i ,,2,1 =； ∞=ij a j i ,之间没有边，在程序中以各边都不可能达到的充分大的数代替； ij ij w a = ij w 是j i ,之间边的长度，n j i ,,2,1, =。 对于无向图，0A 是对称矩阵，ji ij a a =。 Floyd 算法的基本思想是：递推产生一个矩阵序列n k A A A A ,,,,,10 ，其中),(j i A k 表示从顶点i v 到顶点j v 的路径上所经过的顶点序号不大于k 的最短路径长度。 计算时用迭代公式： )),(),(),,(min(),(111j k A k i A j i A j i A k k k k ---+= k 是迭代次数，n k j i ,,2,1,, =。 最后，当n k =时，n A 即是各顶点之间的最短通路值。 prim 算法 构造最小生成树设置两个集合P 和Q ,其中P 用于存放G 的最小生成树中的顶点，集合Q 存放G 的最小生成树中的边。令集合P 的初值为}{1v P =（假设构造最小生成树时，从顶点1v 出发），集合Q 的初值为Φ=Q 。prim 算法的思想是，从所有P p ∈，P V v -∈的边中，选取具有最小权值的边pv ，将顶点v 加入集合P 中，将边pv 加入集合Q 中，如此不断重复，直到V P =时，最小生成树构造完毕，这时集合Q 中包含了最小生成树的所有边。 Kruskal 算法构造最小生成树 科茹斯克尔（Kruskal ）算法是一个好算法。Kruskal 算法如下: (i)选)(1G E e ∈，使得min )(1=e w 。 (ii)若i e e e ,,,21 已选好，则从},,,{)(21i e e e G E -中选取1+i e ，使得 ① }],,,,[{121+i i e e e e G 中无圈，且 ② min )(1=+i e w 。 (iii)直到选得1-νe 为止。 人员分派问题：工作人员n x x x ,,,21 去做n 件工作n y y y ,,,21 ，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？ 这个问题的数学模型是：G 是二分图，顶点集划分为Y X G V =)(，},,{11n x x X =， },,{11n y y Y =，当且仅当i x 适合做工作i y 时，)(G E y x i i ∈，求G 中的最大对集。 匈牙利算法： （i ）从G 中任意取定一个初始对集M 。 （ii ）若M 把X 中的顶点皆许配，停止，M 即完美对集；否则取X 中未被M 许配的一顶点u ，记}{u S =，Φ=T 。 （iii ）若T S N =)(，停止，无完美对集；否则取T S N y -∈)(。 （iv ）若y 是被M 许配的，设M yz ∈，}{z S S =，}{y T T =，转（iii ）；否则，取可增广轨),(y u P ，令))(())((M P E P E M M --= ，转（ii ）。 把人员指派问题、匈牙利算法稍加修改就能够用来求二分图的最大对集。 Kuhn-Munkres 算法（i ）选定初始可行顶点标号l ，确定l G ，在l G 中选取一个对集M 。 （ii ）若X 中顶点皆被M 许配，停止，M 即G 的权最大的完美对集；否则，取l G 中未被M 许配的顶点u ，令}{u S =， Φ=T 。 (iii)若T S N l G ?)(，转（iv ）；若T S N l G =)(，取 )}()()({min ,xy w y l x l T y S x l -+=?∈α， ?? ???∈+∈-=其它),(,)(,)()(v l T v v l S v v l v l l l αα， l l = ，l l G G =。 （iv ）选T S N l G -)(中一顶点y ，若y 已被M 许配，且M yx ∈，则}{z S S =， }{y T T =，转（iii ） ；否则，取l G 中一个M 可增广轨),(y u P ，令 ))(())((M P E P E M M --= ， 转（ii ）。 其中)(S N l G 是l G 中S 的相邻顶点集。 经过G 的每条边的迹叫做G 的Euler 迹；闭的Euler 迹叫做Euler 回路或E 回路；含Euler 回路的图叫做Euler 图。 直观地讲，Euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。 包含G 的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton 轨叫做Hamilton 圈或圈；含Hamilton 圈的图叫做Hamilton 图。 直观地讲，Hamilton 图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。 Fleury 算法： 1o . )(0G V v ∈?，令00v W =。 2o . 假设迹i i i v e v e v W 110=已经选定，那么按下述方法从},,{1i e e E -中选取边1+i e ： （i ）1+i e 和i v 相关联； （ii ）除非没有别的边可选择，否则1+i e 不是},,{1i i e e G G -=的割边(cut edge)。(所谓割边是一条删除后使连通图不再连通的边)。 3o . 当第2步不能再执行时，算法停止。 对于非Euler 图，1973年，Edmonds 和Johnson 给出下面的解法： 设G 是连通赋权图。 （i ）求)}2(mod 1)(),(|{0=∈=v d G V v v V 。 （ii ）对每对顶点0,V v u ∈，求),(v u d （),(v u d 是u 与v 的距离，可用Floyd 算法求得）。 （iii ）构造完全赋权图||0V K ，以0V 为顶点集，以),(v u d 为边uv 的权。 （iv ）求||0V K 中权之和最小的完美对集M 。 （v ）求M 中边的端点之间的在G 中的最短轨。 （vi ）在（v ）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。 （vii ）在（vi ）中得的图'G 上求Euler 回路即为中国邮递员问题的解。 最大流问题---参照《运筹学》第十一章p229-p253 许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 最大流问题的限制条件： 一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）； 二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14 对于给定的网络D=（V ,A,C ）和给定的流 ，若 满足下列条件： （1） （1） 容量限制条件：对每一条弧 ，有 (7.9) （2）平衡条件： 对于中间点： 流出量=流入量，即对于每一个i (i ≠s,t)，有 (7.10) 对于出发带点 ，有 (7.11) 对于收点 ，有 (7.12) 则称 为一个可行流， 称为这个可行流的流量。 注意，我们这里所说的出发点 是指只有从 发出去的弧，而没有指向 的弧；收点 是指只有弧指向 ，而没有从它的发出去的弧。 寻求最大流的标号法（Ford , Fulkerson） 从一个可行流出发（若网络中没有给定，则可以设是零流），经过标 号过程与调整过程。 1）标号过程 在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点，每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量θ用的。 标号过程开始，总先给v s标上(0,+∞)，这时v s是标号而未检查的点，其余都是未标号点，一般地，取一个标号而未检查的点v i，对一切未标号点v j： (1) 在弧上，，则给v j标号。这里。 这时点v j成为标号而未检查的点。 上，，给v j标号。这里。这 (2) 若在弧 成为标号而已检查过的点，重复上述步骤，一旦被标上号，表明得到一条 于是 从 若所有标号都是已检查过，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。 2）2 调整过程首先按 及其它点的第一个标号，利用“反向追踪”的办法，找出增 广链μ。例如设v 的第一个标号为（或），则弧（或相应地）是 的第一个标号，若为（或），则找出（或相应地 μ上的弧。接下来检查 的第一个标号，依此下去，直到为止。这时被找出的弧就构成了 ）。再检查 。令调整量θ是，即的第二个标号。 增广链 令 去掉所有的标号，对新的可行流，重新进入标号过程。 二分匹配 二分图的相关性质(1) 二分图的最大匹配数等于最小覆盖数，即求最少的点使得每条边都至少和其中的一个点相关联，很显然直接取最大匹配的一段节点即可。 (2) 二分图的独立数等于顶点数减去最大匹配数，很显然的把最大匹配两端的点都从顶点集中去掉这个时候剩余的点是独立集，这是|V|-2*|M|，同时必然可以从每条匹配边的两端取一个点加入独立集并且保持其独立集性质。 (3) DAG的最小路径覆盖，将每个点拆点后作最大匹配，结果为n-m，求具体路径的时候顺着匹配边走就可以，匹配边i→j',j→k',k→l'....构成一条有向路径。 最大匹配：图中包含边数最多的匹配称为图的最大匹配。 完美匹配：如果所有点都在匹配边上，称这个最大匹配是完美匹配。 最小覆盖：最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝最大匹配数 最小路径覆盖：用尽量少的不相交简单路径覆盖有向无环图Ｇ的所有结点。解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：Ｘ结点集中的i和Y结点集中的i',如果有边i->j，则在二分图中引入边i->j'，设二分图最大匹配为m,则结果就是n-m。 最大独立集问题：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值．如果图Ｇ满足二分图条件，则可以用二分图匹配来做．最大独立集点数= N - 最大匹配数 注意要点： （一）每个X节点都最多做一次增广路的起点； （二）如果一个Y节点已经匹配了，那么增广路到这儿的时候唯一的路径是走到Y节点的匹配点（可以回忆最大流算法中的后向边，这个时候后向边是可以增流的）。 求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm) 1.1、prim算法: 无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。 【Prim算法思想】 任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。【最小生成树算法实例】 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？ 【输入】第一行两个数v(v<=200),e，分别代表城市数和边数以下e行，每行为两个顶点和它们之间的边权w(w<1000)。 【输出】连通所有城市的公路最小造价。 【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】50 原图 最小生成树 #include d[i]=INT_MAX; } d[f]=0; s=0; for(i=1;i<=n;i++) { mi=INT_MAX; for (j=1;j<=n;j++) if ((v[j]==false) && (d[j] 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'){若不存在根，则输出失败信息} 离散数学图论单元测验题 一、单项选择题(本大题共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) 图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法： 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j) 高三第一轮复习资料（个人汇编请注意保密） 引言 1.课程内容： 必修课程由5个模块组成： 必修1：集合、函数概念与基本初等 函数（指、对、幂函数） 必修2：立体几何初步、平面解析几何初步。 必修3：算法初步、统计、概率。 必修4：基本初等函数（三角函数）、平面向量、三角恒等变换。必修5：解三角形、数列、不等式。 以上是每一个高中学生所必须学习的。 上述内容覆盖了高中阶段传统的数学基础知识和基本技能的主要部分，其中包括集合、函数、数列、不等式、解三角形、立体几何初步、平面解析几何初步等。不同的是在保证打好基础的同时，进一步强调了这些知识的发生、发展过程和实际应用，而不在技巧与难度上做过高的要求。 此外，基础内容还增加了向量、算法、概率、统计等内容。 选修课程有4个系列： 系列1：由2个模块组成。 选修1—1：常用逻辑用语、圆锥曲线 与方程、导数及其应用。选修1—2：统计案例、推理与证明、 数系的扩充与复数、框图系列2：由3个模块组成。 选修2—1：常用逻辑用语、圆锥曲线与方程、 空间向量与立体几何。选修2—2：导数及其应用，推理与证 明、数系的扩充与复数选修2—3：计数原理、随机变量及其 分布列，统计案例。 系列3：由6个专题组成。 选修3—1：数学史选讲。 选修3—2：信息安全与密码。 选修3—3：球面上的几何。 选修3—4：对称与群。 选修3—5：欧拉公式与闭曲面分类。选修3—6：三等分角与数域扩充。系列4：由10个专题组成。 选修4—1：几何证明选讲。 选修4—2：矩阵与变换。 选修4—3：数列与差分。 选修4—4：坐标系与参数方程。 选修4—5：不等式选讲。 选修4—6：初等数论初步。 选修4—7：优选法与试验设计初步。选修4—8：统筹法与图论初步。 选修4—9：风险与决策。 选修4—10：开关电路与布尔代数。 2．重难点及考点： 重点：函数，数列，三角函数，平 面向量，圆锥曲线，立体几 何，导数 难点：函数、圆锥曲线 高考相关考点： ⑴集合与简易逻辑:集合的概念与运 算、简易逻辑、充 要条件 ⑵函数：映射与函数、函数解析式与 定义域、值域与最值、反函 数、三大性质、函数图象、 指数与指数函数、对数与对 数函数、函数的应用 一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他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。如果这个圈就是原图，那么 习题十 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) 统筹法与图论初步 统筹法是运筹学中的一个基本方法 , 是现代项目管理理论中最重要的方法之 。本专题将通过实例介绍统筹法及其应用 , 同时介绍图的基本概念 , 给出图上最短路和最小生成树算法 , 使学生对图论及其应用有一初步了解。 内容与要求 1.统筹方法 (1)通过实例了解统筹问题的思想及其应用的广泛性。 (2)通过实例理解统筹法中的基本概念。 (3)通过实例掌握绘制统筹图的方法。 (4)学会计算统筹图中的参数 :事项最早开始时间和最迟到达时间 , 工序的时 (5)学会寻找统筹图的关键路 , 掌握寻找关键路的算法 , 理解关键路的重要性。 (6)会用统筹方法分析和处理简单的实际问题。 2.图论初步 (1)通过实例了解图的基本概念和图在刻画实际问题中关系的作用。 (2)通过实例了解图的生成树 , 掌握求图的生成树和最小生成树的算法。 (3)通过实例了解图的最短路问题 , 掌握求图的最短路的算法。 (4)了解一些图论的其他问题 , 并知道算法的复杂性。 3.完成一个学习总结报告。报告应包括三方面的内容 :(1) 知识的总结。对本专题的内容或部分内容 (统筹法或图论 )的整体思路、结构的理解,对其中蕴涵的数学思想方法的认识。 (2) 拓展。通过查阅资料、调查研究、访问求教、独立思考 ,对某些内容、某些结果和应用进行拓展和深入。 (3) 对本专题的 说明与建议 1. 统筹法是一个应用十分广泛的方法 , 在学习时不仅要求学生掌握该方法 , 还应培养学生的应用意识 , 即让学生结合自己的生活实际 ,有意识地收集可以应用该方法的实际问题。 2. 应让学生认识到 , 在解决实际问题时 ,可能会出现各种复杂因素 (如时间的随机性、成本的变动、人力的调动等 ), 一些现成的方法可能不能完全适用 , 需要结合其他数学工具来进行处理。 3. 在图论初步的教学中 , 一方面应让学生认识到图和网络是许多实际问题的重要数学模型 , 认识到研究它们的重要性 ; 另一方面 ,本专题侧重介绍一些算法 ,要求学生能清楚地表述这些算法 , 同时能对算法的复杂性问题有所了解。 风险与决策 在日常生活和经济活动中 ,例如, 个人的采购、求职、投资 , 工商企业的生产或经营的方案 , 直至部门和全国的某一事业的计划 , 经常需要对事物的进展情况做出决策, 以便用最有利的方式采取行动。由于事物的进展情况和信息往往受随机因素的影响,不能确切预料 ,决策往往带有风险。在这种情况下 ,决策者通常 有很多行动方案可以采用 ,而统计决策方法可以提供最优的行动方案 , 大大减少由于盲目地决定而导致的损失。因此 , 统计决策方法和统计决策分析将会在社会的发展和进步中发挥越来越大的作用。 在现代社会中 , 公民应该具有合理的决策能力。因此 , 在中学阶段最好能掌握一些简单的统计决策方面的知识和方法 , 形成初步的决策意识。本专题就是为此目的而设立的。 内容与要求 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 ＝ 数学建模中的图论方法 一、引言 我们知道，数学建模竞赛中有问题A和问题B。一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A题入手快，而B题不好下手。 另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。 图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如： AMCM90B－扫雪问题； AMCM91B－寻找最优Steiner树； AMCM92B－紧急修复系统的研制(最小生成树) AMCM94B－计算机传输数据的最小时间(边染色问题) CMCM93B－足球队排名(特征向量法) CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性) CMCM98B－灾情巡视路线(最优回路) 等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。 本文将从图论的角度来说明如何将一个工程问题转化为合理而且可求解的数学模型，着重介绍图论中的典型算法。这里只是一些基础、简单的介绍，目的在于了解这方面的知识和应用，拓宽大家的思路，希望起到抛砖引玉的作用，要掌握更多还需要我们进一步的学习和实践。 离散数学图论部分综合练习 一、单项选择题 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 优选法 1、 一个真实案例 某电子管厂从仓库中清出了积压多年的几百万米某 种“废”金属丝。为了使得这些废金属丝能够重新被利用，科 研人员经过研究发现，找出准确的退火温度是使该废金属丝复 活的关键。 由经验知道，退火温度的范围为，因此，试验范围 为。如果不考虑其他次要因素，则该金属丝的质量指标是温度 的函数，其中。由于目标函数的具体表达式不知道，因此，该 问题的关键在于能否通过次数尽量少的调温试验，求出满足一 定精度条件下的最佳退火温度。 （华罗庚先生70年代初期支援大西南三线建设期间的一个案例） 分析： 尽管目标函数的具体表达式不知道，但是根据经验可知：从退火温度的最低点1400开始，随着的增大，质量指标 的函数值随之增大；当达到最佳退火温度时，随着的继续增 大，一直到最高点1600，质量指标的函数值随之减少。也就是 说，是在试验区间内先增后减的单峰函数，其中只有唯一的一 个最优点。 试验方法讨论： 1、 等分法 通常的想法是：在试验区间[1400，1600]上均匀取点试验，就可 以求得满足一定精度要求的最佳退火温度。例如，若要求精度达到， 我们只要在 各点进行试验，通过比较各点的试验结果，就能找到最佳试验点。例 如，若发现是其中最好的点，就可以断定最佳退火温度必在区间（1480，1500）上。在生产实际中，就可以把1490作为最佳退火温 度。 问题：每一次试验都需要较高的成本，而上述等分法均匀取点， 试验时没有考虑已经获得的质量指标的信息，往往需要作大量试验才 能获得较好的结果。因此等分法是一种浪费的方法。 需要找到一种更节约的方法。 2、 优选法（0.618法-黄金分割法） （受到蜂巢结构的启发） 具体步骤如下： 先在试验区间的0.618处做第一次试验，第一点温度为： 第二次试验：在第一次点关于中心对称的点，即第二次的温度为 比较上面的两次结果，如果1480点较好，去掉1520（称之为“坏 点”）以上的温度。然后在[1400，1520]中找出第二试验点1480的对 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以及形成小回路的边去掉。 算法二： 算法三： 浅谈图论中邻接矩阵的应用 [摘要] 使用邻接矩阵求解有关实际问题符合数学中数形结合的思想,对于更好地理解问题,思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的,它是数学的重要分支,使今年来较为活跃的数学分支。这个问题其实也是一个数学游戏问题,是源于生活,高于生活。图论作为组合数学的一分支,与其他数学分支,如矩阵论,概率论,拓扑学数值分析都有着重要的联系。 [关键字] 邻接矩阵、算法、连通性、最小生成树 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={ 图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma) 图论部分 一、选择题： 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=图论算法详解(C++版)
图论基础
离散数学测验题--图论部分(优选.)
离散数学图论与系中有图题目
图论算法及其MATLAB程序代码
天津高中数学必修+选修全部知识点精华归纳总结
一笔画问题是图论中一个著名的问题
习题参考解答图论部分
统筹法与图论初步
图论学生论文
离散数学图论部分综合练习
数学建模中的图论方法
离散数学图论部分经典试题及答案
优选法与统筹法
经典图论问题
浅谈图论中邻接矩阵的应用
离散数学(图论部分)1-4章习题课
图论算法及matlab程序的三个案例
图论部分复习题
- 离散数学图论部分经典试题及答案
- 习题参考解答(图论部分)Word版
- 习题参考解答(图论部分)
- 图论部分(板书)
- 离散数学测验题--图论部分(优选.)
- 【免费下载】离散数学及其应用图论部分课后习题答案
- 离散数学图论部分经典试题及答案
- 电大离散数学作业5答案(图论部分)
- 图论习题一
- 第五部分图论GraphTheory教学-
- 离散数学图论部分综合练习
- 离散数学图论部分形成性考核书面作业4答案
- 离散数学图论部分经典试题及答案
- 图论部分复习题
- 离散数学图论部分经典试题及答案
- 图论部分复习题
- 离散数学——图论部分习题课
- 10秋作业4(04任务)：图论部分概念及性
- 离散数学 (图论部分)
- 习题参考解答图论部分