图的谱极值问题研究
图谱理论是图论中的一个重要研究领域,它在物理学、化学、生物学、计算机科学等诸多领域都有极重要的应用.谱极值问题是近年来图谱理论研究的热点,其核心内容是研究图的特征值的极值以及对应的极图.本文主要围绕图的谱极值问题进行了研究.基于图的拉普拉斯矩阵、距离拉普拉斯矩阵和A_α-矩阵,讨论了相关特征值的极值问题,主要内容如下:·考虑了图的代数连通度.对Fiedler 向量在特殊的图结构中的分量性质进行了研究.以Fiedler向量为工具,刻画了周长给定的图中代数连通度达到最小的所有极图.同时,对于周长给定的图中代数连通度的极大值也进行了讨论.·讨论了图的拉普拉斯谱半径与分数匹配数.首先利用商矩阵的方法,建立了图的分数匹配数与拉普拉斯谱半径的联系,并由此得到了拉普拉斯谱半径的一个可达的下界,同时也对极图进行了刻画.最后,给出了图中含有分数完美匹配的一些谱条件.·研究了连通图的距离拉普拉斯谱半径.首先基于图的距离拉普拉斯谱半径,考虑了图的几类移接变形,进而确定了单圈图中距离拉普拉斯谱半径达到最大的极图,该结论也解决了Aouchiche和Hansen所提出的猜想.最后,利用图的最大传递指标和团数给出了图的距离拉普拉斯谱半径的下界.·讨论了图的A_α-特征值的极值.首先基于图的A_α-谱半径,给出了图的几类移接变形,同时证明了Nikiforov和Rojo所提出的两个猜想.利用这些移接变形,刻画了直径给定的图中A_α-谱半径达到最大的极图,以及
团数给定的图中A_α-谱半径达到最小的极图.对于α>1/2的情形,得到了图的第k大A_α-特征值的上界.
运筹学（yùnchóuxué）简介 英语全称为：Operational?Research(英国)或者是Operations?Research(美国) 在中国战国时期，曾经有过一次流传后世的赛马比赛，相信大家都知道，这就是田忌赛马。田忌赛马的故事说明在已有的条件下，经过筹划、安排，选择一个最好的方案，就会取得最好的效果。可见，筹划安排是十分重要的。 现在普遍认为，运筹学是近代应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用数学方法进行解决。前者提供模型，后者提供理论和方法。 运筹学的思想在古代就已经产生了。敌我双方交战，要克敌制胜就要在了解双方情况的基础上，做出最优的对付敌人的方法，这就是“运筹帷幄之中，决胜千里之外”的说法。 但是作为一门数学学科，用纯数学的方法来解决最优方法的选择安排，却是晚多了。也可以说，运筹学是在二十世纪四十年代才开始兴起的一门分支。 运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。当然，随着客观实际的发展，运筹学的许多内容不但研究经济和军事活动，有些已经深入到日常生活当中去了。运筹学可以根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，已达到最好的效果。 运筹学作为一门用来解决实际问题的学科，在处理千差万别的各种问题时，一般有以下几个步骤：确定目标、制定方案、建立模型、制定解法。 虽然不大可能存在能处理及其广泛对象的运筹学，但是在运筹学的发展过程中还是形成了某些抽象模型，并能应用解决较广泛的实际问题。 随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重要的作用。运筹学本身也在不断发展，现在已经是一个包括好几个分支的数学部门了。比如：数学规划（又包含线性规划；非线性规划；整数规划；组合规划等）、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、对策论、搜索论、模拟等等。 运筹学有广阔的应用领域，它已渗透到诸如服务、库存、搜索、人口、对抗、控制、时间表、资源分配、厂址定位、能源、设计、生产、可靠性、等各个方面。 运筹学是软科学中“硬度”较大的一门学科，兼有逻辑的数学和数学的逻辑的性质，是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具。运筹学已被应用到各种管理工程中，在现代化建设中发挥着重要作用。 [编辑本段]运筹学的历史 运筹学作为一门现代科学，是在第二次世界大战期间首先在英美两国发展起来的，有的学者把运筹学描述为就组织系统的各种经营作出决策的科学手段。?P.M.Morse与G.E.Kimball在他们的奠基作中给运筹学下的定义是：“运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。”运筹学的另一位创始人定义运筹学是：“管理系统的人为了获得关于系统运行的最优解而必须使用的一种科学方法。”它使用许多数学工具（包括概率统计、数理分析、线性代数等）和逻辑判断方法，来研究系统中人、财、物的组织管理、筹划调度等问题，以期发挥最大效益。 现代运筹学的起源可以追溯到几十年前，在某些组织的管理中最先试用科学手段的时候。可是，现在普遍认为，运筹学的活动是从二次世界大战初期的军事任务开始的。当时迫切需要把各项稀少的资源以有效的方式分配给各种不同的军事经营及在每一经营内的各项活动，所以美国及随后美国的军事管理当局都号召大批科学家运用科学手段来处理战略与战术问题，实际上这便是要求他们对种种（军事）经营进行研究，这些科学家小组正是最早的运筹小组。 第二次世界大战期间，“OR”成功地解决了许多重要作战问题，显示了科学的巨大物质威力，为“OR”后来的发展铺平了道路。
最大流算法 clc,clear,M=1000; c(1,2)=3;c(1,4)=3; c(2,3)=1;c(2,4)=20; c(3,6)=3; c(4,5)=10; c(5,1)=4;c(5,3)=2;c(5,6)=13; n=length(u); list=[]; maxf=zeros(1:n);maxf(n)=1; while maxf(n)>0 maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=M; while (~isempty(list))&(maxf(n)==0) flag=list(1);list(1)=[]; index1=(find(u(flag,:)~=0)); label1=index1(find(u(flag,index1)... -f(flag,index1)~=0)); label1=setdiff(label1,record); list=union(list,label1); pred(label1(find(pred(label1)==0)))=flag; maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1)); record=union(record,label1); label2=find(f(:,flag)~=0); label2=label2'; label2=setdiff(label2,record); list=union(list,label2); pred(label2(find(pred(label2)==0)))=-flag; maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2); end if maxf(n)>0 v2=n; v1=pred(v2); while v2~=1 if v1>0
第5章 运筹学模型 5.2 图论模型 图论是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。由于这种数学模型和方法直观形象，富有启发性和趣味性，深受人们的青睐。到目前为止，已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。传统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。本章将在介绍图的一些基本概念的基础上，着重介绍最小生成树、最短路、最大流及最小费用最大流问题。 5.2.1 图的基本概念 城市之间的交通关系，家族成员之间的关系，工厂、企业、事业单位内部，部门之间的上下关系，工程中各个工序之间的先后关系等等，用图形来描述往往是很有益的。图论是研究某种特定关系的一门学问。 1.图 图 (graph) 由若干个点 (称作顶点，vertex) 和若干条连接两两顶点的线段（称edge ）组成。通常，顶点可用来表示某一事物，边用来表示这些事之间的某种关系。如图5-1中的五个顶点可以代表五个城市。如果两个顶点之间有一条边连接，就表示这两个城市之间有一条铁路。同样，它也可以代表五个人。如果两个人认识，则用一条边把这两个顶点连接 起来。 图5-1 由于图是用来表示某些事物之间的联系，因而在画图时，顶点位置，边的长短、曲直是无关紧要的。只要两个图的顶点可以一一对应，并且 使得对应的顶点之间是否有边相连完全相同，就可以认为是同一个图。例如：图5-1也可以画成图5-2的形式。 图 5-2 设图的顶点集合V ={n v v v ,...,, 21}, 边的集合 E ={m e e e , ... ,,21} 把图记作 ) , (E V G =。这里大括号 { } 内的元素是没有顺序的，而小括号（ ）内的元素是有顺序 的。如果边e 连接顶点u 和v ，则记作e = {v u ,}。u 和v 称作e 的端点，e 称作u 和v 的关联边。如果u 和v 之间有一条边，即{v u ,}∈E ，则称u 和v 相邻。如果两条边有一个共同的端点，则称这两条边相邻。没有关联边的顶点称作孤立点。两个顶点之间可以有不止一条
最大流问题 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。 网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。 基本概念 设一个赋权有向图D=(V , A)，在V 中指定一个发点（源）vs 和一个收点（汇）vt ，且只能有一个发点vs 和一个收点vt 。（即D 中与vs 相关联的弧只能以 vs 为起点，与vt 相关联的弧只能以 vt 为终点），其他的点叫做中间点。 对于D 中的每一个弧(vi, vj)A ∈，都有一个权cij 叫做弧的容量。我们把这样的图 D 叫做一个网络系统，简称网络，记做D =(V , A, C) 。 Vs Vt 图1 图1是一个网络。每一个弧旁边的权就是对应的容量。 网络D 上的流，是指定义在弧集合A 上的一个函数f={f(vi, vj)}={fij}，f(vi,vj)=fij 叫做弧在(vi,vj)上的流量 。 Vs Vt 图2 图2中，每条弧上都有流量fij ，例如fs1=5，fs2=3，f13=2等。 容量是最大通过能力，流量是单位时间的实际通过量。显然，0≤fij≤cij 。网络系统上流的特点： (1)发点的总流出量和收点的总流入量必相等； (2)每一个中间点的流入量与流出量的代数和等于零； (3)每一个弧上的流量不能超过它的最大通过能力（即容量）。网络上的一个流f={fij}叫做可行流，如果f 满足以下条件： （1）容量条件：对于每一个弧(vi,vj)A ∈，有0≤fij≤cij 。
（2）平衡条件： 对于发点vs ，有∑f sj ?∑f js =v (f ) 对于收点vt ，有∑f tj ?∑f jt =?v (f ) 对于中间点，有∑f ij ?∑f ji =0 其中发点的总流量（或收点的总流量）v(f)叫做这个可行流的流量。 网络系统中最大流问题就是，在给定的网络上寻求一个可行流f={fij}，其流量v(f)达到最大值，即从vs 到vt 的通过量最大。 最大流问题可以通过线性规划数学模型来求解。图1的最大流问题的线性规划数学模型为 max v =f s 1+f s 2 s.t. { ∑j f ij ?∑i f ij =0 i ≠s,t 0≤f ij ≤c ij 所有弧(v i ,v j ) fs1和fs2是与起点相连的两条弧上的流量。 满足上式的约束条件的解{fij}称为可行解，在最大流问题中称为可行流。 对有多个发点和多个收点的网络，可以另外虚设一个总发点和一个总收点，并将其分别 与各发点、收点连起来，就可以转换为只含一个发点和一个收点的网络。 S T 所以一般只研究具有一个发点和一个收点的网络。 我们把fij=cij 的弧叫做饱和弧，fij
题目：最小生成树在城市交通建设中的应用 姓名： 学号： 指导老师： 专业：机械工程 2014年3月16
目录 摘要..................................................................................... 错误！未定义书签。 1 绪论 (1) 2 有关最小生成树的概念 (2) 3 prim算法介绍 (3) 4 系统设计及其应用 (5) 一、系统设计 (5) 二、最小生成树应用 (8) 5 总结 (11) 参考文献 (12) 附件： (13)
最小生成树在城市交通建设中的应用 摘要：连通图广泛应用于交通建设，求连通图的最小生成树是最主要的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。 求图的最小生成树有两种算法，一种是Prim（普里姆）算法，另一种是Kruskal（克鲁斯卡尔）算法。 本文通过将城市各地点转换成连通图，再将连通图转换成邻接矩阵。在Microsoft Visual C++上，通过输入结点和权值，用普里姆算法获得权值最小边来得到最小生成树，从而在保证各个地点之间能连通的情况下节省所需费用。 本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。 关键字：PRIM算法、最小生成树、邻接矩阵、交通建设
Abstract Connected graph is widely applied in traffic construction, connected graph of minimum spanning tree is the main application.Such as to establish a communication network between the n city, want to consider is how to ensure n points connected under the premise of the most save money, apply to the minimum spanning tree. O figure there are two kinds of minimum spanning tree algorithm, one kind is Prim (she) algorithm, the other is a Kruskal algorithm (Kruskal). In this article, through the city around point into a connected graph, then connected graph is transformed into adjacency matrix.On Microsoft Visual c + +, through the input nodes and the weights, gain weight minimum edge using she algorithm to get minimum spanning tree, which in the case of guarantee every location between connected to save costs. Based on the analysis topic subject background, significance, subject requirements, etc, from requirements analysis, general design, detailed design, testing, and other aspects detailed introduces the system design and implementation process, finally the completion of the system are summarized. Key words: PRIM algorithm, minimum spanning tree, adjacency matrix, traffic construction
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 1.6. 2.1.1.1.Dijkstra 1.6. 2.1.1.2.Bellman-Ford 1.6. 2.1.1.2.1.Shortest path faster algorithm(SPFA) 1.6. 2.1.2.应用Applications 1.6. 2.1.2.1.差分约束系统System of difference constraints 1.6. 2.1.2.2.有向无环图上的最短路Shortest paths in DAG 1.6. 2.2.所有顶点对间最短路All-pairs shortest paths 1.6. 2.2.1.基本算法Basic algorithms 1.6. 2.2.1.1.Floyd-Warshall 1.6. 2.2.1.2.Johnson
数学科学学院 课程名称图论导引 题目图论在交叉学科中的应用姓名闫二路 学号 A01014134 专业数学与应用数学 授课老师汪毅
图论在交叉学科中的应用 [摘要]利用图论知识可以解决一些交叉学科中的实际问题。对于更好地理解问题，思考问题从而求解问题具有现实意义。图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支，它是源于生活，高于生活。图论作为组合数学的一分支，与其他数学分支，如信息论，矩阵论都有着重要的联系。 [关键字] 树、即时码、hamilton圈、Hamilton路 1．即时码的树图构造法 即时码定义：在唯一可译变长码中，有一类码，它在译码时无须参考后续的码符号就能立即做出判断，译成对应的信源符号，则这类码称为即时码。 树的定义：一个图G若是无圈的且连通，则称图G是树。 为了联系树与即时码的关系我们引入关于判断树的一个定理； 定理1:图G是树当且仅当G的任何两个顶点都被唯一的路连接。 从上述定理1我们可以判断利用树构造的码为即时码，如下图构造的即时码：
从上面我们可以得到码字集合C1={000,001,010,011,100,101,110,111}，C2={00,01,02,10,11,12,20,210，211,212,220,221,222} 我们根据即时码的定义可得利用树构造的码都是即时码，我们也知道即时码一定是唯一可译码，因此树图能给我们带来比较方便的方法来构造即时码。 问题求解反思：我们从即时码的树图构造法中，我们得到:使用图论中的树我们能很容易得到信息论中即时码的一种构造方法，这里利用了交叉学科相互结合的思想，利用图我们能更好的理解一些实际问题，有利于我们的理解，从这个方面我们能得出图论在其他学科有着很重要的联系，有利于实际问题更好的解决。 2.Hamilton图的应用 Hamilton图的定义：一个含图G的每个顶点的圈称为是G的Hamilton 圈，这个含有Hamilton圈的图称为是一个Hamilton图。 Hamilton圈在现实中有着广泛的应用，当我们给出一个实际问题时，我们应该怎样Hamilton图来解决实际问题，这需要我们从联系实际
红外谱图解析基本知识 基团频率区 中红外光谱区可分成4000 cm-1 ~1300（1800）cm-1和1800 （1300 ）cm-1 ~ 600 cm-1两个区域。最有分析价值的基团频率在4000 cm-1 ~ 1300 cm-1之间，这一区域称为基团频率区、官能团区或特征区。区内的峰是由伸缩振动产生的吸收带，比较稀疏，容易辨认，常用于鉴定官能团。 在1800 cm-1（1300 cm-1）~600 cm-1区域内，除单键的伸缩振动外，还有因变形振动产生的谱带。这种振动基团频率和特征吸收峰与整个分子的结构有关。当分子结构稍有不同时，该区的吸收就有细微的差异，并显示出分子特征。这种情况就像人的指纹一样，因此称为指纹区。指纹区对于指认结构类似的化合物很有帮助，而且可以作为化合物存在某种基团的旁证。 基团频率区可分为三个区域 (1) 4000 ~2500 cm-1 X-H伸缩振动区，X可以是O、N、C或S等原子。 O-H基的伸缩振动出现在3650 ~3200 cm-1范围内，它可以作为判断有无醇类、酚类和有机酸类的重要依据。 当醇和酚溶于非极性溶剂（如CCl4），浓度于0.01mol. dm-3时，在3650 ~3580 cm-1处出现游离O-H基的伸缩振动吸收，峰形尖锐，且没有其它吸收峰干扰，易于识别。当试样浓度增加时，羟基化合物产生缔合现象，O-H基的伸缩振动吸收峰向低波数方向位移，在3400 ~3200 cm-1出现一个宽而强的吸收峰。 胺和酰胺的N-H伸缩振动也出现在3500~3100 cm-1，因此，可能会对O-H伸缩振动有干扰。 C-H的伸缩振动可分为饱和和不饱和的两种： 饱和的C-H伸缩振动出现在3000 cm-1以下，约3000~2800 cm-1，取代基对它们影响很小。如-CH3基的伸缩吸收出现在2960 cm-1和2876 cm-1附近；R2CH2基的吸收在2930 cm-1和2850 cm-1附近；R3CH基的吸收基出现在2890 cm-1
第一章：图论基本概念 1.定义 平凡图/非平凡图 简单图/复合图 空图 n 阶图 连通图/非连通图 完全图n K 12 n n n m K 偶图,m n K 完全偶图 ,m n m K mn K 正则图 图和补图，自补图 自补图判定方法 定点的度 d v 最小度 最大度 握手定理 2d v m 图的度序列与图序列，图序列判定方法（注意为简单图） 图的频序列 2.图运算 删点/删边 图并/图交/图差/图对称差 图联 积图/合成图111122,u adjv u v u adjv 或 超立方体 3.连通性 途径 迹 路 图G 不连通，其补图连通 一个图是偶图当且仅当它不包含奇圈 4.最短路算法（b t A T ） 5.矩阵描述 邻接矩阵及其性质，图的特征多项式 关联矩阵 6.极图？？ L 补图 完全L 部图 完全L 几乎等部图 托兰定理 第二章：树 1.定义 树：连通的无圈图 森林 树的中心和树的形心？ 入<=sqrt(2m(n-1)/n)
生成树 根树 出度 入度 树根 树叶 分支点 m 元根树 完全m 元根树 2.性质 每棵非平凡树至少有两片树叶 图G 是树当且仅当G 中任意两点都被唯一的路连接 T 是(n,m)树，则m = n – 1 具有k 个分支的森林有n-k 条边 每个n 阶连通图边数至少为n-1（树是连通图中边的下界） 每个连通图至少包含 一棵生成树 3.计算 生成树计数 递推计数法： G G e G e 关联矩阵计数法：去一点后，每个非奇异阵对应一棵生成树 最小生成树（边赋权） 避圈法 破圈法 完全m 元树： 11m i t 第三章：图的连通性 1. 割边、割点和块（性质使用反证法） 割边： w G e w G 边e 为割边当且仅当e 不在任何圈中 割点： w G v w G v 是无环连通图G 的一个顶点，v 是G 的割点当且仅当V(G-e)可以被划分为两个子 集，v 在两个子集内点互连的路上 块：没有割点的连通子图 G 顶点数>=3，G 是块当且仅当G 无环且任意两顶点位于同一圈上 v 是割点当且仅当v 至少属于G 的两个不同的块 2. 连通度 点割 k 顶点割 最小点割（最少用几个点把图割成两份） G 的连通度 G 连通图没顶点割时连通度 1G n ，非连通图 0G 边割 k 边割 最小边割（最少用几条边把图割成两份） G 的边连通度 G 递推到无圈，自环不算圈
工商管理中的运筹学问题—建模及求解 项目报告 姓名： 课题组的分工或贡献： 课程名称：运筹学 指导教师： 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。
八年级数学最短路径问题 【问题概述】最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题 - 求图中所有的最短路径． 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查．
【精品练习】 1．如图所示，正方形ABCD 的面积为12，△ABE 是等边三角形，点E 在正方形ABCD 内，在对角线AC 上有 一点P ，使PD +PE 的和最小，则这个最小值为（ ） A ． B ． C ．3 D 2．如图，在边长为2的菱形ABCD 中，∠ABC ＝60°，若将△ACD 绕点A 旋转，当AC ′、AD ′分别与BC 、CD 交于点E 、F ，则△CEF 的周长的最小值为（ ） A ．2 B ．32 C ．32+ D ．4 3．四边形ABCD 中，∠B ＝∠D ＝90°，∠C ＝70°，在BC 、CD 上分别找一点M 、N ，使△AMN 的周长最小时， A D E P B C
∠AMN +∠ANM 的度数为（ ） A ．120° B ．130° C ．110° D ．140° 4．如图，在锐角△ABC 中，AB ＝42，∠BAC ＝45°，∠BAC 的平分线交BC 于点D ，M 、N 分别是AD 和AB 上的动点，则BM +MN 的最小值是 ． 5．如图，Rt △ABC 中，∠C ＝90°，∠B ＝30°，AB ＝6，点E 在AB 边上，点D 在BC 边上（不与点B 、C 重合）， 且ED ＝AE ，则线段AE 的取值范围是 ． 6．如图，∠AOB ＝30°，点M 、N 分别在边OA 、OB 上，且OM ＝1，ON ＝3，点P 、Q 分别在边OB 、OA 上，则MP ＋PQ ＋QN 的最小值是_________．（注“勾股定理”：直角三角形中两直角边的平方和等于斜边的平方，即Rt △ABC 中，∠C ＝90°，则有222AB BC AC =+） 7．如图，三角形△ABC 中，∠OAB ＝∠AOB ＝15°，点B 在x 轴的正半轴，坐标为B (36，0)． OC 平分∠AOB ，点M 在OC 的延长线上，点N 为边OA 上的点，则MA ＋MN 的最小值是______． 8．已知A （2，4）、B （4，2）．C 在y 轴上，D 在x 轴上，则四边形ABCD 的周长最小值为 ， D E A B C
hdu4318 Power transmission 最短路当数据很大的时候的解决办法一道题目的解题全过程记录 最短路解决大数据模拟链表 Power transmission Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 663 Accepted Submission(s): 231 Problem Description The project West-East power transmission is famous around the world. It transmits the electricity from western areas to east China. There are many nodes in the power system. Each node is connected with several other nodes in the system by cable. Power can be only transmitted between two connected nodes. For each node, it can’t send power to two or more other nodes at the same time. As we have all known, power will be loss during the transmission. Bob is the chief engineer of the project. He wants to build a transmission line which send power from one node to another node and minimize the power loss at the same time. Now he asks you to help him solve the problem. Input There are several test cases. For each test case, the first line contains an integer N (0 < N ≤ 50000) which represents the number of nodes in the power system. Then there will be N groups of data following. For the i-th(0 < i ≤ N) group, the first line is an integer ki (ki ≤ 50), which means the node i is connected with ki nodes. The rest of the i-th group data are divided into ki lines. Each line contains an integer ai (0 < ai ≤ N, ai ≠ i) and an integer bi (0 ≤ bi ≤ 100), which represents power can be transmitted from node i to ai and will loss bi% while transmitting. The last line of input data contains three integers separated by single spaces. The first one is s, the second is t (0 < s, t ≤ N), and the third is the total power M (0 < M ≤ 10^6) at node s. Output For each test case, output the minimum of loss power while transmitting from node s to node t. The result should be printed with two digits to the right of the decimal point. If power cannot be transmitted from node s to node t, output “IMPOSSIBLE!” in a line. Sample Input 4 2
实验 KBr压片法测定苯甲酸红外光谱及谱图解析 I.实验目的 1、熟悉傅里叶变换红外光谱仪的工作原理及其使用方法。 2、掌握KBr压片法的操作技能。 3、了解红外光谱谱图解析。 II.实验用品 仪器：红外光谱仪（岛津 FTIR-8400S），压片机，研钵，红外灯。 试剂：溴化钾（光谱纯）、苯甲酸（分析纯）。 III.实验原理 傅立叶变换红外光谱仪是根据光的相干性原理设计的测量分子吸收光谱的仪器，属于干涉型光谱仪。傅立叶变换红外光谱仪主要由光源、干涉仪（迈克逊)、吸收池（样品室）、检测器、计算机和记录系统等组成。傅立叶变换红外光谱仪将各种频率的光信号经干涉作用后调制成干涉图，即时间域光谱图，然后用计算机进行快速傅立叶变换，换算成频率域光谱图即红外光谱图。 1 2
Ⅳ. 实验步骤 1、压片制样 准备： 1)保持使用压片机的房间湿度较低； 2)将压片机配件，放入干燥器备用； 3)用玛瑙研钵一次研磨适量KBr晶体干燥，放入干燥器备用； 4)为避免手汗对压片的影响，研磨和压片过程中戴手套； 压片操作： 1%干燥的样品，在红 1)取200毫克备用KBr粉末于玛瑙研钵中，加入 ~ 外灯下研细混匀； 2)使用乙醇棉清洗模具等； 3)将样品和KBr混合粉末放到模具中，用抹刀铺平；将装配好的压片 模具移至压片机下； 4)压片机阀门拧至lock, 加压至~60KN，停留适当时间使压片透明； 脱模，样品基本透明为合格； 5)将样品装入样品架； 2、测试 1)将样品架放入仪器内，点击测试按钮； 2)测试结束，保存文件。 3)取出样品架，卸下样品。 3、整理 1)清洁模具等制样器具； 2)如有需测试样品则进入下一样品的制备，如无样品则整理物品、清 洁台面后离开。 4、注意事项： 1)操作规范，轻举轻放，不要敲击； 2)研钵材质为玛瑙，易摔碎； 3)全过程要求干燥防水； 4)将溴化钾研细（2μm）； 5)控制溴化钾与样品的比例； 6)注意保持室内清洁、干燥； 7)不要震动光学台 8)取、放样品时,样品盖应轻开轻闭； 9)眼睛不要注视氦-氖激光，以免受到伤害。 Ⅴ.实验结果 1、对样品纯度、来源、元素分析及其他物理性质、谱学性质等方面的 了解。 2、初步分析特征基团频率、特征宽强峰、倍频（泛频）及合频特征峰。 3、初步确定为某类化合物后，与标准谱图核对 Ⅵ.问题讨论 1、KBr压片法制备红外吸收光谱固体试样的注意事项 2、红外光谱实验室为什么要求温度和相对湿度维持一定的指标
山东科技大学 本科毕业设计（论文）题目最大流问题以及应用 学院名称数学与系统科学学院 专业班级信息与计算科学2011级2班学生姓名吕永强 学号201101051416
摘要 网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的一个重要的内容，应用极为广泛。研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。 本论文讨论最大流问题，综述图论的历史背景、基本概念和基本知识；阐述网络的基本概念；介绍最大流问题的核心依据——Ford-Fulkerson最大流最小割定理；综述解决最大流问题的几种算法Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法，并比较各算法在解决不同问题中的优劣。 为了更加明确的展现最大流问题在生产生活中的应用，本文例举了一个实际生活中的问题——铁路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在一定的限制条件下，设计出一个在一昼夜间能通过某段铁路的最多的货运列车数量并列出每辆列车开出的时 刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和Ford-Fulkerson标号法的算法依据，最终解决了问题。 本文采用理论与实例相结合，重在应用理论依据解决实际问题，具有较强的实践性，突出的是应用。
Abstract The network flow problem is an important operational research subject. The maximum flow problem is an important content of network flow problem, which has widely applications. The research of maximum flow problem and its applications to industry, engineering，commerce, agriculture, transportation and other areas can bring us great convenience. The paper discusses the maximum flow problem, and summarizes the historical background of graph theory, basic concepts, basic knowledge and describes the basic concept of the network. The core basis of the maximum flow problem -- Ford-Fulkerson maximum flow minimum cut theorem is introduced. Several algorithms for solving maximal-flow problem like Ford-Fulkerson labeling algorithm, Edmonds-Karp correct algorithm, Dinic algorithm are summarized in this paper. It also compares various algorithms to solve different problems in the pros and cons. In order to more clearly show the application of the maximum flow problem in the production life, the paper illustrates a real-life problem - -The optimal scheduling of railway freight train to highlight the importance of maximum flow. This instance is to be solved under certain constraints , to design the most freight train numbers through the railway in a day and night and to list out the schedules for each train. In this instance, by abstracting the network diagram from the real problems, transform the actual problem into the maximum flow problem, and use the properties of graph and Ford-Fulkerson labeling algorithm, and ultimately solve the problem. In this paper, the combination of theory and examples focus on solving practical problems by applying theoretical basis. It has strong practicality and