Low-degree minimal spanning trees in normed spaces

离散数学》双语课程教学大纲一、课程编号：040510二、课程类型：必修课程学时：理论教学 72学时 / 4.5学分。

适用专业：信息与计算科学专业。

先修课程：线性代数、概率论、高等数学等。

后续课程：编译原理、操作系统、数据结构、数据库等。

三、课程性质与任务《离散数学》是信息与计算科学中基础理论的核心课程。

该课程采用双语教学形式，教材是国外原版英语教材。

通过本课程的学习，主要培养学生的抽象思维能力、严密的逻辑推理能力、阅读外文科技文献能力和专业英语写作能力。

并为学生今后处理离散信息、离散建模、软件开发、计算机硬件系统设计、程序设计的时间和空间复杂度分析等提供理论指导基础，是学生从事信息科学的实际工作必备数学工具。

四、教学主要内容及学时分配授课内容教学要求课时1.Fundamentals1.1.Sets and subsets1.2.Operations on sets1.5.Boolean matrix掌握 62 Logic2.1.Propositions and logical operations 2.2.Conditional Statements2.3.Methods of proof 掌握103.Counting3.1.Permutationsbinations3.3.Pigeonhole principle掌握 64.Relations and Digraphs4.1.Product sets4.1.Product sets and Partitions4.2.Relations and Digraphs4.3.Paths in Relations and Digraphs掌握204.4.Properties of relations4.5.Equivalence relations4.7.Operations on relations4.8.Transitive closure and Warshall’s Algorithm5.Functions5.1.Functions5.2.Functions for computer science5.3.Growth of functions5.4.Permutation Functions掌握 6 6.Order relations and structures6.1.Partially ordered sets6.2.Extremal elements of partially ordered sets 掌握67.Trees7.1.Treesbeled Trees7.3.Tree searching7.4.Undirected Trees7.5.Minimal spanning trees掌握 68.Topics in Graph theory8.1.Graphs8.2.Euler paths and circuits8.3.Hamiltonian paths and circuits8.5.matching problems8.6.coloring graphs掌握8五、教学基本要求了解离散数学所涵盖的内容及背景思想；理解离散数学组的数学思想和基本概念。

离散数学英中名词对照表英文Abel categoryAbel group (commutative group) Abel semigroup Abelian groupabsorption property accessibility relation acyclicaddition principleadequate set of connectives adjacentadjacent matrixadjugateadjunctionaffine planealgebraic closed field algebraic element algebraic extensionalphabetalternating groupannihilatorantecedentanti symmetryanti-isomorphismarc setargumentarityarrangement problem associateassociativeassociative algebraassociatorasymmetricatomatomic formulaaugmenting pigeon hole principle augmenting path automorphism automorphism group of graph auxiliary symbol A 离散数学英文—中文名词axiom of choiceaxiom of equalityaxiom of extensionalityaxiom of infinityaxiom of pairsaxiom of regularityaxiom of replacement for the formulaaxiom of the empty setaxiom of unionB balanced imcomplete block designbarber paradoxbase (base 2 exponential function)base (logarithm function to the base 2)Bell numberBernoulli numberBerry paradoxbiconditionalbijection (one-to-one correspondence)bi-mdulebinary relationbinary operationbinary symmetric channel (BSC)binary treebinomial coefficientbinomial theorembinomial transform bipartite graphblockblockblock codeblock designBondy theoremBoolean algebra Boolean expression Boolean functionBoole homomorophism Boole latticeBoolean matrixBoolean productbound occurrencebound variablebounded latticeBruijn theorem Burnside lemmaC cagecancellation property canonical epimorphism Cantor conjecture Cantor diagonal method Cantor paradoxcapacitycardinal number cardinalityCartesion product of graph Catalan numbercatenationCayley graphCayley theoremceiling functioncell (block)centercertain eventchain (walk) characteristic function characteristic of ring characteristic polynomial check digitsChinese postman problem chromatic number chromatic polynomial circuitcirculant graph circumferenceclassclassical completeness classical consistent cliqueclique numberclose with respect to closed termclosureclosure of graphcode elementcode lengthcode wordcoefficientcoimageco-kernalcoloringcoloring problemcombinationcombination numbercombination with repetationcommon divisorcommon factorcommutativecommutative diagramcommutative ringcommutative seimgroupcomparablecompatible withcomplementcomplement elementcomplement of B with respect to A complementary relation complemented latticecomplete bipartite graphcomplete graphcomplete k-partite graphcomplete latticecomplete matchcomplete n-treecompositecomposite operationcomposition (molecular proposition) composition of graph (lexicographic product) compound statementconcatenation (juxtaposition) concatenation graphconditional statement (implication) congruence relationcongruent toconjectureconjunctive normal form connected component connective connectivityconnectivity relation consecutively consequence (conclusion) conservation of flow consistent (non-contradiction) constructive proofcontain (in)contingencycontinuumcontraction of graph contradiction contravariant functor contrapositiveconversecoproductcorankcorresponding universal map countable (uncountable) countably infinite set counter examplecountingcovariant functorcoveringcovering numbercrossing number of graph cosetcotreecutcut edgecut vertexcyclecycle basiscycle matrixcycle rankcycle spacecycle vectorcyclic groupcyclic indexcyclic permutation cyclic semigroupD De Morgan's law decision procedure decoding table deduction theorem degreedegree sequence derivation algebra Descartes product descendant designated truth value deterministic diagonal functor diagonal matrix diameterdigraphdilemmadirect consequence direct limitdirect sumdirected by inclutiondisconnecteddiscrete Fourier transform discrete graph (null graph) disjoint setdisjunctiondisjunctive normal form disjunctive syllogism distancedistance transitive graph distinguished element distributivedistributive lattice divisibilitydivision subringdivison ringdivisor (factor) dodecahedrondomaindual categorydual formdual graphdual principledual statementdummy variableE eccentricityedge chromatic number edge coloringedge connectivityedge coveringedge covering numberedge cutedge setedge-independence number eigenvalue of graph element (entry) elementary divisor ideal elementary product elementary sumempty graphempty relationempty set endomorphismendpointentry (element) enumeration function epimorphismequipotentequivalenceequivalent category equivalent class equivalent matrix equivalent object equivalent relationerror functionerror patternEuclid algorithmEuclid domainEuler characteristicEuler circuitEuler functionEuler graphEuler numberEuler pathEuler polyhedron formula Euler tourEuler traileven permutationeventeverywhere defined excess capacity existence proof existential generalization existential quantification existential quantifier existential specification explicitextended Fibonacci number extended Lucas number extensionextension field extension graphexterior algebraF facefactorfactorablefactotialfactorizationfaithful (full) functor Ferrers graphFibonacci numberfieldfilterfinite dimensional associative division algebra finite extensionfinite field (Galois field )finite groupfinite setfinitely generated modulefirst order theory with equalityfive-color theoremfive-time-repetitionfixed pointfloor functionflowforestforgetful functorfour-color theorem (conjecture)F-reduced productfree elementfree monoidfree occurrencefree R-modulefree variablefree-Ω-algebrafull n-treefunction schemeG Galileo paradoxGauss coefficientGBN (G?del-Bernays-von Neumann system) GCD (Greatest Common Divisor) generalized Petersen graphgenerating functiongenerating proceduregeneratorgenerator matrixgeneric elementgenusgirthG?del completeness theoremgolden section numbergraceful graphgraceful tree conjecturegraphgraph of first class for edge coloring graph of second class for edge coloring graph rankgraph sequencegreatest common factorgreatest elementgreedy algorithmGrelling paradoxGr?tzsch graphgroupgroup codegroup of graphgrowth of functionHajós conjectureHamilton cycleHamilton graphHamilton pathHarary graphhash functionHasse diagramHeawood graphheightHerschel graphhom functorhomemorphism homomorphism homomorphism image homomorphism of graph hyperoctahedronhypothelical syllogism hypothesis (premise)idealidempotentidentityidentity functionidentity natural transformation imageimbeddingimmediate predcessor immediate successorimpossible eventincidentincident axiomincident matrixinclusion and exclusion principle inclusion relationindegreeindependentindependent number independent setindependent transcendental element indexindirected method H Iindividual variableinduced subgraphinfinite extensioninfinite groupinfinite setinitial endpointinitial objectinjectioninjection functorinjective (one to one mapping) inner faceinner neighbour setinorder searchintegral domainintegral subdomaininternal direct sum intersectionintersection of graph intersection operation intervalinvariant factorinvariant factor idealinverseinverse limitinverse morphisminverse natural transformation inverse operationinverse relationinversioninvertableinvolution property irreflexiveisolated vertexisomorphic categoryisomorphismisomorphism of graphjoinjoin of graphJ Jordan algebraJordan product (anti-commutator)Jordan sieve formulaj-skewjuxtapositionk-chromatic graphk-connected graphk-critical graphk-edge chromatic graphk-edge-connected graphk-edge-critical graph Kanaugh mapkernelKirkman schoolgirl problem Klein 4 groupKonisberge Brudge problem Kruskal's algorithm Kuratowski theoremlabeled graphLah numberLatin rectangleLatin squarelatticelattice homomorphismlawLCM (Least Common Multiple) leader cosetleast elementleafleast upper boundleft (right) identityleft (right) invertible element left (right) moduleleft (right) zeroleft (right) zero divisorleft adjoint functorleft cancellableleft cosetlengthlexicographic orderlLie algebraline- grouplinear array (list)linear graphlinear order (total order)K Llinear order set (chain)logical connective logical followlogically equivanlent logically implies logically valid loopLucas numbermagicmany valued proposition logic map coloring problem matchingmathematical structure matrix representation maximal element maximal idealmaximal outerplanar graph maximal planar graph maximum flow maximum matching maxtermmaxterm normal form (conjunctive normal form)McGee graph meetMenger theorem Meredith graph message word mini term minimal -connected graph minimal polynomial minimal spanning tree Minimanoff paradox minimum distance Minkowski summinterm (fundamental conjunctive form)minterm normal form (disjunctive normal form)M?bius function M?bius ladder M?bius transform (inversion)modal logic modelmodule homomorphismMkmoduler latticemodulusmodus ponensmodus tollensmodule isomorphismmonic morphismmonoidmonomorphismmorphism (arrow)M?bius functionM?bius ladderM?bius transform (inversion)multigraphmultinomial coefficientmultinomial expansion theoremmultiple-error-correcting codemultiplication principlemutually exclusivemultiplication tablemutually orthogonal Latin squareN n-ary operationn-ary productn-ary tree (n-tree)n-tuplenatural deduction systemnatural homomorphismnatural isomorphismnatural transformationnearest neighbernegationneighbour setnext state transition functionnon-associative algebranon-standard logicNorlund formulanormal formnormal modelnormal subgroup (invariant subgroup)n-relationnull graph (discrete graph)null objectnullary operationobjectodd permutationoffspringone to oneone-to-one correspondence (bijection) onto optimal solutionorbitorderorder (lower order,same order) order ideal order relationordered pairOre conditionorientationorthogonal Latin square orthogonal layoutoutarcoutdegreeouter faceouter neighbourouterneighbour setouterplanar graphpancycle graphparallelismparallelism classparentparity-check codeparity-check equationparity-check machineparity-check matrixpartial functionpartial ordering (partial relation) partial order relation partial order set (poset)partitionpartition number of integerpartition number of setPascal formulapathperfect code O Pperfect t-error-correcting code perfect graph permutationpermutation grouppermutation with repetation Petersen graphp-graphPierce arrowpigeonhole principleplanar graphplane graphPolish formPólya theorempolynomailpolynomial codepolynomial representation polynomial ring positional treepossible worldpostorder searchpower functorpower of graphpower setpredicateprenex normal formpreorder searchpre-ordered setprimary cycle modulePRIM's algorithmprimeprime fieldprime to each otherprimitive connectiveprimitive elementprimitive polynomialprincipal idealprincipal ideal domainprinciple of dualityprinciple of mathematical induction principle of redundancy probabilisticprobability (theory)productproduct categoryproduct partial orderproduct-sum formproof (deduction)proof by contraditionproper coloringproper factorproper filterproper subgroupproperly inclusive relationproposition (statement)propositional constantpropositional formula (well-formed formula,wff) propositional functionpropositional variablepseudocodepullbackpushoutquantification theoryquantifierquasi order relationquaternionquotient (difference) algebraquotient algebraquotient field (field of fraction)quotient groupquotient modulequotient ring (difference ring , residue ring) quotient set Ramsey graph Ramsey number Ramsey theorem rangerankreachability reconstruction conjecture recursive redundant digits reflexiveregular expression regular graph R Qregular representationrelation matrixrelative setremainderreplacement theoremrepresentationrepresentation functorrestricted proposition formrestrictionretractionreverse Polish formRichard paradoxright adjoint functorright cancellableright factorright zero divisonringring of endomorphismring with unity elementR-linear independencerooted treeroot fieldrule of inferenceRussell paradoxS sample spacesatisfiablesaturatedscopesearchingsectionself-complement graphsemantical completenesssemantical consistentsemigroupseparable elementseparable extensionsequencesequentsequentialSheffer strokesiblingssimple algebraic extensionsimple cyclesimple extensionsimple graphsimple pathsimple proposition (atomic proposition) simple transcental extension simplicationsinkslopesmall categorysmallest element Socrates argument soundness (validity) theorem sourcespanning subgraph spanning treespectra of graphspetral radiussplitting fieldsquare matrixstandard modelstandard monomil statement (proposition) Steiner tripleStirling numberStirling transformstrong induction subalgebrasubcategorysubdirect product subdivison of graph subfieldsubformulasubdivision of graph subgraphsubgroupsub-modulesubmonoidsublatticesubrelationsubringsub-semigroup subscript。

