图论与网络分析简介
引言
图论与网络分析简介
￠图论(Graph Theory)是运筹学的一个分支，是建立和处理离散数学模型的一个重要工具，其起源最早可追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文，现已广泛应用在物理学、化学、控制论、信息论、科学管理、计算机等各个领域中。
￠网络分析（Network Analysis）作为图论的一个重要内容，已成为对各种系统进行分析、研究和管理的重要工具，包括：最小支撑树问题、最短路问题、最大流问题，以及网络计划评审与优化问题等。
￠哥尼斯堡城有一条河叫普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如下图所示。
一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到出发地。尽管试验者很多，但是都没有成功。
A B
￠为了寻找答案，1736年欧拉将这个问题抽象成下图所示的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。
￠欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。
￠图论中的图，是反映现实世界中具体事物及其相互关系的一种抽象工具，它比地图、分子结构图、电路图等更抽象。
￠图的定义：简单的说，一个图是由一些点(Vertices)及点间的连线(Edges)所组成的。点可以作为现实世界中事物的抽象，而点间的连线表示事物间的关系。
例2：有A、B、C、D四支篮球队，进行单循环比赛，比
赛情况如表1所示。试用一个图表示各队之间的胜负关系。
比赛球队获胜球队
A——B A
A——C A
A——D D
B——C B
B——D D
C——D C
表1
图2
图3
01,,k i i i v v v V
∈ 1,k j j e e E ∈ 1(,)
t t t j i i e v v -=(1,2,,)t k = ，0112,,,,,,k k
i j i j j i v e v e e v μ= 0i v k i v 01k
i i i v v v μ=
0k
i i v v =0k
i i v v =
1475678v v v v v v μ=图4
44768754
v v v v v v v μ=245768v v v v v μ=3456874v v v v v v μ=
图5
图6
22412
v v v v μ=12143
v v v v μ= 图6
经典图论问题
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 的邻接矩阵为 ??? ???? ? ????? ???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、图论的历史 图论以图为研究对象的数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论则是研究事物对象在上述表示法中具有的特征与性质的学科。 在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了。另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。 事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。 图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段： 第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)。 东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被河的分支和岛分成了四个部分，各部分通过7座桥彼此相通。如同德国其他城市的居民一样，该城的居民喜欢在星期日绕城散步。于是产生了这样一个问题：从四部分陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。这就是有名的哥尼斯堡七桥问题。 哥尼斯堡七桥问题看起来不复杂，因此立刻吸引所有人的注意，但是实际上很难解决。 瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父。 欧拉把七桥问题抽象成数学问题---一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解。Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在？Euler证明这样的回路是不存在的。 第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树
图论
3 图论 图论在计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学和经济管理等领域有着广泛的应用。但很多图论问题虽易表达，却难以求解，其中有相当多的图论问题均属NP完全问题。本章主要介绍工程实用简单图论问题的并行算法及其MPI编程实现，包括传递闭包、连通分量、最短路径和最小生成树等。 1.1 传递闭包 设A是一个含N个顶点的有向图G的布尔邻接矩阵(Boolean Adjacent Matrix)，即元素a ij=1当且仅当从顶点i到j有一条有向边。所谓A的传递闭包（Transitive Closure），记为A+，是一个N×N的布尔矩阵，其元素b ij=1当且仅当：①i=j；或②从i出发存在有向路径到j，又称为顶点i到j可达。从G的布尔邻接矩阵A求出G的传递闭包，就称为传递闭包问题。 传递闭包问题有很强的应用背景，在科学计算中广泛存在。传递闭包问题的经典解法之一就是利用布尔矩阵的乘法来求解。本节将把这一算法分别在串行和并行机上实现。 1.1.1 传递闭包串行算法 利用布尔矩阵相乘求解传递闭包问题的原理为：对于布尔矩阵(A+I)k中的任一元素b ij，b ij=1表示从i到j存在长度小于等于k的可达路径，否则，b ij=0。显然对于k=1，(A+I)1中b ij=1当且仅当从i到j路径长度为0（i=j）或为1（从i到j存在有向边）；(A+I)2中，b ij=1当且仅当从i到j路径长度小于等于2；((A+I)2) 2中，b ij=1当且仅当从i到j路径长度小于等于4，等等。因为任意两点间如果存在可达路径，长度最多为N-1，所以k≥N-1时，(A+I)k 就是所求的传递闭包A+。于是(A+I)矩阵的㏒N次自乘之后所得的矩阵就是所求的传递闭包。 根据前面的叙述，很自然的有下面的传递闭包串行算法15.1，其时间复杂度为O(N3㏒N)。 算法15.1传递闭包串行算法 输入：图G的布尔邻接矩阵A 输出：A的传递闭包M procedure closure Begin (1)读入矩阵A /* 以下作A = A+I的运算*/ (2)for i=0 to N-1 do a(i, i) = 1 endfor /* 以下是A矩阵的㏒N次自乘，结果放入M矩阵；每次乘后，结果写回A矩阵*/ (3)for k=1 to㏒N do (3.1)for i=0 to N-1 do for j=0 to N-1 do s=0
图论-网络流
网络流网络流
1532Drainage Ditches Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9885 Accepted Submission(s): 4695 Problem Description Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch. Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network. Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle. Input The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch. Output For each case, output a single integer, the maximum rate at which water may emptied from the pond.
信息技术-信息技术网络分析与网络计划 62页 精品
第六章网络分析与网络计划 网络分析是图论的一个应用分支．它主要是应用图论的理论与方法来解决具有网络性质的管理决策问题．在现实生活和生产实践中，网络分析方法有很广泛的应用．如在企业管理中，如何制订管理计划或设备购置计划，使收益最大或费用最小；在组织生产中，如何使各工序衔接好，使生产任务完成得既快又好；在交通网络中，如何使调运的物资数量多且费用最小等．由于网络分析具有图形直观，方法简便，容易掌握的特点，因此得到迅速的发展，且广泛地应用在各个领域，成为经济活动中许多管理决策的优化问题的重要手段． 网络计划方法是上世纪50年代发展起来的计划控制技术，主要包括计划评审技术(programme evaluation and review technique，简称PERT)和关键路径方法(critical path method或critical path analysis，简称CPM、CPA)．网络计划方法特别适用于现代管理中的多因素多环节的复杂计划的优化控制，成为管理运筹学的重要应用分支． 本章在引入有关图的一些基本概念的基础上，介绍最小生成树、网络最短路、最大流、最小费用最大流等网络分析模型及其解法；并对网络计划图（统筹图）的制作、作业时间参数计算、关键线路方法和计划评审技术等网络计划基本技术和方法进行初步介绍． 第一节图的基本概念 一、图 现实世界中有许多具体事物及关系可以用图形来抽象表示．例如，路线关系、工序安排、区位规划等都可以用图来表达． 我们先通过几个直观的例子，来认识什么是图． 例6-1 歌尼斯堡七桥问题 哥尼斯堡(Konigsbergs)城域有一个普雷格尔河系，由新河、旧河及其交汇 而成的大河组成，它把该城分成了一岛三岸共四块陆地，陆地之间有七座桥连通，如图6-1(a)所示．当时城内居民在散步时热衷于这样一个问题：从某陆
运筹学图论问题
工商管理中的运筹学问题—建模及求解 项目报告 姓名： 课题组的分工或贡献： 课程名称：运筹学 指导教师： 2019年6月
前言 工商管理中的运筹学问题—建模及求解项目报告主要内容为（1）运输问题建模与管理运筹学软件求解及分析；（2）目标规划问题建模与管理运筹学软件求解及分析；（3）整数规划问题建模与管理运筹学软件求解及分析；（4）图论问题与管理运筹学软件求解及分析。范围为运筹学第五版教程中的线性规划、运输问题、目标规划、整数规划和图论等章节。本次项目的实施旨在更好的了解运筹学的理论，学会将运筹学的各种方法应用到实际问题中去，做到学以致用。
4.1研究内容 图论最吸引人的特色是它蕴含着大量有趣的思想、漂亮的图形和巧妙的方法，使非常困难的问题也易于表达。最短路问题是图与网络知识中的经典问题之一，生活中如选址、石油运输管道铺设时的选线、设备更新等问题，都可以归结为最短路问题。此外，图论问题中还包括最大流问题和网络计划问题等。 4.2问题描述 石油管道铺设最优方案的选择问题: 如下图所示，其中v1为出发点，v10为目的地，v2、v3、v4、v5、v6、v7、v8、v9分别为可供选择的各站站点，图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道线路才使总费用最小? 图中各点之间的距离如下: ( 1) V1—V2：3、V1—V3∶5、V1—V4∶4; ( 2) V2—V5∶6、V2—V6∶3、V2—V7∶5、V3—V5∶3、V3-V6∶2、V3-V7∶4、V4-V5∶4、V4— V6∶1、V4—V7∶5； ( 3) V5—V8∶2、V5—V9∶5、V6—V8∶7、V6— V9∶4、V7—V8∶5、V7—V9∶4； ( 4) V8—V10∶3、V9—V10∶4. 4.3求解步骤（Dijkstra 算法） 4.3.1.给v s以P标号，P(v s)=0，其余各点均给T标号，T（v s）=+∞。 4.3.2.若v i点为刚得到P标号的点，考虑这样的点v j:(v i，v j)属于E，且v j为T标号点。 对v j的T标号点进行以下的修改：T（v j）=min[T（v j）,P（v j）+l ij]. 4.3.3.比较所有具有T标号的点，把最小的改为P标号，即P（v i'）=min[T（v i）]， 当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号则停止。否则 用v i'代替v i转回4.3.2。
图论最短路径选址问题
姓名：学号：专业：
图论的实际应用——蔬菜批发市场选址问题 摘要：在现实生活和生产实践中，有许多管理、组织与计划中的优化问题，都可借助图论知识得以解决，而最短路问题是利用图论解决的一个典型的实际问题。图论中最典型的两种求最短路径的算法分别为Dijkstra算法和Floyd算法，其中Floyd算法广泛应用于求任意两点间的最短路径。本文介绍了利于Floyd算法来解决城市蔬菜批发市场选址的问题。 关键词：最短路；Floyd算法；选址问题 0．引言 对于许多地理问题，当它们被抽象为图论意义下的网络图时，问题的核心就变成了网络图上的优化计算问题。其中，最为常见的是关于路径和顶点的优选计算问题[5]。在路径的优选计算问题中，最常见的是最短路径问题，最短路径可能是给定两点间的最短路径，也可能是任意各点间的最短路径。而在顶点的优选计算问题中，最为常见的是选址问题，所谓选址问题就是在某一地理区域构成的网络中选择一个顶点，建立服务设施，为该网络中的各个点提供服务，使得服务效率最高[3]。 选址问题，在规划建设中经常可以碰到，这里所谓的服务设施，可以是某些公共服务设施，如医院，消防站，物流中心等。也可以是生产服务设施，如仓库，转运站等等。可以认为，选址问题，就是把服务设施与服务对象，反映与统一的网络中，便于对问题进行研究[4]。尽管对选址的目标、要求有不同的评判标准，但是要求服务对象与服务设施之间易于沟通、易于达到，这是一个最基本的要求。1．最短路径问题 最短路径问题是图论研究的一个经典算法问题，其目的是求出给定两点之间的长最短的路径，这里所说的长具有广泛意义，即可指普通意义的距离，也可是时间或费用等[2]。因此，最短路径问题通常可以归纳为三类：(1)距离意义上的最短路径，即求两点间距离最短的路径；(2)经济意义上的最短路径，即为两点间的费用最少的路径；(3)时间意义上的最短路径，即选择两点间最节省时间的
图论解决渡河问题
图论解决渡河问题 农夫，狼，羊，草渡河问题，是一道很经典的问题。讲述的是农夫，狼，羊，草渡河，但只有一艘船，而且每次渡河农夫都只能带一个上船。同时，在农夫不在的情况下，狼与羊不能在一起，羊与草不能在一起。求要用怎样方式渡河，才能保证农夫不受到任何损失。 一、将实际问题转换成数学问题 每次渡河，必然是由一个渡河的状态转变成为另一个状态，在每个状态之间都有渡河的可能。由此，可以作出一幅有向图。并且，会有一个起点与终点，由起点到终点之间的连线，就能找出一个合适的渡河方法。 二、数学问题的实现 1、列出所有岸边状态： 由于只要知道任意的一岸的情况，便能推导出当前的渡河状态，所以只列出起始岸边的情况。 起始岸边人狼羊草 V0 1 1 1 1 V1 1 1 1 0 V2 1 1 0 1 V3 1 0 1 1 V4 1 0 1 0 V5 0 1 0 1 V6 0 1 0 0 V7 0 0 1 0 V8 0 0 0 1 V9 0 0 0 0 图0 因为条件的限制，所以起始岸边只存在这十种情况。其中V0为起始状态，V9为渡河结束。其中，当人的状态为1时，表示的在起始岸，0则为对岸。 2、列出所有渡河状态： 因为每次渡河必须要有人的存在，所以所有的渡河情况为： 人狼羊草 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 图1
3、生成有向图的邻接矩阵： 从图0和图1，可以生成一个渡河的有向图。 已知从起始岸到对岸必定是2个成员渡河，而起始岸到对岸则可以单独一人，或者两个成员。 生成的有向图的邻接矩阵如下： V0 V1 V2 V3 V4 V5 V6 V7 V8 V9 V0 0 0 0 0 0 1 0 0 0 0 V1 0 0 0 0 0 0 1 1 0 0 V2 0 0 0 0 0 1 1 0 1 0 V3 0 0 0 0 0 0 0 1 1 0 V4 0 0 0 0 0 0 0 1 0 1 V5 1 0 1 0 0 0 0 0 0 0 V6 0 1 1 0 0 0 0 0 0 0 V7 0 1 0 1 1 0 0 0 0 0 V8 0 0 1 1 0 0 0 0 0 0 V9 0 0 0 0 1 0 0 0 0 0 图3 4、从邻接矩阵中找出渡河路径： 先将通过的点列入路径的集合里，已知起始位置为V0，则通过路径的集合为{V0}，下一状态则为V5，集合变为{V0，V5}。再从V5开始寻找下一状态，当遇到路径集合里有的点后，跳过寻找下一个点，如果不存在下一点路径则将此元素去除路径集合，重新在上一状态寻找。 直到找到V9为止。 路径寻找状态如下表 路径集合是否存在下一点路径 V0 1 V0,V5 1 V0,V5,V2 1 V0,V5,V2,V6 1 V0,V5,V2,V6,V1 1 V0,V5,V2,V6,V1,V7 1 V0,V5,V2,V6,V1,V7,V3 1 V0,V5,V2,V6,V1,V7,V3,V8 0 V0,V5,V2,V8,V3,V7,V3 0 V0,V5,V2,V8,V3,V7,V4 1 V0,V5,V2,V8,V3,V7,V4,V9 图 4
网络流基本概念
对于交通网、管道网，都有物质流动的问题，在交通网中，有人、车辆的流动；在管道网中有流体（水、油等）的流动等等。这种网络中的物质流动称为网络流。 下面介绍与网络流有关的一些基本概念。 （1）流量：表示某时间内通过弧（j i v v ）的物质数量，记为ij f ，他是网络流问题中待求解的变量。网络中的总流量用v(f)表示。 （2）容量：弧的最大允许流通量，一般用ij c 表示。 （3）可行流：在实际的网络中，网络流应满足下面两个条件： 1) 容量限制条件：对于没一个弧{j i v v }∈A ，A 为弧集来说，ij c f ≤≤ij 0。即通过每条弧 的流量不能超过该弧的容量。 2) 平衡条件：对于始点s v ，流入始点的流量等于网络中的总流量，即 ()f v f f A v v js A v v sj s j j s =-∑∑∈∈)()( 对于终点t v ，流出终点的流量等于网络中的总流量，即 ()f v f f A v v jt A v v tj t j j t -=-∑∑∈∈)()( 对于仍以中间的顶点()t s i i ,≠，流进某中间顶点的流量等于流出盖顶点的流量。即 0)()(=-∑∑∈∈A v v ji A v v ij i j j i f f 在网络分析中，满足上面两个条件的流动，称为可行流。 （4）零弧与非零弧：满足 的弧称为零弧。由于 ，所以弧的流量不能减小；满足 的弧称为非零弧。弧的流量可以被减小，但要满足 0。 （5）饱和弧和非饱和弧：网络中流量等于容量（即ij f =ij c ）的弧称为饱和弧。流量小于容量（即ij f
图论基础知识汇总(适合建模)
图与网络模型及方法 §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22 n n H C 的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决 这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 图与网络是运筹学（Operations Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP －shortest path problem ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两
经典逻辑思维问题及答案
经典逻辑思维问题及答案 第一组 .烧一根不均匀的绳，从头烧到尾总共需要个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢? .你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻? .如果你有无穷多的水，一个公升的提捅，一个公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出公升的水? .一个岔路口分别通向诚实国和说谎国。来了两个人，已知一个是诚实国的，另一个是说谎国的。诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。请问应该怎么问? 个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。个呢?(注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑) .在个点上画条直线，要求每条直线上至少有三个点? .在一天的小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次?都分别是什么时间?你怎样算出来的? .怎么样种植棵树木，使其中任意两棵树的距离相等? 第二组 .为什么下水道的盖子是圆的? .中国有多少辆汽车? .将汽车钥匙插入车门，向哪个方向旋转就可以打开车锁? .如果你要去掉中国的个省(含自治区、直辖市和港澳特区及台湾省)中的任何一个，你会去掉哪一个，为什么? .多少个加油站才能满足中国的所有汽车? .想象你站在镜子前，请问，为什么镜子中的影象可以颠倒左右，却不能颠倒上下? .为什么在任何旅馆里，你打开热水，热水都会瞬间倾泻而出?
.你怎样将的用法解释给你的奶奶听? .你怎样重新改进和设计一个银行自动取款机? .如果你不得不重新学习一种新的计算机语言，你打算怎样着手来开始? .如果你的生涯规划中打算在年内受到奖励，那获取该项奖励的动机是什么?观众是谁? .如果微软告诉你，我们打算投资五百万美元来启动你的投资计划，你将开始什么样商业计划?为什么? . . . . . . . . 第一题 . 五个海盗抢到了颗宝石，每一颗都一样大小和价值连城。他们决定这么分：抽签决定自己的号码(、、、、) 首先，由号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔进大海喂鲨鱼如果号死后，再由号提出分配方案，然后剩下的人进行表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼依此类推条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化?
§2-1网络图论的基本概念
§2-1 网络图论的基本概念 对于一个电路图，如果用点表示其节点，用线段表示其支路，得到一个由点和线段组成的图，这个图被称为对应电路图的拓扑图，通常用符号G 表示。例如：图2-1-1（a ）所示电路，其对应的拓扑图如图2-1-1 (b) 所示。 拓扑图是线段和点组成的集合，它反映了对应的电路图中的支路数、节点数以及各支路与节点之间相互连接的信息。 在拓扑图中，如果任意两点之间至少有一条连通的途径，那么这样的图称为连通图，例如图2-1-1（b ）所示的图，否则称为非连通图，例如图2-1-2（b ）所示的图。如果图G 1中所有的线段与点均是图G 中的全部或部分线段与点，且线段与点的连接关系与图G 中的一致，那么图G 1称为图G 的子图。例如图2-1-3（b ）（c ）（d ）（e ）均是图2-1-3（a ）的子图。 图 2-1-1 图2-1-2 图2-1-3
下面介绍网络图论中非常重要的一个概念——树。树是连通图G 的一个特殊子图，必须同时满足以下三个条件： （1）子图本身是连通的； （2）包括连通图G 所有节点； （3）不包含任意回路。 组成树的支路称为树支，不包含在树上的支路称为连支（或链支）。如果用t n 表示树支的数目，则： 1t n n =- （式2-1-1） 连支的数目l 等于支路数b 减去树支的数目，即 1l b n =-+ （式2-1-2） 如果将一个电路铺在一个平面上，除节点之外再没有其他交点，这样的电路被称为平面电路，否则，称为非平面电路。 在平面电路中，内部没有任何支路的回路称为网孔。它是一种特殊的回路。 一个有b 条支路、n 个节点的连通平面图的网孔数m 为： 1m b n =-+ （式2-1-3） 接下来介绍割集的概念。割集是连通图G 的一个子图，它满足以下两个条件： （1）移去该子图的全部支路，连通图G 将被分为两个独立部分； （2）当少移去该子图中任一条支路时，则图仍然保持连通。 一个具有n 个节点的连通图，有（n-1）条树，有（n-1）个单树支割集。 (a) (b) 图2-1-7
图论与强连通网络流-练习题
一般图论与连通性-练习题 Problem A. 老乡 问题描述 “老乡见老乡两眼泪汪汪，问一问老乡你过得怎么样？心情好不好啊做工忙不忙？其实我和你一样夜夜梦故乡。 老乡见老乡两眼泪汪汪，问一问老乡你又要去何方？吃过多少苦啊受过几回伤？其实我和你一样总想闯一闯。 他乡的话你你你会不会讲，他乡的歌你你你爱不爱唱？习不习惯飘泊的生活，想不想念自己的家乡？他乡的话你你你会不会讲，他乡的歌你你你爱不爱唱？有没有钱寄给你爹娘，想没想过何时回故乡？……” 《老乡》唱出了很多20世纪九十年代打工创业者的心声，歌曲一经发行，便传遍大江南北。 其实，老乡的范围可大可小。比如在省里看到同一县的人，在市里看到同一区的人，在全国看到同一省的人，都可以算做老乡。在农村或小县城的日常口语中，老乡一般也能用作关系亲密的兄弟之间的一种称呼。 现在给定称作老乡的若干人员对，请您做出判断给定任何两人是否是老乡。 输入 有若干组测试数据。每组测试数据的第一行是2个整数n，q (0 ≤ n ≤ 10000，q<10) ，即是老乡的人数对。接下来有n行，每行是一个用空格隔开的数对A 和B，表示A和B是老乡，(A ≠ B, 1 ≤ A, B ≤ 100000) 。接下来有q行，每行有两个整数x和y。 两组数据之间有一个空行。 输出 对每组测试数据，先输出“Case #”，换行，其中#是测试数据序号（从1开始）。接着对q组整数x和y，一行输出x与y是否是老乡的结论：如是，则输出“YES”，否则输出“NO”。 输入样例 4 2 1 2 3 4
5 6 1 6 1 4 1 5 4 2 1 2 3 4 5 6 7 8 1 4 1 5 输出样例Case 1 NO YES Case 2 NO NO Case 3 NO YES
图论总结(超强大)
1.图论Graph Theory 1.1.定义与术语Definition and Glossary 1.1.1.图与网络Graph and Network 1.1. 2.图的术语Glossary of Graph 1.1.3.路径与回路Path and Cycle 1.1.4.连通性Connectivity 1.1.5.图论中特殊的集合Sets in graph 1.1.6.匹配Matching 1.1.7.树Tree 1.1.8.组合优化Combinatorial optimization 1.2.图的表示Expressions of graph 1.2.1.邻接矩阵Adjacency matrix 1.2.2.关联矩阵Incidence matrix 1.2.3.邻接表Adjacency list 1.2.4.弧表Arc list 1.2.5.星形表示Star 1.3.图的遍历Traveling in graph 1.3.1.深度优先搜索Depth first search (DFS) 1.3.1.1.概念 1.3.1. 2.求无向连通图中的桥Finding bridges in undirected graph 1.3. 2.广度优先搜索Breadth first search (BFS) 1.4.拓扑排序Topological sort 1.5.路径与回路Paths and circuits 1.5.1.欧拉路径或回路Eulerian path 1.5.1.1.无向图 1.5.1. 2.有向图 1.5.1.3.混合图 1.5.1.4.无权图Unweighted 1.5.1.5.有权图Weighed —中国邮路问题The Chinese post problem 1.5. 2.Hamiltonian Cycle 哈氏路径与回路 1.5. 2.1.无权图Unweighted 1.5. 2.2.有权图Weighed —旅行商问题The travelling salesman problem 1.6.网络优化Network optimization 1.6.1.最小生成树Minimum spanning trees 1.6.1.1.基本算法Basic algorithms 1.6.1.1.1.Prim 1.6.1.1. 2.Kruskal 1.6.1.1.3.Sollin（Boruvka） 1.6.1. 2.扩展模型Extended models 1.6.1. 2.1.度限制生成树Minimum degree-bounded spanning trees 1.6.1. 2.2.k小生成树The k minimum spanning tree problem(k-MST) 1.6. 2.最短路Shortest paths 1.6. 2.1.单源最短路Single-source shortest paths 1.6. 2.1.1.基本算法Basic algorithms
经典图论问题
5经典图论问题 一笔画问题 中国邮递员问题（CPP）
规划模型： 设ij x 为经过边j i v v 的次数，则得如下模型。 ∑E ∈j i v v ij ij x w max ∑∑ 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 5.3 旅行推销员问题（TSP ） 分析： ..t s
算法一：象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。 算法二： 算法三：
规划模型： 先将一般加权连通图转化成一个等价的加权完全图，设当从i v 到j v 时，1=ij x ，否则， 0=ij x ，则得如下模型。 ∑∑==n i n j ij ij x w 11 min ∑===n j ij n i x 1 ,,1,1Λ ∑===n i ij n j x 1 ,,1,1Λ 1,,2-=n k Λ n i i k x x x k i i i i i i k ΛΛΛ1,,,1113221=-≤+++ 0=ij x 或1，j i n j i ≠=,,,1,Λ 排课表问题 问题一 定理：最小边色数()G χ'等于最大顶点度数()G ?。 以下加边循环算法为多项式时间算法：就是加边让每个顶点的度数一样（为最大度数），然后求一组完美匹配M ，着同样颜色，然后从图中去掉M 中的边,再求第二组完美匹配。。。。。。。。 ..t s
问题二：
基本思想是：由给定的教室数与总课时数确定教学时间长度（即匹配数--色数），在没有考虑教室数限制所计算的匹配数基础上，增加空匹配至时间长度个，然后调节匹配边差大于1的匹配，直到满足要求。
图论里面的重要概念(一)
1、支配集： 设D集合是无向图G的一个顶点子集，对于G中的任意顶点u，要么在D里，要么与D集合的一个顶点相邻，那么称我们集合D的G的一个支配集。如果去掉D中任何一个顶点，D不在是支配集，则支配集是极小支配集。G中所有支配集中顶点个数最小的支配集称为最小支配集，即是极小支配集。最小支配集的顶点个数为支配数。 2、独立集： 设I集合无向图G的一个顶点子集，对于集合I中任意两点都不相邻，则我们称集合I为G 的一个独立集。如果在I中加入一个非I集合的顶点后，I集合不在是独立集，则称集合I 为极大独立集。G中所有独立集中顶点个数最多的独立集称为最大独立集，即是极大独立集。最大独立集的顶点个数为独立数。 3、覆盖集： 设K集合是无向图G的一个顶点子集，对于G中的任意一条边e，至少有一个端点属于K，那么我们称集合K是G的一个覆盖集。如果去掉K中的任意一个顶点，K不在是覆盖集，则称集合K是极小覆盖集。在G中所有覆盖集中顶点个数最少的覆盖集称为最小覆盖集。即是极大覆盖集。最小覆盖集的顶点个数为覆盖数。 4、网络流： a、网络与流： 网络D=(V,A,C） 设D是一个简单有向图，V是顶点集，A是边集，C弧容量集。 网络流F F(i,j)=集合A上的一个函数，为弧(vi,vj)的流量。 b、可行流与最大流： 可行流 （1）容量限制 对于每条弧(vi,vj)属于A，则0<=|F(i,j)|<=c(i,j)。 （2）平衡条件 对于V里的每个顶点i!=s,t;(源点和汇点) 都有流入量=流出量 对顶点s的流出量-s的流入量=-1*（顶点t的流出量-t的流入量） 最大流 求最大流问题即是求顶点s的流出量-流入量的最大值或者求顶点t的流出量-流入量的最小值。 c、可改进路P 如果|F(i,j)|=C(i,j)，称该弧为饱和弧 如果|F(i,j)|
相关文档
- 图论和网络分析算法及Matlab实现(Graph and Network Analysis)
- 图论、社会网络分析与复杂网络理论
- 图论和网络分析算法与Matlab实现(Graph_and_Network_Analysis)
- 运筹学图与网络分析课件
- 图论基础与网络流习题集锦
- 运筹学_3 网络分析_31 图论与网络分析简介_
- 图论与网络分析
- 运筹学——.图与网络分析-最短路.
- 第七章 图论与网络分析
- 图论和网络分析算法及Matlab实现(Graph_and_Network_Analysis)
- 图论和网络分析
- 图与网络分析 (Graph Theory and Network Analysis)
- 图论和网络分析算法及Matlab实现(Graph_and_Network_Analysis)
- 信息技术-信息技术网络分析与网络计划 62页 精品
- 图论和网络分析算法及Matlab实现GraphandNetworkAnalysis
- 图与网络分析
- 图论和网络分析算法及Matlab实现(Graph and Network Analysis)
- 图论和网络分析算法及Matlab实现(Graph and Network Analysis)
- 图论与网络分析简介
- 图论和网络分析算法及Matlab实现(Graph_and_Network_Analysis)资料