1.图论Graph Theory1.1.定义与术语Definition and Glossary1.1.1.图与网络Graph and Network1.1.2.图的术语Glossary of Graph1.1.3.路径与回路Path and Cycle1.1.4.连通性Connectivity1.1.5.图论中特殊的集合Sets in graph1.1.6.匹配Matching1.1.7.树Tree1.1.8.组合优化Combinatorial optimization1.2.图的表示Expressions of graph1.2.1.邻接矩阵Adjacency matrix1.2.2.关联矩阵Incidence matrix1.2.3.邻接表Adjacency list1.2.4.弧表Arc list1.2.5.星形表示Star1.3.图的遍历Traveling in graph1.3.1.深度优先搜索Depth first search (DFS)1.3.1.1.概念1.3.1.2.求无向连通图中的桥Finding bridges in undirected graph1.3.2.广度优先搜索Breadth first search (BFS)1.4.拓扑排序Topological sort1.5.路径与回路Paths and circuits1.5.1.欧拉路径或回路Eulerian path1.5.1.1.无向图1.5.1.2.有向图1.5.1.3.混合图1.5.1.4.无权图Unweighted1.5.1.5.有权图Weighed —中国邮路问题The Chinese post problem1.5.2.Hamiltonian Cycle 哈氏路径与回路1.5.2.1.无权图Unweighted1.5.2.2.有权图Weighed —旅行商问题The travelling salesman problem1.6.网络优化Network optimization1.6.1.最小生成树Minimum spanning trees1.6.1.1.基本算法Basic algorithms1.6.1.1.1.Prim1.6.1.1.2.Kruskal1.6.1.1.3.Sollin（Boruvka）1.6.1.2.扩展模型Extended models1.6.1.2.1.度限制生成树Minimum degree-bounded spanning trees1.6.1.2.2.k小生成树The k minimum spanning tree problem(k-MST)1.6.2.最短路Shortest paths1.6.2.1.单源最短路Single-source shortest paths1.6.2.1.1.基本算法Basic algorithms1.6.2.1.1.1. ..................................................................................................... D ijkstra1.6.2.1.1.2. .......................................................................................... B ellman-Ford1.6.2.1.1.2.1.....................................Shortest path faster algorithm(SPFA)1.6.2.1.2.应用Applications1.6.2.1.2.1. ........................... 差分约束系统System of difference constraints1.6.2.1.2.2. .......................... 有向无环图上的最短路Shortest paths in DAG1.6.2.2.所有顶点对间最短路All-pairs shortest paths1.6.2.2.1.基本算法Basic algorithms1.6.2.2.1.1. ....................................................................................... F loyd-Warshall1.6.2.2.1.2. .................................................................................................... Johnson 1.6.3.网络流Flow network1.6.3.1.最大流Maximum flow1.6.3.1.1.基本算法Basic algorithms1.6.3.1.1.1. ........................................................................ Ford-Fulkerson method1.6.3.1.1.1.1.......................................................... E dmonds-Karp algorithm1.6.3.1.1.1.1.1. ................................................... M inimum length path1.6.3.1.1.1.1.2. ........................................... Maximum capability path1.6.3.1.1.2. ............................................... 预流推进算法Preflow push method1.6.3.1.1.2.1.................................................................................. P ush-relabel1.6.3.1.1.2.2........................................................................... Relabel-to-front1.6.3.1.1.3. .......................................................................................... Dinic method1.6.3.1.2.扩展模型Extended models1.6.3.1.2.1. ............................................................................... 有上下界的流问题1.6.3.2.最小费用流Minimum cost flow1.6.3.2.1.找最小费用路Finding minimum cost path1.6.3.2.2.找负权圈Finding negative circle1.6.3.2.3.网络单纯形Network simplex algorithm1.6.4.匹配Matching1.6.4.1.二分图Bipartite Graph1.6.4.1.1.无权图-匈牙利算法Unweighted - Hopcroft and Karp algorithm1.6.4.1.2.带权图-KM算法Weighted –Kuhn-Munkres(KM) algorithm1.6.4.2.一般图General Graph1.6.4.2.1.无权图-带花树算法Unweighted - Blossom (Edmonds)1.图论Graph Theory1.1. 定义与术语Definition and Glossary1.1.1.图与网络Graph and Network二元组(),V E称为图(graph)。

图论总结（超强⼤）1.图论Graph Theory1.1.定义与术语Definition and Glossary1.1.1.图与⽹络Graph and Network1.1.2.图的术语Glossary of Graph1.1.3.路径与回路Path and Cycle1.1.4.连通性Connectivity1.1.5.图论中特殊的集合Sets in graph1.1.6.匹配Matching1.1.7.树Tree1.1.8.组合优化Combinatorial optimization1.2.图的表⽰Expressions of graph1.2.1.邻接矩阵Adjacency matrix1.2.2.关联矩阵Incidence matrix1.2.3.邻接表Adjacency list1.2.4.弧表Arc list1.2.5.星形表⽰Star1.3.图的遍历Traveling in graph1.3.1.深度优先搜索Depth first search (DFS)1.3.1.1.概念1.3.1.2.求⽆向连通图中的桥Finding bridges in undirected graph1.3.2.⼴度优先搜索Breadth first search (BFS)1.4.拓扑排序Topological sort1.5.路径与回路Paths and circuits1.5.1.欧拉路径或回路Eulerian path1.5.1.1.⽆向图1.5.1.2.有向图1.5.1.3.混合图1.5.1.4.⽆权图Unweighted2.Hamiltonian Cycle 哈⽒路径与回路1.5.2.1.⽆权图Unweighted1.5.2.2.有权图Weighed —旅⾏商问题The travelling salesman problem1.6.⽹络优化Network optimization1.6.1.最⼩⽣成树Minimum spanning trees1.6.1.1.基本算法Basic algorithms1.6.1.1.1.Prim1.6.1.1.2.Kruskal1.6.1.1.3.Sollin（Boruvka）1.6.1.2.扩展模型Extended models1.6.1.2.1.度限制⽣成树Minimum degree-bounded spanning trees1.6.1.2.2.k⼩⽣成树The k minimum spanning tree problem(k-MST)1.6.2.最短路Shortest paths1.6.2.1.单源最短路Single-source shortest paths1.6.2.1.1.基本算法Basic algorithms1.6.2.1.1.1. ..................................................................................................... D ijkstra1.6.2.1.1.2. .......................................................................................... B ellman-Ford1.6.2.1.1.2.1.....................................Shortest path faster algorithm(SPFA)1.6.2.1.2.应⽤Applications1.6.2.1.2.1. ........................... 差分约束系统System of difference constraints2.1.2.2. .......................... 有向⽆环图上的最短路Shortest paths in DAG1.6.2.2.所有顶点对间最短路All-pairs shortest paths1.6.2.2.1.基本算法Basic algorithms1.6.2.2.1.1. ....................................................................................... F loyd-Warshall1.6.2.2.1.2. .................................................................................................... Johnson 1.6.3.⽹络流Flow network1.6.3.1.最⼤流Maximum flow1.6.3.1.1.基本算法Basic algorithms1.6.3.1.1.1. ........................................................................ Ford-Fulkerson method 1.6.3.1.1.1.1.......................................................... E dmonds-Karp algorithm1.6.3.1.1.1.1.1. ................................................... M inimum length path1.6.3.1.1.1.1.2. ........................................... Maximum capability path1.6.3.1.1.2. ............................................... 预流推进算法Preflow push method1.6.3.1.1.2.1.................................................................................. P ush-relabel1.6.3.1.1.2.2........................................................................... Relabel-to-front1.6.3.1.1.3. .......................................................................................... Dinic method1.6.3.1.2.扩展模型Extended models1.6.3.1.2.1. ............................................................................... 有上下界的流问题1.6.3.2.最⼩费⽤流Minimum cost flow1.6.3.2.1.找最⼩费⽤路Finding minimum cost path1.6.3.2.2.找负权圈Finding negative circle2.3.⽹络单纯形Network simplex algorithm1.6.4.匹配Matching1.6.4.1.⼆分图Bipartite Graph1.6.4.1.1.⽆权图-匈⽛利算法Unweighted - Hopcroft and Karp algorithm1.6.4.1.2.带权图-KM算法Weighted –Kuhn-Munkres(KM) algorithm1.6.4.2.⼀般图General Graph1.6.4.2.1.⽆权图-带花树算法Unweighted - Blossom (Edmonds)1.图论Graph Theory1.1. 定义与术语Definition and Glossary1.1.1.图与⽹络Graph and Network⼆元组(),V E称为图(graph)。

《离散数学》双语专业词汇表set：集合subset：子集element, member：成员，元素well-defined：良定，完全确定brace：花括号representation：表示sensible：有意义的rational number：有理数empty set：空集Venn diagram：文氏图contain(in)：包含（于）universal set：全集finite (infinite) set：有限（无限）集cardinality：基数，势power set：幂集operation on sets：集合运算disjoint sets：不相交集intersection：交union：并complement of B with respect to A：A与B的差集symmetric difference：对称差commutative：可交换的associative：可结合的distributive：可分配的idempotent：等幂的de Morgan’s laws：德摩根律inclusion-exclusion principle：容斥原理sequence：序列subscript：下标recursive：递归explicit：显式的string：串，字符串set corresponding to a sequence：对应于序列的集合linear array(list)：线性表characteristic function：特征函数countable(uncountable)：可数（不可数）alphabet：字母表word：词empty sequence(string)：空串catenation：合并，拼接regular expression：正则表达式division：除法multiple：倍数prime：素（数）algorithm：算法common divisor：公因子GCD(greatest common divisor)：最大公因子LCM(least common multiple)：最小公倍数Euclidian algorithm：欧几里得算法，辗转相除法pseudocode：伪码（拟码）matrix：矩阵square matrix：方阵row：行column：列entry(element)：元素diagonal matrix：对角阵Boolean matrix：布尔矩阵join：并meet：交Boolean product：布尔乘积mathematical structure(system)：数学结构（系统）closed with respect to：对…是封闭的binary operation：二元运算unary operation：一元运算identity：么元，单位元inverse：逆元statement, proposition：命题logical connective：命题联结词compound statement：复合命题propositional variable：命题变元negation：否定（式）truth table：真值表conjunction：合取disjunction：析取quantifier：量词universal quantification：全称量词化propositional function：命题公式predicate：谓词existential quantification：存在量词化converse：逆命题conditional statement, implication：条件式，蕴涵式consequent, conclusion：结论，后件contrapositive：逆否命题hypothesis：假设，前提，前件biconditional, equivalence：双条件式，等价logically equivalent：（逻辑）等价的contingency：可满足式tautology：永真(重言)式contradiction, absurdity：永假(矛盾)式logically follow：是…的逻辑结论rules of reference：推理规则modus ponens：肯定律m odus tollens：否定律indirect method：间接证明法proof by contradiction：反证法counterexample；反例basic step：基础步principle of mathematical induction：（第一）数学归纳法induction step：归纳步strong induction：第二数学归纳法relation：关系digraph：有向图ordered pair：有序对，序偶product set, Caretesian set：叉积，笛partition, quotient set：划分，商集block, cell：划分块，单元domain：定义域range：值域R-relative set：R相关集vertex(vertices)：结点，顶点edge：边in-degree：入度out-degree：出度path：通路，路径cycle：回路connectivity relation：连通性关系reachability relation：可达性关系composition：复合reflexive：自反的irreflexive：反自反的empty relation：空关系symmetric：对称的asymmetric：非对称的antisymmetric：反对称的graph：无向图undirected edge：无向边adjacent vertices：邻接结点connected：连通的transitive：传递的equivalent relation：等价关系congruent to：与…同余modulus：模equivalence class：等价类linked list：链表storage cell：存储单元pointer：指针complementary relation：补关系inverse：逆关系closure：闭包symmetric closure：对称闭包reflexive closure：自反闭包composition：关系的复合transitive closure：传递闭包Warshal’s algorithm：Warshall算法function, mapping, transformation：函数，映射，变换argument：自变量value, image：值，像，应变量labeled digraph：标记有向图identity function on A：A上的恒等函数everywhere defined：处处有定义的onto：到上函数，满射one to one：单射，一对一函数bijection, one-to-one correspondence：双射，一一对应invertible function：可逆函数floor function：下取整函数ceiling function：上取整函数Boolean function：布尔函数base 2 exponential function：以2为底的指数函数logarithm function to the base n：以n为底的对数hashing function：杂凑函数key：键growth of function：函数增长same order：同阶lower order：低阶running time：运行时间permutation：置换，排列cyclic permutation：循环置换，轮换transposition：对换odd(even) permutation：奇（偶）置换order relation：序关系partial order：偏序关系partially ordered set, poset：偏序集dual：对偶comparable：可比较的linear order(total order)：线序，全序linearly ordered set, chain：线（全）序集，链product partial order：积偏序lexicographic order：字典序Hasse diagram：哈斯图topological sorting：拓扑排序isomorphism：同构maximal(minimal) element：极大(小)元extremal element：极值元素greatest(least) element：最大(小)元unit element：么(单位)元zero element：零元upper(lower) bound：上(下)界least upper(greatest lower) bound：上(下)确界lattice：格join：，保联，并meet：保交，交sublattice：子格absorption property：吸收律bounded lattice：有界格distributive lattice：分配格complement：补元modular lattice：模格Boolean algebra：布尔代数involution property：对合律Boolean polynomial, Boolean expression：布尔多项式（表达式）or(and, not) gate：或(与，非)门inverter：反向器circuit design：线路设计minterm：极小项Karnaugh map：卡诺图tree：树root：根，根结点rooted tree：（有）根树level：层，parent：父结点offspring：子女结点siblings：兄弟结点height：树高leaf(leave)：叶结点ordered tree：有序树n-tree：n-元树complete n-tree：完全n-元树(complete) binary tree：(完全)二元(叉)树descendant：后代subtree：子树positional tree：位置树positional binary tree：位置二元(叉)树doubly linked list：双向链表tree searching：树的搜索（遍历）traverse：遍历，周游preorder search：前序遍历Polish form：（表达式的）波兰表示inorder search：中序遍历postorder search：后序遍历reverse Polish form：（表达式的）逆波兰表示linked-list representation：链表表示undirected tree：无向树undirected edge：无向边adjacent vertices：邻接结点simple path：简单路径（通路）simple cycle：简单回路acyclic：无（简单）回路的spanning tree：生成树，支撑树Prim’s algorithm：Prim算法minimal spanning tree：最小生成树weighted graph：（赋）权图weight：树distance：距离nearest neighbor：最邻近结点greedy algorithm：贪婪算法optimal solution：最佳方法Kruskal’s algorithm：Kruskal算法graph：(无向)图vertex(vertices)：结点edge：边end point：端点relationship：关系connection：连接degree of a vertex：结点的度loop：自回路path：路径isolated vertex：孤立结点adjacent vertices：邻接结点circuit：回路simple path(circuit)：基本路径(回路) connected：连通的disconnected：不连通的component：分图discrete graph(null graph)：零图complete graph：完全图regular graph：正规图，正则图linear graph：线性图subgraph：子图Euler path(circuit)：欧拉路径(回路) Konisberg Bridge problem：哥尼斯堡七桥问题ordinance：法规recycle：回收，再循环bridge：桥，割边Hamiltonian path(circuit)：哈密尔顿路径(回路)dodecahedron：正十二面体weight：权TSP(traveling salesperson problem)：货郎担问题transport network：运输网络capacity：容量maximum flow：最大流source：源sink：汇conversation of flow：流的守恒value of a flow：流的值excess capacity：增值容量cut：割the capacity of a cut：割的容量matching problems：匹配问题matching function：匹配函数compatible with：与…相容maximal match：最大匹配complete match：完全匹配coloring graphs：图的着色proper coloring：正规着色chromatic number of G：G的色数map-coloring problem：地图着色问题conjecture：猜想planar graph：(可)平面图bland meats：未加调料的肉chromatic polynomial：着色多项式binary operation on a set A：集合A上的二元运算closed under the operation：运算对…是封闭的commutative：可交换的associative：可结合的idempotent：幂等的distributive：可分配的semigroup：半群product：积free semigroup generated by A：由A生成的自由半群identity(element)：么（单位）元monoid：含么半群，独异点subsemigroup：子半群submonoid：子含么半群isomorphism：同构homomorphism：同态homomorphic image：同态像Kernel：同态核congruence relation：同余关系natural homomorphism：自然同态group：群inverse：逆元quotient group：商群Abelian group：交换（阿贝尔）群cancellation property：消去律multiplication table：运算表finite group：有限（阶）群order of a group：群的阶symmetric group：对称群subgroup：子群alternating group：交替群Klein 4 group：Klein四元群coset：陪集(left) right coset：(左)右陪集normal subgroup：正规(不变)子群prerequisite：预备知识virtually：几乎informal brand：不严格的那种notation：标记sensible：有意义的logician：逻辑学家extensively：广泛地，全面地commuter：经常往来于两地的人by convention：按常规，按惯例dimension：维(数) compatible：相容的discipline：学科reasoning：推理declarative sentence：陈述句n-tuple：n-元组component sentence：分句tacitly：默认generic element：任一元素algorithm verification：算法证明counting：计数factorial：阶乘combination：组合pigeonhole principle：鸽巢原理existence proof：存在性证明constructive proof：构造性证明category：类别，分类factor：因子consecutively：相继地probability(theory)：概率(论) die：骰子probabilistic：概率性的sample space：样本空间event：事件certain event：必然事件impossible event：不可能事件mutually exclusive：互斥的，不相交的likelihood：可能性frequency of occurrence：出现次数(频率) summarize：总结，概括plausible：似乎可能的equally likely：等可能的，等概率的random selection(choose an object at random)：随机选择terminology：术语expected value：期望值backtracking：回溯characteristic equation：特征方程linear homogeneous relation of degree k：k阶线性齐次关系binary relation：二元关系prescribe：命令，规定coordinate：坐标criteria：标准，准则gender：性别graduate school：研究生院generalize：推广notion：概念intuitively：直觉地verbally：用言语approach：方法，方式conversely：相反地pictorially：以图形方式restriction：限制direct flight：直飞航班tedious：冗长乏味的main diagonal：主对角线remainder：余数random access：随机访问sequential access：顺序访问custom：惯例polynomial：多项式substitution：替换multi-valued function：多值函数collision：冲突analysis of algorithm：算法分析sophisticated：复杂的set inclusion(containment)：集合包含distinguish：区分analogous：类似的ordered triple：有序三元组recreational area：游乐场所multigraph：多重图pumping station：抽水站depot：货站，仓库relay station：转送站。

The Directed Minimum-DegreeSpanning Tree ProblemRadha Krishnan and Balaji RaghavachariComputer Science Department,University of Texas at Dallas,Richardson,TX75083-0688,USA.{Radha.Krishnan,Balaji.Raghavachari}@Abstract.Consider a directed graph G=(V,E)with n vertices and aroot vertex r∈V.The DMDST problem for G is one of constructing aspanning tree rooted at r,whose maximal degree is the smallest amongall such spanning trees.The problem is known to be NP-hard.A quasi-polynomial time approximation algorithm for this problem is presented.The algorithmfinds a spanning tree whose maximal degree is at mostO(∆∗+log n)where,∆∗is the degree of some optimal tree for theproblem.The running time of the algorithm is shown to be O(n O(log n)).Experimental results are presented showing that the actual running timeof the algorithm is much smaller in practice.1IntroductionThe minimum-degree spanning tree(MDST)problem for an undirected graph G=(V,E)is that of constructing a spanning tree of G,whose maximal degree is the smallest among all spanning trees of G.It is a generalization of the Hamil-tonian Path problem and thus is also NP-hard.The problem can be defined on directed graphs as follows.Given a root vertex r∈V,find an incoming(or outgoing)spanning tree rooted at r,known as a branching,in which the maxi-mal indegree(outdegree)of a vertex is minimized.We will refer to the directed version of the MDST problem as the DMDST problem.In the Steiner case,a set of terminals D⊆V is also specified.The output tree must span the set D. However,it may contain any of the other vertices of G.The general problem of computing low-degree trees is both fundamental and finds ready applicability,such as in noncritical broadcast and VLSI layout prob-lems.It is also inherently appealing due to its seeming simplicity.Previous polynomial-time algorithms[2]for the DMDST problemfind trees whose de-gree is at most O(∆∗log n),i.e.,a factor of log n from the optimal degree∆∗. On the other hand,the algorithm in[4]for undirected graphsfinds a tree whose degree is at most∆∗+1,i.e.,an additive constant1away from the optimal. Our work tries to bridge this gap in performance of approximation algorithms for the undirected and directed versions of the MDST problem.Research supported by the National Science Foundation under grant CCR-9820902.R.Hariharan,M.Mukund,and V.Vinay(Eds.):FSTTCS2001,LNCS2245,pp.232–243,2001.c Springer-Verlag Berlin Heidelberg2001The Directed Minimum-Degree Spanning Tree Problem233 Our algorithm for the DMDST problemfinds a tree whose maximal degree is at most c∆∗+ log c n =O(∆∗+log n),for any constant c>1.The ap-proximation quality has therefore been improved from a multiplicative factor of log n to an additive term of log n.The running time of the algorithm is shown to be quasi-polynomial,O(n log c n+O(1)).However,it is conjectured that a better bound may be provable,and also that the running time may be much better in practice for this reason.We present experimental evidence to show that in practice the algorithm ran much faster than the theoretical bound obtained here. Also,the degree of the tree output is often very close to the optimal degree. Previous work in undirected graphs.Thefirst result on approximating a minimum-degree spanning tree was that of F¨u rer and Raghavachari[2].They gave a polynomial-time approximation algorithm that returns a tree whose de-gree is at most O(∆∗log n).Thefirst polynomial-time approximation algorithm for the Steiner version of the problem was provided by Agrawal,Klein and Ravi[1].Their approximation ratio is O(log|D|),where D is the set of ter-minals.Ravi,Raghavachari and Klein[12]studied generalizations of the MDST problem and gave quasi-polynomial time approximation algorithms.F¨u rer and Raghavachari[4]improved their previous results and provided a new polynomial-time algorithm to approximate the MDST problem to within one of optimal. Their algorithm also extends to the Steiner version of the problem,but only works on undirected graphs.A survey of these and other minimum-degree prob-lems has appeared in a book on approximation algorithms[9].Ravi,Marathe,Ravi,Rosenkrantz and Hunt[11]proposed algorithms for computing low-weight bounded-degree subgraphs satisfying given connectivity properties.Given a graph G with nonnegative weights on the edges,and a degree bound∆,their algorithm computes a spanning tree of G whose degree is at most O(∆log n∆)and whose weight is at most O(log n)times the weight of a minimum-weight tree with degree at most∆.Their techniques extend to the Steiner tree and generalized Steiner tree problems with the same ratio.They also studied special cases when the edge weights satisfy the triangle inequality and presented efficient algorithms for computing subgraphs that have low weight and small bottleneck cost.More recently,K¨o nemann and Ravi[7]have given an algorithm thatfinds a tree of degree O(∆+log n)whose cost is at most O(1)times the cost of an optimal tree of degree∆.Given a graph G and an independent set of nodes I,the problem offinding a spanning tree that minimizes the maximum degree of any node in I is solvable in polynomial time[8].Gavish[5]formulated the MDST problem as a mixed integer program and provided an exact solution using the method of Lagrangian multipliers.Ravi[10]presented an approximation algorithm for the problem of finding a spanning tree whose diameter plus maximal degree is a minimum. Previous work in directed graphs.F¨u rer and Raghavachari[2]showed that their algorithm for computing low-degree trees further generalizes tofind branch-ings in directed graphs.Their algorithm builds a tree in stages by taking the union of a sequence of low-degree forests(e.g.,matchings),and the degree of the234Radha Krishnan and Balaji Raghavachariresulting tree is shown to be O(∆∗log n).This paper improves the performance from a multiple of log n to an additive term of log n.2Definitions and NotationThe input is an arbitrary directed graph G=(V,E),and a root vertex r∈V. Let n be the number of vertices in G.It is assumed that r is reachable from all vertices of G.Let T∗be an optimal DMDST whose maximal degree is∆∗.A branching rooted at r is a subgraph of G whose underlying undirected graph is a spanning tree such that it has a directed path from any vertex to r.In a branching,each vertex other than r has exactly one outgoing edge and r has no outgoing edges.It is easily shown that the only subgraphs with n−1edges in which there is a directed path from every vertex to r is a branching rooted at r.Sometimes this is also known as an in-branching.One can also define an out-branching,in which r can reach every vertex of G through directed paths.In this paper,a branching always refers to an in-branching.However,our algorithm can be easily modified tofind out-branchings with small outdegree.Let T be a branching.For each edge(v,w)in T,we call w as the parent of v,denoted by p[v].Since every vertex except r has a unique outgoing edge, each vertex has a unique parent,and r has none.The reflexive and transitive closure of the parent function yields the ancestor relation.In other words,v is an ancestor of u if there is a directed path in the branching from u to v.We call u a descendent of v if v is its ancestor.We say that two vertices v and w are related if either v is an ancestor of w,or vice versa.Otherwise,we say that the vertices are unrelated.For any two unrelated vertices v and w,the least common ancestor is the ancestor closest to v that is also an ancestor of w.We define C v to be the set of all vertices in the subtree rooted at v,i.e.,the set of all vertices including v,for which v is an ancestor.The degree of a vertex in a given branching is the number of edges coming into that vertex.We may also refer to it as its indegree.For a branching,let S∆be the set of all vertices whose degree is∆or more.The degree of a branching is the maximum degree of any of its vertices.Our goal is tofind a branching of as small a degree as possible.3MDST Problem:Directed vs Undirected GraphsOur algorithm is based on an algorithm proposed by F¨u rer and Raghavachari[3] for undirected graphs thatfinds a tree whose degree is O(∆∗+log n).Their algo-rithm starts with an arbitrary spanning tree of G,and iteratively decreases the degree of high-degree vertices by applying“improvement”steps.An improve-ment step involves replacing an edge incident to a high-degree node by another edge that keeps the tree connected.They applied improvement steps to high-degree nodes repeatedly,until no improvement was possible at these nodes.In order to extend this algorithm to directed graphs,we make several modifications.The Directed Minimum-Degree Spanning Tree Problem235(a)Undirected graph(b)Directed graphFig.1.Directed versus undirected graphsFirst,in directed graphs,we face the following problem.Suppose an edge is removed that splits the current tree into two trees,namely P and Q(see Fig.1). Suppose we try to combine the two trees by adding the edge(x,y),where x∈P and y∈Q.In the case of undirected graphs,any such edge would do and we get back a spanning tree of G.But in the case of directed graphs,the vertex x must be the root of the tree Q.Otherwise the procedure would not yield a branching of G.To illustrate,as shown in Fig.1(a),undirected trees P and Q can be merged into a single tree by adding either the edge(x,y)or the edge(a,b).But in the case of directed graphs,as shown in Fig.1(b),only the edge(x,y)yields a branching.If(a,b)is added,then a has two outgoing edges,and the resulting graph is not a branching.Therefore the improvement step needs to be modified.Second,the analysis of the algorithm for undirected graphs uses the notion of“witness sets”.A witness set is a small set of nodes whose removal splits the graph into a large number of connected components.The ratio of the number of components to the number of nodes in the witness set is a lower bound on∆∗. It was shown by F¨u rer and Raghavachari[3]that there are witness sets that can be used tofind a tree whose degree is at most∆∗+1.We will show that the notion of a witness set must also be modified for the case of directed graphs.3.1Witness SetsThe minimum ratio of the cardinality of a vertex set W to the number of com-ponents that are generated when W is removed from the graph is called the toughness of the graph.Win[13]has shown the following interesting relation-ship between the toughness of a graph and the MDST problem.He showed that if the toughness of a graph is at least1k−2,then it has a spanning tree whose degree is at most k(for k>2).Vertex sets for which the above ratio is close to the toughness of the graph are called witness sets.F¨u rer and Raghavachari[3] used such witness sets to establish a lower bound on the degree of an optimal tree for the MDST problem.They showed that if there is a witness set of size w whose removal splits G into t components then∆∗≥ w+t−1.w236Radha Krishnan and Balaji RaghavachariThis definition is not suitable for directed graphs.We prove a new lemma that can be used to establish a lower bound on∆∗for directed graphs.Suppose we have a set of witness vertices W and a set of blocking vertices B satisfying the property that paths from different vertices of W do not intersect before being incident to a vertex in B(see Fig.2).From this we show that there are|W| paths that have distinct edges into B,thus establishing a lower bound on the degree of vertices in B in any branching.Fig.2.Paths from W are internally disjointLemma1.Let G=(V,E)be a directed graph and r∈V.Suppose there are subsets of vertices W⊂V and B⊂V that satisfy the following properties: 1.Any path from a vertex v∈W to r must have an incoming edge into a vertexin B,2.For any two vertices v,w∈W,any path from v to r can intersect a pathfrom w to r only after it passes through a vertex in B.In other words,G has no branching wherein the path from v to the least common ancestor of v and w does not contain a vertex of B.Then the degree of an DMDST rooted at r of G satisfies,∆∗≥ |W|/|B| . Proof.Let T∗be an optimal branching rooted at r for the DMDST problem. Since it is a branching,it contains a path from any vertex to the root.By Condition1of the lemma,a path from a vertex v∈W to r contains at least one edge into a vertex in B.Let f v=v be the closest ancestor of v such that f v∈B.Let P v be this path from v to f v.By Condition2of the lemma,the paths{P v:v∈V−{r}}are all internally disjoint.Therefore we have identified |W|paths in T∗,and each of these paths has an incoming edge to some vertex in B.Therefore the average degree of a vertex in B is at least|W|/|B|,implying that there is at least one vertex in T∗whose degree is |W|/|B| or more.4The DMDST AlgorithmOur algorithm starts with an arbitrary branching T of G and reduces the degree of high-degree nodes iteratively by applying improvement steps defined below.The Directed Minimum-Degree Spanning Tree Problem237 Consider a node v whose parent in the tree is p.We can decrease the indegree of p by1(which is an improvement step applied to p)if we can delete the edge (v,p)andfind an alternate path for v to reach the root r.This new path from v to r initially goes through some nodes of C v,vertices in the subtree rooted at v,reaching a node w∈C v(w may be v itself).A new edge(w,x)is added (replacing the edge from w to its parent)where x is unrelated to v.Since x is unrelated to v,it is unrelated to any vertex in C v.Therefore the path from x to r in T is unaffected.Since v can reach x after the improvement,v can reach r. We perform an improvement step only if after the improvement,vertices whose.degrees increased have a smaller degree than p(a)Branching before improvement(b)Branching after improvementFig.3.Example of an improvement applied to vertex pFig.3illustrates an example of an improvement step.In this example,the tree edges are shown in thick lines and other edges of g are shown in dashed lines.The indegree of p is5.If v canfind an alternate path to r so that the edge (v,p)may be deleted from T,the degree of p can be decreased to4.The edge (c,g)is deleted because the indegree of g is already4,and if we choose to add this edge,its indegree becomes5.Decreasing the degree of p to4by increasing the degree of g to5(old degree of p)does not make progress.The edge(v,p) is also deleted and the algorithm tries tofind a path from v to r.Such a path exists—(v→a→b→c→d→w→x→...→r)and the algorithm uses this path to modify the branching;the new branching is shown in Fig.3(b).The indegree of p has thus been successfully reduced to4.We will now describe how to test if such an improvement exists.Let the degree of p be∆.Wefirst ensure that the degree of vertices whose degree is∆−1or238Radha Krishnan and Balaji Raghavacharigreater does not increase.Delete all nontree edges of G that are incident into nodes of degree∆−1or greater,i.e.,S∆−1.In the remaining graph,delete the edge(v,p)and test if there is a path from v to r.If such a path exists,we can select a shortest such path and use it to make an improvement to p as follows. Let x be the vertex closest to v in the path such that x∈C v.For each edge (y,z)in the path from v to x,we replace the edge(y,p[y])by the edge(y,z).It can be verified that the above operation results in another branching since the number of edges is still n−1and all vertices can still reach r.Procedure Improvement(T,v,p)1.Delete(v,p)from G.2.Let∆be the degree of p.For each vertex u∈V whose indegree in T isgreater than∆−1,delete from G edges going into u that are not in T.3.Run Breadth-first search from v,and test if the root r is reachable from v.4.If there is no path from v to r,return False after restoring all edges of G.5.Otherwise,BFSfinds a path P from v to r.Let w be thefirst vertex on thepath with the property that(w,x)∈P and w∈C v and x∈C v.6.For each edge(a,b)in the subpath of P from v to x,replace the edge from(a,p[a])in T by(a,b).7.Restore all edges of G and return True.We now consider the DMDST algorithm.The algorithm tries to reduce the degree of high-degree vertices byfinding suitable improvements.The target ver-tices are those whose degrees are within O(log n)from the maximal degree of the current branching.When no improvements are possible to these nodes,the algorithm terminates.Algorithm DMDST(G,r)1.Find a branching T of G rooted at r.Let its degree be k.Fix some constantc>1.2.For each edge(v,p)∈T,run Improvement(T,v,p)if the degree of p in Tis more than k− log c n .If the degree of T has changed,reset k to be its new degree.3.Repeat the above step until Improvement(T,v,p)returns false for everyedge(v,p)∈T for which it is called.4.Return T.5Analysis of the AlgorithmThe analysis of the running time of the algorithm uses potential functions that were introduced by F¨u rer and Raghavachari[3],and adapted by Ravi, Raghavachari and Klein[12]and K¨o nemann and Ravi[7].In fact our analysis of the running time is almost the same as in[12].The potential of a vertex of degree∆is defined to be n∆,and therefore the total potential of all the verticesThe Directed Minimum-Degree Spanning Tree Problem239 is at most n k+1,where k is the current degree of T.An improvement is applied to a vertex of degree∆>k− log c n .Each improvement step that targets a vertex of degree∆reduces the total potential by at least n∆−2,since the degree of a node of degree∆is reduced by1and the degree of all the other nodes may increase to∆−1.Since∆>k− log c n ,this reduction in potential is at least a fraction n−log c n−3of the current potential of the branching.It follows that the number of improvement steps is at most n log c n+3.Each improvement step can be implemented in O(n3)time,thus giving a total running time of O(n log c n+6) for the algorithm.The following lemma relates the running time of the algorithm and the num-ber of improvement steps,I.This expression for the running time is a more meaningful measure,since our experiments show that I grows only linearly with n,making the observed running time O(n4).Lemma2.The running time of Algorithm DMDST is O(n3I),where I is the number of improvement steps.The analysis of the degree bound of the tree output by the algorithm is more interesting.For this analysis,the notion of witness sets that was used by the algorithm for undirected graphs has to be strengthened.In directed graphs, there may be edges in the“wrong”direction that don’t help in constructing a branching,but they may stop the graph from falling apart when a few critical vertices are removed.We now show how tofind a witness set W and its blocking set B for the branching T output by our algorithm.In fact we will identify one pair of sets W and B for each∆in the range k to k− log c n .Lemma3.Let T be a branching whose degree is∆or more.Let S∆be the set of vertices whose degree is∆or more.There are at least(∆−1)|S∆|+1unrelated vertices such that the parent of each of these vertices is in S∆.Proof.The proof is by induction on the cardinality of S∆.If|S∆|=1,then the single vertex in that set has at least∆children,and the children of this vertex satisfy the lemma.If|S∆|>1,remove a node v∈S∆and all its descendents from T such that v has no descendents in S∆(except itself).Now the resulting branching has|S∆|−1nodes of degree∆or more,and by the induction hypoth-esis,has at least(∆−1)(|S∆|−1)+1unrelated nodes that are children of S∆. Since all these nodes are unrelated to each other,at most one of these nodes is an ancestor of v.Therefore there are(∆−1)(|S∆|−1)nodes left that are not ances-tors of v.Now we add the children of v to this set,the set increases by at least∆, and the number of nodes that we get is(∆−1)(|S∆|−1)+∆=(∆−1)|S∆|+1.Lemma4.Let T be the branching output by our algorithm.Let its degree be k. Then for any k− log c n <∆≤k,∆∗≥(∆−1)|S∆|+1|S∆−1|.240Radha Krishnan and Balaji RaghavachariProof.Let W be the set of vertices as in Lemma3that are children of nodes in S∆,but have no descendents in S∆.We know that|W|≥(∆−1)|S∆|+1.Let B be S∆−1,the set of all vertices whose degree is at least∆−1.For each vertex v∈W,the algorithm tries tofind an improvement that decreases the degree of p=p[v].Since it failed(the condition under which the algorithm stops),any path from v to r that doesn’t use(v,p)must go through a vertex x in S∆−1.By construction,the internal vertices of the path from v to x is entirely contained in C v,the descendents of v in T.Since all vertices of W are unrelated to each other,these subtrees are disjoint.Therefore,the sets W and B that we have defined satisfy the conditions given in the statement of Lemma1.Therefore,∆∗≥ |W|/|B| ≥(∆−1)|S∆|+1|S∆−1|.Theorem1.The degree of the branching returned by our algorithm is at most c∆∗+log c n,where c>1is the constant in Step1of the DMDST algorithm. Proof.Lemma4establishes a set of lower bounds on∆∗for log c n different values of∆.At least for one of these values of∆,|S∆−1|≤c|S∆|.Using this value of∆,we get k≤c∆∗+log c n.6Experimental ResultsThe algorithms were implemented in C,using Knuth’s Stanford GraphBase toolkit[6]and tested on large numbers of randomly generated graphs.These input random graphs actually followed two different patterns,as described be-low individually.The running time clearly depends upon the initial tree,and this was indeed observed in the experimental study.We tried to generate the initial tree using both depth-first search(DFS)and breadth-first search(BFS).BFS tends to generate high degree nodes and therefore the number of improvement steps tends to be much higher than if the initial tree was generated by DFS. In dense graphs,DFS generallyfinds low-degree trees by itself.While we found that our algorithm further reduces the degree of the initial DFS tree significantly, we present experimental results with an initial BFS tree,because we wished to capture the worst-case performance of the algorithm.6.1Uniformly Distributed Random GraphsFor this class of randomly generated input graphs,the probability of existence of an edge between two vertices is set to be a constant.The number of vertices were varied from100to9000.A small number of runs were on20,000-node graphs.We also varied the density of the graph.This class of graphs tends to be Hamiltonian and a good algorithm should be able tofind a low-degree branching. We observed that our algorithm also has no difficulty in achieving this.The results for this class of graphs is presented in Fig.4,which shows the number of improvement steps as a function of n.The x-axis shows n and theThe Directed Minimum-Degree Spanning Tree Problem 241900080007000600050004000300020001000250002000015000100005000Fig.4.Number of improvement steps versus n y-axis shows the average number of improvement steps in random graphs with uniform edge probability.For each value of n ,the algorithm was run on several random instances and the average number of improvement steps over these in-stances was used to generate this plot.Note that the number of improvement steps is almost linear in n .In all of our test cases,we found that the algorithm always found a branching of degree two or less,irrespective of how large n was or how bad the initial degree of the tree was.For problems of small size (n less than 100)the algorithm would often return a branching of degree one,i.e.,a Hamiltonian path.Fig.5shows the degree of the intermediate trees as the algorithm progresses on a 20,000-node random graph with uniform edge probability.Observe that the algorithm makes rapid progress initially since there are very few vertices of high degree.Once the degree becomes small,a larger number of improvements are needed to decrease the degree of the tree.Note that if one terminated the algorithm earlier (say,to meet a fixed deadline)then the current tree can be used without a big sacrifice on the quality.The shape of the curve shows that we get about 50%of the progress in about 10%of the time.300002500020000150001000050000706050403020100Fig.5.Degree of tree versus number of improvements on a 20,000node graph242Radha Krishnan and Balaji Raghavachari6.2Graphs with a Hidden Hamiltonian PathThe second class of graphs we tested were deliberately constructed to provide “bad”inputs to the algorithm to really test the algorithm’s power and efficacy.The graphs in this class were generated by first obtaining a random bipartite graph with n 1vertices on one side and n 2vertices on the other side (say n 1<n 2).The ratio of n 2/n 1was varied (while holding n =n 1+n 2constant).We finally added to each of these bipartite graphs a random Hamiltonian path.Without the “hidden”path that we added at the end,the degree of any branching in the bipartite graph is at least n 2/n 1,since vertices in the tree must alternate between the two sides.We wanted to see if the algorithm finds this hidden path.The algorithm performed very well even in these bad input instances,always returning no more than a degree 2tree in the end.As shown in Fig.6the number of improvement steps varies significantly with the ratio n 2/n 1,a measure of the badness of the input graph.As expected,the algorithm takes longer as the ratio gets closer to 1.We observed that in all cases,the number of improvements is a small multiple of n .100908070605040302010044004200400038003600340032003000280026002400Fig.6.The x-axis shows the ratio of n 2/n 1and the y-axis shows the average number of improvement steps for bipartite graphs with a total of 1000vertices.The input graphs for this plot were randomly generated bipartite graphs that were augmented with a hidden Hamiltonian path.7ConclusionsWe have presented an approximation algorithm for the directed minimum-degree spanning tree problem.We introduced a new notion of witness sets that works in directed graphs.Though we couldn’t prove a polynomial running time for our algorithm,it is likely to be fast in practice as shown by the experimental evi-dence.There are several open questions that follow from this work.Is it possible to implement our algorithm to run in polynomial time?Currently,the Steiner version of the DMDST problem does not have an approximation algorithm even with an O (log n )approximation ratio.The Directed Minimum-Degree Spanning Tree Problem243 We describe an example that shows why our current approach fails in the Steiner version of the DMDST problem.In this example,there is a high-degree node p of degree k.Its children are c1,...,c k.Each of these k children have an edge into vertex s,which is not in the current Steiner tree,and s has an edge into p.It can be verified that there is no improvement possible for vertex p.But,the degree of p can be reduced to k2 +1by connecting k2 of p’s children through s.In fact if the graph has a number of other extra nodes similar to s,the degree of p can be reduced even to2.This example shows that our algorithm does not guarantee any performance bound on the degree of the tree for the Steiner case. The reason that we were unable to apply Lemma1is that,the paths from c1 through c k(the nodes in W)to r intersect each other at s,before reaching p (which forms the set B),thus violating Condition2of the lemma.References1.A.Agrawal,P.Klein,and R.Ravi,How tough is the minimum-degree Steiner tree?A new approximate min-max equality,TR CS-91-49,Brown University,1991.2.M.F¨u rer and B.Raghavachari,An NC approximation algorithm for the mini-mum degree spanning tree problem,In Proc.of the28th Annual Allerton Conf.on Communication,Control and Computing,pages274–281,1990..M.F¨u rer and B.Raghavachari,Approximating the minimum degree spanning tree to within one from the optimal degree,In Proc.of3rd ACM-SIAM Symp.on Disc.Algorithms(SODA),pages317–324,1992.4.M.F¨u rer and B.Raghavachari,Approximating the minimum-degree Steiner treeto within one of optimal,J.Algorithms,17:409–423,1994.5.B.Gavish,Topological design of centralized computer networks–formulations andalgorithms,Networks,12:355–377,1982.6.D.E.Knuth,The Stanford GraphBase:a platform for combinatorial computing,Addison Wesley,1993.7.J.K¨o nemann and R.Ravi,A matter of degree:improved approximation algorithmsfor degree-bounded minimum spanning trees,In Proc.of32nd annual ACM Sym-posium on Theory of Computing(STOC),pages537-546,2000.wler,Combinatorial optimization:networks and matroids,Holt,Rinehartand Winston,New York,1976.9.B.Raghavachari,Algorithms forfinding low degree structures,In“Approximationalgorithms,”D.Hochbaum(ed.),PWS Publishers Inc.,pages266-295,1996. 10.R.Ravi,Rapid rumor ramification:approximating the minimum broadcast time,In Proc.of35th Annual IEEE Symposium on Foundations of Computer Science (FOCS),pages202–213,1994.11.R.Ravi,M.V.Marathe,S.S.Ravi,D.J.Rosenkrantz,and H.B.Hunt III,Manybirds with one stone:multi-objective approximation algorithms,In Proc.of25th Annual ACM Symp.on the Theory of Computing(STOC),pages438–447,1993.12.R.Ravi,B.Raghavachari,and P.Klein,Approximation through local optimality:designing networks with small degree,In Proc.of12th Conf.on Foundations of Software Tech.and p.Sci.(FSTTCS),pages279–290.Lect.Notes in Comp.Sci.652,1992.13.S.Win,On a connection between the existence of k-trees and the toughness of agraph,Graphs and Combinatorics,5:201-205,1989.。

最小生成树是否唯一工程技术计算机光盘软件与应用ComputerCDSoftwareandApplications2011年第6期最小生成树是否唯昊宇亮,孔凡龙(华中师范大学,武汉430079)摘要:最小生成树是图论的经典问题,求最小生成树以及求最小生成树的权值和得到了足够关注,而很少人去研究最小生成树是否唯一.对于给定的图而言,因为最小生成树的权值和是确定的,所以最小生成树不唯一当且仅当最小生成树的形状不唯一.本文提出判断最小生成树是否唯一的三种方法并且对它们给予分析和评价.关键词:最小生成树;唯一;prim算法;kruskal算法;次小生成树中图分类号:TP301.6文献标识码:A文章编号:1007-9599(2011)06—0072-02 MinimumSpanningTreeIftheUniqueWuYuliang,KongFanlong(CentralChinaNormalUniversity,Wuhan430079,China)Abstract:Minimumspanningtreeisaclassicproblemofgraphtheory,findtheminimu mspan ningtreeminimumspanningtree,andfindtheweightandgetenoughattention,andfewpeopletostudytheminimumspanni ngtreeisunique.Foragivengraphisconcemed,becausetheweightsandtheminimumspanningtreeisdetermined,SOtheminimu mspanningtreeisnotuniqueandonly iftheshapeoftheminimumspanningtreeisnotunique.Determinewhethertheproposedmini mumspanningtree,andtheonlythree waystogivetheiranalysisandevaluation.Keywords:Minimumspanningtree;Unique;Primalgorithm;Kruskalalgorithm;Smallspan ningtree一,三种方法判断最小生成树(MsT)是否唯一(一)借助prim算法提出的方法prim算法的基本思想是:首先选取图中的任意一个顶点v作为树的根加入生成树的集合Q中,之后不断往生成树中(集合0中)添加顶点w,顶点w满足与集合Q中的某个顶点之间有边,且该边上的权值是此时所有连接集合Q中的结点与不在集合Q中的结点的边中权值最小的,如此加入n一1个结点后,就形成了MST.按照上面的思想,可以知道最小生成树加入点的顺序.最小生成树是由点和边组成的,点在上边已经确定,我们还需确定边才能最终确定最小生成树.每次加入顶点W时(第一点除外),顶点W都满足与集合Q中的某个顶点有当时最小权的边,把集合Q中的那个顶点看作顶点W的前驱结点.那么到算法结束时,我们都能得到每个点(第一个点除外)的前驱结点,将每个点(第一个点除外)与它的前驱结点相连,就有n-1条边了,最小生成树构造完成.该算法的伪代码描述:Prim~ST(G,r)//求图G的以r为根的MST,通过求每个点的前驱结点来求MST{//初始化,Q一{r),除r外的所有前驱结点都为r且与Q的最短距离都是与r的距离.InitCandidateSet(…):for(k=O:k&lt;n-1:k十+)//要加入其它n一1个点{for(v:0:v&lt;n:v++)//枚举所有不在集合Q中的点(u,v)=SelectLishtEdge(…)://选取最小的边,其中u为已加入集合Q的点,v为没有加入集合Q中的点Q—Qu(v);//将点v加入集合Q中pre[v]:u://同时记录v的前驱结点ModifycandidateSet(…)://根据加入的v调整不在Q中的点与在Q中的最短距离)1在上述算法中,每次把集合Q外的最靠近集合Q中的点加入集合0,所以只有当集合Q外存在多个与集合Q中的点具有相同的最小边权值时,MST才有可能不唯一.当出现这种情况时,加入下一个点时枚举所有的这些点,最后判断每次得到的形状是否一样.这样固然可以,但时间复杂度太高了,这里提出如下方法.当有可能存在MST不唯一一时,考虑两个极端的MST.～'个是每次遇到多种选择时,都选择序号最小的点加入集合Q,另一个是每次遇到多种选择时,加入序号最大的点.如果这两个极端的MST完全一样,那么MST就是唯一的.这种方法的时空复杂度与prim算法的时空复杂度一样.所以时间复杂度为0(n2),空间复杂度为0(n2).(二)借助kruskal算法提出的方法kruskal算法的基本思想是:为使生成树上总的权值之和达到最小,应使每一条边上的权值尽可能小,自然应从权值最小的边选起,直至选出n一1条权值最小的边为止,然而这n-1条边必须不构成回路.所以每次加入最小的边之前判断是否会构成回路, 不构成回路就加入该边,构成回路就丢弃该边.按照以上思想,具体可以这样操作:用邻接表的数据结构存储每条边的信息,然后将每个点都看作一个单独的集合,从小到大枚举每条边,如果边的两端点不在同一个集合的话,就加入这条边,并且将这两个点所属的集合合并,否则,就不加这条边(因为同一个集合的点一定是可达的,然后加入该条边的话就一定会构成回路).算法结束后就有n-1条不会产生回路的边了,MST的形状也就出来了.Kruskal每一步都是加入最小权的边,所以当且仅当要加入的侯选边中存在两条最小权值且连接的是两个相同集合的边时(此时这两条边不能同时加入,取舍导致了最终结果的不唯一), MST才不唯一.所以在加入每条边时,都要判断后面是否存在与它权值相等且连接的是两相同集合的边.该算法的伪代码描述为:KruskalMST(G)//图的边存储在e中,MST的边全部存在E中{Initcandidateset(…)://初始化,一条边都没取,且每个顶点都有各自的集合Sort(e)://按边的权值从小到大排序for(k=l:k&lt;=m:k++)//m为边的条数.从小到大枚举每条边{if(Set(e[k].u)!=Set(e[k].v))//如果两端点在同一个集合中,一定会产生回路.{for(j=k+l::j++)//找后面与它权值相等且连接相同集合的边1—72—2011年第6期计算机光盘软件与应用ComputerCDSoftwareandApplications工程技术if(e[j].w==e[k].w)Lif(边J和边k连接的是两个相同的集合)输出MST不唯一,return:)elsebreak://如果发现连接的不是相同的集合立即退出循环)Union(e[k]:u,e[k].v)://将两端点所在集合合并为一个集合E[num++]=k://记录k为MST中的边))输出MST唯一://若没发现MST不唯一的情况,则MST唯一.】(三)借助次小生成树提出的方法次小生成树是所有生成树中权值和第二小的生成树.判断最小生成树是否唯一可以转化到判断次小生成树的权值和是否与最小生成树的权值和相等的问题上来.如果权值和相等,那么最小生成树不唯一,否则唯一.求次小生成树的基本思想是:先求最小生成树,然后枚举最小生成树的每一条边(总共有n-1条),删去后再求最小生成树,这样得到的所有生成树中最小的就是次小生成树.该算法的伪代码描述为:SST(G){suml=KruskalMST(G)://最小生成树的权值和for(sum2=maxint,i=0:i&lt;n-I:i++)//枚举删去MST中的每一条边(j=KruskalMST(G-E[i])://去掉MST中的第i条边后再求最小生成树if(j&lt;sum2)sum2=j://更新次小生成树的权值和}if(suml==sum2)MST不唯一elseMST唯一二,分析评价三种方法首先从时空复杂度分析这三种方法:第一种方法只是用prim算法求了两次MST,所以跟prim算法的时空复杂度是一样的,都是0(n2).在第二种方法中,kruskal的时间复杂度的瓶颈在于对边排序,后面对边扫描是0(e),而判断MST是否唯一时,排序是一样的,只是扫描时,每次加入一条边时都要向后判断是否存在一条与其权值相等且连接相同两集合的边,所以时问复杂度与边的权值相等的程度相关,最好的时候为0(elog2e),最坏的时候为0(e2),空间复杂度与kruskal算法一样0(e).第三种方法用了n次kruskal算法求MST,所以时间复杂度为0(ne]og2e),空间复杂度仍是0(e).然后从思考的难易比较,如果知道次小牛成树的话,不得不说第三种方法是最好想的,而第一种(第二种) 方法就需要对prim算法(kruskal算法)有深入的理解才能琢磨出.最后总整体来评价这三种算法,第三种算法是比较容易想的, 当想不到前面两种方法时,牺牲时间总比没有方法好;而第二种方法在图是稀疏图且相同边权的边不是很多的情况下,时空复杂度是相当可观的;而第一种方法在稠密图且相同边权很多的情况下,优势非常明显.三,结束语本文针对最小生成树是否唯一提出了三种解决方法,并且从多种角度分析它们的利弊以及说明它们的适用范围.参考文献:【1】R.L.Graham&amp;P.Hel1.MinimumSpanningTree.Annalsof theHistory.ofComputing,V olume7,Number1,January1985.43-57【2]ThomasH.Cormen.Introductiontoalgorithm[M}.高教出版社,2002【3】严蔚敏,陈文博.数据结构及应用算法教程【M】.清华大学出版社.2001【4】汪汀.最小生成树问题的拓展【z】.1012004国家集训队论文.2004【5】吴景岳.最小生成树算法及其应用【z】.IOI2004国家集训队论文.2004(上接第155页)取得了一些重大地突破,在我国高科技技术计划,国家重大自然科学基金等资金的支持下,我国从事汉字识别研究的同志们经过长期地艰苦努力才取得的成果,没有国家的支持,领导的关怀和同志们的帮助是无法完成的.但是,在手写体汉字识别的技术研究发展方向上,尤其是汉字技术真正的实用化与被广大用户所采纳接受的方面,还有许多问题需要我们进一步来解决,在我看来主要还包括三个方面:(一)识别系统的总体性能需要进一步进行提高.解决像报纸这种多栏目,并且排列位置复杂的印刷文本材料,在识别的同时最好能自动理解,在这同时利用自然语言进行理解并进行识别后进一步处理以提高汉字的识别率与适应性,降低系统由于误识而产生的错误等等.(二)系统软件的固化和系统各部分之间的衔接,以及系统的质量与性能的稳定还需进一步提高.(三)扩大识别算法的核心技术所能够应用的范围,开发更多的应用操作系统,并将我们的研究成果迅速转化成产品,逐步提高产品的商品化水平,使之能够走出国门,销往全世界.一73一这些都是我国手写体汉字识别系统亟须解决的问题,也将是我国识别技术今后可能发展的方向.五,结语汉字手写体的识别对于日渐流行的电脑技术来说的确是一个亟待改善的重要研究方向.本文提出了一种基于神经网络的汉字识别方法,在这同时也大致介绍了目前汉字识别的发展方向.当然,目前研究最多的还是基于神经网络的汉字手写体识别方法.参考文献:…孙广玲,唐降龙.基于识别结果反馈信息的闭环联机字符识别系统U1.计算机工程与应用,2002,22(2):112-114【21朱小燕,史一凡.基于反馈的手写体字符识别方法的研究U】. 计算机,2002,25(5):476-482【31王建平,潘乐,王金玲.基于反馈的手写体汉字识别系统U】.合肥工业大学:自然科学版,2008,31(7):1020—1025[作者简介]陈馥瑁(1984一),女,湖南武陵区人,硕士在读,湖南文理学院,职称为助教,研究方向为软件工程.。

第一章集合论、逻辑与算法基础1.1集合set（集合）power set（幂）complement of a set（补集）roster method（枚举法）universalset set（全集）symmetric difference（对称差集）set-builder method（集合构造方法）Venn diagrams（文氏图）ordered pair（有序对）subset（子集）union of sets（并集）Cartesian product（笛卡尔积）superset（父集）intersection of sets（交集）diagonal of a set（对角集）proper subset（真子集）disjoint sets（不相交集）ordered n-tuples（有序n元组）equal sets（相等集合）index set（索引集）n-flod Cartesian product（n次笛卡尔积）empty （null）set（空集）set difference（差集）bit string（位串）finite set（有限集）mutually disjoint（互不相交）length（长度）infinite set（无限集）pairwise disjoint（互不相交）singleton set（单体集合）relative complement（相对补集）1.2数理逻辑statement（命题）condition（条件）converse（逆命题）proposition（命题）biimplication（双向蕴涵）inverse（反命题）truth value（真值）biconditional（双向条件）contrapositive（逆否命题）negation（非）logical connectives（逻辑连接词）statement formula（命题公式）conjunction（合取）well-formed formulas（良态公式）formula（公式）disjunction（析取）tautology（重言式）implication（蕴涵）contradiction（矛盾式）1.3论证有效性proof（证明）modus tollens（否定法）disjunctive addition（析取加法）argument（论证）disjunctive syllogisms（析取三段论）conjunctive addition（合取加法）conclusion（结论）hypothetical syllogism（假设三段论）logically valid（逻辑有效）premise（前提）dilemma（二难推论）modus ponens（断言法）conjunctive simpli fications（合取简化）1.4量词与一阶逻辑statement logic（命题逻辑）predicate（谓词）domain（域）propositional logic（命题逻辑）propositional function（命题函数）free vricable（自由变量）n-place predicate（n位谓词）bound variable（约束变量）first-order logic（一阶逻辑）universal quantifier（全称量词）counterexample（反例）existential quantifier（存在量词）disproof（反证）1.5证明方法theorem（定理）indirect proof（间接证明）proof by contradiction（反证法）proof by direct method（直接证明方法）direct proof（直接证明）1.6 算法algorithm（算法）two-way selection（双路选择）list（列表）input（输入）if two-dimensional array（二维数组）output（输出）thenread precision（精度）else printuniqueness（唯一性）whilesubproprams（子程序）finiteness（有限性）do proceduregenerality（通用性）forfunction assignment operator（赋值运算符）begin constant polynomial（常量多项式）assignment statement（赋值语句）enddegree（次数）control structures（控制结构）return one-way selection（单路选择）arrays（数组）第三章关系与偏序集3.1关系与偏序集binary relation （二元关系）directed graph representation（有向图表示）digraph （有向图）relation （关系）vertex（顶点）adjacent to （与...相邻）R-related （R-相关）directed edge（有向边）adjacent from（从...相邻）related （相关）directed arc（有向弧）loop （环）empty relation （空关系）arrow diagram （矢量图）domain （域）universal relation （全称关系）directed graph（有向图）range （值域）image (映像) equivalence class （等价类）transitive closure （传递闭包）inverse （逆）R-class（R-类）directed walk （有向通路）composition （复合）reflexive （自反）R-equivalence class （R-等价类）walk （通路）partition （划分）vertices of the walk （通路顶点）transitive （传递）equivalence relation induced by the partition （划分推出的等价关系）terminal vertex （终止顶点）equivalence relation （等价关系）internal vertices （内部顶点）equality relation （相等性关系）reflexive closure （自反闭包）path （路径）congruence modulo m （模m同余）symmetric closure （对称闭包）3.2偏序集antisymmetric （反对称）lexicographic order （词典序）topological ordering （拓扑排序）partial order （偏序）dictionary order （字典序）upper bound（上界）partially ordered set （偏序集）closed （闭合）poset （偏序集）least upper bound（lub）（最小上界）covers （覆盖）lower bound （下界）dual （序偶）Hasse diagram （哈赛图）greatest lower bound （glb）（最大下界）comparable （可比）minimal element （极小元）lattice （格）linearly ordered set （线性有序集）maximal element （极大元）distributive （可分配性）totally ordered set （完全有序集）greatest element （最大元）complement （补元）chain （链）least element （最小元）Boolean algebra （布尔代数）product partial order （积偏序）compatible （兼容，相容）第四章矩阵与关系闭包4.1矩阵matrix（矩阵）diagonal matrix（对角矩阵）join（并）rectangular array（矩阵阵列）identity matrix（单位矩阵）Boolean meet（布尔交）element（元素）sum（和）meet（交）entry（项）difference（差）join of meet expression（相交表达式的并）equal（等于）multiplication（乘法）Boolean product（布尔积）square matrix（方阵）transpose（转置）product（积）zero matrix（零矩阵）symmetric（对称）diagonal element（对角元素）Boolean join（布尔并）4.2 关系矩阵与闭包matrix of a relation（关系矩阵）Warshall’s algorithm（Warshall算法）第五章函数5.1 函数function（函数）target（目标）onto（满射）well defined（合理定义）range（值域）surjective（满射）single valued（单值）numeric functions（数字函数）surjection（满射）image（映像）identity function（恒等函数）one-to-one correspondence（一一映射）preimage（预映像，前射，前像，原像）constant function（常数函数）bijective（双射）mapped（映射）one-one（单射函数）bijection（双射）domain（域）injective（内射）composition（复合）codomain（合域）injection（内射）5.2 特殊函数与集合的基数inverse function（逆函数）images（映像）cardinality（基数）left invertible（左可逆）direct image（直接映像）equivalent（等价）left inverse（左逆）inverse image（逆映像）equipotent（幂等）right invertible（右可逆）floor（下限）countable（可数）right inverse（右逆）ceiling（上限）uncountable（不可数）restriction（限制）floor function（弱取整函数）extension（扩展）ceiling function（强取整函数）5.3 序列与字符串sequence（序列）sum of the terms（项之和）index（索引）nth term of the sequence（序列第n项）summation symbol（求和符号）subscript（下标）finite sequence（有限序列）string（字符串）infinite sequence（无限序列）word（字符）integer sequence（整数序列）dummy variable（哑变量）alphabet（字母表）arithmetic progression（AP）（等差数列）lower limit（下限）length（长度）first term（首项）upper limit（上限）empty string（空字符串）common difference（公差）general term（通项）empty word（空串）geometric progression（GP）（等比数列）product of the terms（项之积）concatenation（接合）common ratio（公比）product symbol（求积符号）5.4 二元运算binary operation（二元运算）mathematical system（数学系统）idempotent（幂等）close under（在……下闭合）groupoid（群）idempotent semigroup（幂等半群）associative（可结合）identity（单位元）band（带）commutative（可交换）semigroup（半群）free semigroup generated by（由……生成的自由半群）Cayley multiplication table（Cayley乘法表）monoid（幺半群）free monoid generated by（由……生成的自由幺半群）Cayley table（Cayley表）transformation semigroup（变换半群）第六章同余6.1同余Congruent （同余）congruence class modulo （模m的同余类）6.3线性同余linear congruence in one variable （一个变量x的线性同余式）inverse （逆）residue representation （余数表示）unique modulo （唯一模）modular representation （模表示）round-robin tournament （循环赛）hashing （散列）hash address （散列地址）linear probing （线性探测）hash table （散列表）hashing function （散列函数）probe sequence （探测数列）hash function （散列函数）collision （冲突）double hashing （双重散列）6.4特殊同余定理Euler phi-function （欧拉phi函数）ciphertext （密文）encryption key （加密钥匙）plaintext（明文）decryption function （加密函数）decryption key （揭秘钥匙）第十章图论10.1图的定义与符号graph （图）parallel （平行边）arc（弧）set of vertices （顶点集合）isolated vertex （顶点孤立）Staring vertex （始点）set of edges （边集）degree （度）terminating vertex （终点）incidence function （关联函数）k-regular graph （k-正则图）in-degree （入度）end vertices （端点）even degree vertex （偶度顶点）out-degree （出度）endpoints（端点）odd degree vertex （奇度顶点）simple graph （简单图）incident （关联）degree sequence (度数列) complete graph（完全图）Adjacent （相邻）directed graph（有向图）triangle （三角形）loop （环）digraph （有向图）bipartite graph （二分图）incidence table （关联表）directed edge（有向边）Bipartition （二分）complete bipartite （完全二分）subgraph （子图）Complement of a graph（补图）Ramsey number （Ramsey数）10.2通路，路径与圈walk （通路）initial vertex （始点）terminal vertex（终点）directed walk （有向通路）length of a walk （通路长度）length of a directed walk （有向通路长度）u-v walk （u-v通路）u-v directed walk （u-v 有向通路）closed walk （闭合通路）closed directed walk （闭合有向通路）open walk （开放通路）open directed walk （开放有向通路）trail （迹) path （路径）trivial walk （平凡通路）trivial path （平凡路径）trivial trail （平凡迹）nontrivial walk （非平凡通路）nontrivial path （非平凡路径）nontrivial trial （非平凡迹）circuit （回路）cycle （圈）k-cycle （k圈）even cycle （偶数圈）odd cycle （奇数圈）subwalk （子通路）reduction of P by Q（P用Q简化）decomposition （分解）connected （连接）connected graph （连接图，连通图）disconnected graph （不连接图，不连通图）component （分支）distance （距离）matching （匹配）M-saturated （M-饱和）M-unsaturated （M-不饱和）perfect matching （完美匹配）maximum matching（最大匹配）neighbors （邻居）10.3图的矩阵表示adjacency （相邻矩阵）incidence matrix（关联矩阵）10.4特殊回路Euler circuit （欧拉回路）Euler trail （欧拉迹）Hamiltonian graph （汉密尔顿图）Euler graph （欧拉图）Hamiltonian cycle （汉密尔顿圈）Hamiltonian path （汉密尔顿路径）10.5同构isomorphic （同构）different （不同）10.6图算法weight （权）weighted graph （加权图）weight matrix （加权矩阵）length of a path （路径长度）shortest path algorithm （最短路径算法）greedy algorithm （贪婪算法）topological ordering （拓扑排序）immediate successor （直接后继）queue （队列）rear （队尾）10.7 平面图和图着色planar graph（平面图）exterior face（外面）proper vertex coloring（正常顶点着色）plane graph（平面图）interior face（内面）chromatic number（色数）planar representation of a graph（图的平面表示）subdivision of a graph（图的细分）edge coloring（边着色）faces（面）homeomorphic（同胚）proper edge coloring（正常边着色）boundary（边界）vertex coloring（顶点着色）chromatic index（色索引）第十一章树与网络11.1 树tree（树）acyclic graph（无环图）11.2 有根树rooted tree（有根树）binary tree（二叉树）postorder traversal（后序遍历）lever（层）trivial tree（平凡树）inorder sequence（中序顺序）child（子节点）left child（左子节点）preorder sequence（前序顺序）terminal vertex（终点）right child（右子节点）postorder sequence（后序顺序）leaf（叶子）left subtree（左子树）binary search tree（二叉搜索树）internal vertex（内顶点）right subtree（右子树）infix（中缀）descendant（后代）full binary tree（完全二叉树）prefix（前缀）ordered rooted tree（有序有根树）inorder traversal（中序遍历）postfix（后缀）height（高度）preorder traversal（前序遍历）expression tree（表达式树）11.3 生成树spanning tree（生成树）minimal spanning tree（最小生成树）weighted tree（加权树）Prim’s algorithm（Prim算法）weight（权）11.4 网络single-source，single-sink network（单元单汇网络）flow conservation（流量守恒）quasipath（拟路径）source（源）flow in edge（边流）forward arc（正向弧）target（目标）flow into（流入）backward arc（反向弧）sink（汇）flow out of（流出）slack（松弛）s-t network（s-t网络）conservation of flow（流量守恒）F-saturated（F-饱和）capacity（容量）value of a flow（流值）F-unsaturated（F-不饱和）transport network（传输网络）s-t cut of network（网络的s-t分割）flow augmenting（流增广）network（网络）capacity of an s-t cut（s-t分割容量）patent（父节点）flow（流）minimal cut（最小分割）immediate predecessor（直接前驱）capacity constraint（容量限制）maximal flow（最大流）。

Algorithm Design TechniquesAssignment3:Solutions(1)Hamiltonian Path.(a)Longest Path ProblemThe Longest Path Problem is in NP.Given a solution path P,we justcheck that P consists of at least k edges,and that these edges form apath(where no vertex is used more than once).This verification can bedone in polynomial time.The reduction follows directly from Hamiltonian Path.Given an instanceof Hamiltonian Path on a graph G=(V,E).We create an instance of thelongest path problem G ,k as follows.We use exactly the same graph,i.e G =G and we set k=|V|−1.Then there exists a simple path oflength k in G iffG contains a Hamiltonian path.(b)Minimum Leaf Spanning treeThe Minimum Leaf Spanning tree is in NP.Clearly the certificate is atree of k leaves,which can be verified in linear time.Again,the reduction follows directly from Hamiltonian Path.Given aninstance of Hamiltonian Path on a graph G=(V,E).We create an in-stance of the minimum leaf spanning tree problem G ,k as follows.Again,we use exactly the same graph,i.e G =G but now we set k=2.A treewith2leaves is a path,so a spanning tree with two leaves is a Hamilton-ian Path in the graph.So there exists a Hamiltonian path iffthere existsa spanning tree with2leaves.(2)Hitting Set Problem.The Hitting Set problem is in NP.To check a solution a∗1,...,a∗kwe just seeif every set B j is hit by at least one of the a∗i.We use a reduction from Set Cover to show NP-completeness.Given sets S1,...,S n and a ground set W={w1,...,w m}of elements to cover,let a1,...,a n represent the sets and let B1,...,B m represent the elements.We say that a i hits B j if and only if set S i contains element w j.It follows that12there is a hitting set of size at most k if and only if there is a set cover of size at most k .This is a polynomial reduction.We use a reduction from Partition to show NP-completeness.We have inte-gers x 1,...,x n and we want to find a subset S ⊂[n ]with i ∈S x i = i/∈S x i .To set this up as a zero-weight cycle problem we take a directed cycle with n arcs,one for each integer.We now make two copies of each arc i .One copy has weight x i and the other has weight −x i .So any directed cycle in G uses exactly one the type i arcs.Let S be the set of integers where we use their positive arcs.Thus the weight of the corresponding cycle is i ∈S x i − i/∈S x i .Clearly,this equals zero if and only if we have the desired partition.This is a polynomial reduction.(3)Dominating Set.Dominating Set is in NP.To check a proposed solution S ⊂V ,we simply have to check that any vertex not in S is adjacent to some vertex in S .We use a reduction from Set Cover to show NP-completeness.Given sets S 1,...,S n and a ground set W ={w 1,...,w m }of elements to cover,we create a graph as follows.There is a vertex v i for each set S i and a vertex u j for each element w j .There is an edge (v i ,w j )if and only if w j is in set S i .Finally we add an edge (v i ,v i )for each pair of sets S i and S j -we do this because then every v i are more useful than any u j in building a dominating set.It is then easy to see that there is a dominating set of size at most k in G if and only if there is a set cover of size at most k .This is a polynomial reduction.(4)Feedback vertex set.The Feedback vertex set problem is in NP.To check a proposed solution,X ⊆V ,we just verify that G −X forms an acyclic graph.This verification can be done in polynomial time.We use a reduction from Vertex Cover problem to show NP-Completeness.Take an instance of vertex cover in an undirected graph G U =(V ,E ).We now replace each edge in the undirected graph with two directed edges,a for-ward edge and a backward edge to obtain the directed graph,G D =(V ,A ).So we now need to prove that,X ⊆V is a vertex cover in G U iffX forms a feedback vertex set in G D .Assume X is a vertex cover of G U .Then by definition,every edge of G U must be incident with at least one vertex of X .Clearly,every directed edge3of G D should also be incident with at least one vertex of X .So every cycle in G D must include a vertex of X .Now,assume that X is a feedback vertex set of the directed graph G D .Then by definition,every cycle in G D must include a vertex of X .Consider any cycle of length 2.This is just a pair of directed edges between two vertices.So X must contain at least one vertex for each cycle of length 2in G D .But,by our construction,for every edge in G U joining two vertices,G D contains a cycle of length 2between the same pair of vertices.So X contains at least one of these two vertices for each edge in G U .So X is a vertex cover of G U .(5)Bartering.This problem is in NP.To check a feasible exchange of subset S of items of player I and subset T of items of player II,we simply check that I prefers T to S and II prefers S to T .We use a reduction from the Knapsack problem to show NP-completeness.We have n items of weights w 1,...,w n and values v 1,...,v n :Is there a set of items of weight at most W and value at least V .We set up a barter economy with just 2people.Person I has n items that she values at w 1,...,w n ;Person II values these items at v 1,...,v n .Person II has just one item that he values at V −1;Person I values this item at W +1.So a trade can take place if I has a subset of item of weight at most W and that has a value of at least V .This is a polynomial reduction.(6)Galactic Shortest Paths.This problem is in NP.To check a proposed path P ,we just check that it has length at most L and risk value at most R .We use a reduction from Partition to show NP-completeness.Again,we have integers x 1,...,x n and we want to find a subset S ⊂[n ]with i ∈S x i = i/∈S x i .To set this up as a path problem we take a directed path (with end vertices s and t )with n arcs,one for each integer.We now make two copies of each arc i .The first copy has length x i and risk value 0;the second copy has length 0and risk value x i .So any s −t path P in G uses exactly one the type i arcs.Let S be the set of integers where we use their first copy.Thus the length of the path is i ∈S x i ;the risk of this path is risk values on those integers where we use the second copy of their arcs,so the risk is i/∈S x i .So set R =L =12i x i .Then we have a path of length at most L and risk at most R if an only if we have a valid partition.This is a polynomial reduction.。

算法设计与分析◎基本概念算法是解题方案的准确而完整的描述，它是一些步骤组成的一个过程。

算法不等于程序，它不需要考虑具体的机器和语言。

数据结构程序加工处理的数据在计算机中的存放方式。

算法是对数据加工的步骤。

程序就是在数据的某种特定的表示方法和结构的基础上对抽象算法的具体描述。

3 算法的特征有穷性( finiteness)：一个算法必须在有限步骤之内完成。

2) 确定性(definiteness)：算法中的每一步必须明确，不能模棱两可。

3) 能行性(effectiveness)：算法中的每一步都是可以实现的，或者可以分解为可执行的的基本操作。

4) 输入(input)：有零个或多个输入。

5) 输出(output)：有一个或多个输出。

7 算法的正确性评价一个算法，正确性是一个永恒的标准。

算法的正确依赖于所用理论的正确. 但是，理论正确的算法未必能得到正确结果，逻辑正确未必能得到正确结果。

计算工具的精度对结果会有较大影响。

2 算法的设计步骤1) 问题的描述2) 模型的建立3) 算法设计4) 算法分析5) 算法的实现6) 验证算法正确性6) 验证算法正确性目前是通过验证表达该算法的程序的正确性来实现。

虽然这两者不完全一致，但因目前要证明算法的正确性仍然有困难,所以上述方法仍然是主要方法。

验证程序的正确性采用程序测试的方法。

经测试验证是正确的程序，在很大程度上可以相信该程序及其算法的正确性。

1 算法的复杂度算法复杂度主要指时间复杂度和空间复杂度。

算法的时间复杂度(Time complexity): 指执行算法的计算工作量，即算法的时间代价。

算法的空间复杂度(Space complexity): 指算法执行过程中需要存储空间的大小，即算法的空间代价.算法的时间复杂度的度量基本运算:基本运算应与使用的计算机及语言无关。

基本运算次数应与算法运算总次数大体上成比例。

问题规模: 算法所执行的基本运算的次数不仅与算法本身有关，还与问题的规模有关。