图论总结(超强大)78408

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

1.6.3.网络流Flow network

1.6.3.1.最大流Maximum flow

1.6.3.1.1.基本算法Basic algorithms

1.6.3.1.1.1.Ford-Fulkerson method

1.6.3.1.1.1.1.Edmonds-Karp algorithm

1.6.3.1.1.1.1.1.Minimum length path

1.6.3.1.1.1.1.

2.Maximum capability path

1.6.3.1.1.

2.预流推进算法Preflow push method

1.6.3.1.1.

2.1.Push-relabel

1.6.3.1.1.

2.2.Relabel-to-front

1.6.3.1.1.3.Dinic method

1.6.3.1.

2.扩展模型Extended models

1.6.3.1.

2.1.有上下界的流问题

1.6.3.

2.最小费用流Minimum cost flow

1.6.3.

2.1.找最小费用路Finding minimum cost path

1.6.3.

2.2.找负权圈Finding negative circle

1.6.3.

2.

3.网络单纯形Network simplex algorithm

1.6.4.匹配Matching

1.6.4.1.二分图Bipartite Graph

1.6.4.1.1.无权图-匈牙利算法Unweighted - Hopcroft and Karp algorithm

1.6.4.1.

2.带权图-KM算法Weighted –Kuhn-Munkres(KM) algorithm

1.6.4.

2.一般图General Graph

1.6.4.

2.1.无权图-带花树算法Unweighted - Blossom (Edmonds)

1.图论Graph Theory

1.1.定义与术语Definition and Glossary

1.1.1.图与网络Graph and Network

二元组()

,V E称为图(graph)。V为结点(node)或顶点(vertex)集。E为V中结点之间的边的集合。

点对(),u v称为边(edge)或称弧(arc)，其中,u v V

∈，称,u v是相邻的(adjacent)，称u,v与边(),u v相关联(incident)或相邻。

若边的点对(),u v有序则称为有向(directed)边，其中u称为头(head)，v称为尾(tail)。所形成的图称有向图(directed graph)。为对于u来说(),u v是出边(outgoing arc)；对于v来说(),u v是入边(incoming arc)。反之，若边的点对无序则称为无向(undirected)边，所形成的图称无向图(undirected graph)。

若图的边有一个权值(weight)，则称为赋权边，所形成的图称赋权图(weighted graph)或网络(network)。用三元组G(V,E,W)表示网络。其中W表示权集，它的元素与边集E一一对应。

满足||||log||

E V V

<的图，称为稀疏(sparse)图；反之，称为稠密(dense)图。

1.1.

2.图的术语Glossary of Graph

阶(order)：图G中顶点集V的大小称作图G的阶。

环(loop)：若一条边的两个顶点为同一顶点，则此边称作环。

简单图(simple graph)：没有环、且没有多重弧的图称作简单图。

定向图：对无向图G的每条无向边指定一个方向得到的有向图。

底图：把一个有向图的每一条有向边的方向都去掉得到的无向图。

逆图：把一个有向图的每条边都反向由此得到的有向图。

竞赛图(tournament)：有向图的底图是无向完全图，则此有向图是竞赛图。

邻域(neighborhood)：在图中与u 相邻的点的集合{|,(,)}v v V u v E ∈∈，称为u 的邻域，记为()N u 。

度：

度(degree)：一个顶点的度是指与该边相关联的边的条数，顶点v 的度记作deg(v)。握手定理：无向图：deg()2||v V

v E ∈=∑；有向图：deg ()deg ()v V

v V

v v +-∈∈=∑∑。

入度(indegree)：在有向图中，一个顶点v 的入度是指与该边相关联的入边(即边的尾是v)的条数，记作deg ()v +。

出度(outdegree)：在有向图中，一个顶点的出度是指与该边相关联的出边(即边的头是v)的条数，记作deg ()v -。

孤立点(isolated vertex)：度为0的点。叶(leaf)：度为1的点。

源(source)：有向图中，deg ()v +=0 的点。汇(sink)：有向图中，deg ()v -=0的点。 奇点(odd vertex)：度为奇数的点。偶点(even vertex)：度为偶数的点。 子图：

子图(sub-graph)：G'称作图G 的子图如果(')()V G V G ?以及(')()E G E G ?。

生成子图(spanning sub-graph)：即包含G 的所有顶点的连通子图，即满足条件

(')()V G V G =的G 的子图G ’。

生成树(spanning tree)：设T 是图G 的一个子图，如果T 是一棵树，且()()V T V G =，则称T 是G 的一个生成树。即G 的生成子图，且子图为树。

点导出子图(induced subgraph)：设)(G V V ?'，以V '为顶点集，以两端点均在V '中的边的全体为边集所组成的子图，称为G 的由顶点集V '导出的子图，简称为G 的点导出子图，记为

[]G V '。

边导出子图(edge-induced subgraph)：设)(G E E ?'，以E '为顶点集，以两端点均在E '中

的边的全体为边集所组成的子图，称为G 的由边集E '导出的子图，简称为G 的边导出子图，记为][E G '。

图的补图(complement)：设G 是一个图，以)(G V 为顶点集，以{(,)|(,)()}u v u v E G ?为边集的图称为G 的补图，记为G 。

点集的补集：记 ''V V V =-为点集'V 的补集。 特殊的图：

零图(null graph)：E =?，即只有孤立点的图。n 阶零图记为n N 。 平凡图(trivial graph)：一阶零图。 空图(empty graph)：V E ==?的图。

有向无环图(directed acyclic graph(DAG))：有向的无环的图。

完全图(complete graph)：完全图是指每一对不同顶点间都有边相连的的无向图，n 阶完全图常记作n K 。

二分图（bipartite graph ）：若图G 的顶点集可划分为两个非空子集X 和Y ，即V X Y =?且X Y ?=?，且每一条边都有一个顶点在X 中，而另一个顶点在Y 中，那么这样的图称作二分图。

完全二分图(complete bipartite graph)：二分图G 中若任意两个X 和Y 中的顶点都有边相连，则这样的图称作完全二分图。若||,||X m Y n ==，则完全二分图G 记作,m n K 。

正则图(regular graph)：如果图中所有顶点的度皆相等，则此图称为正则图。

1.1.3. 路径与回路 Path and Cycle

途径(walk)：图G 中一个点边交替出现的序列0112

k k i i i i i i p v e v e e v =，满足,j j i i v V e E ∈∈，

1(,)j j j i i i e v v -=。

迹(trail)：边不重复的途径。

路(path)：顶点不重复的迹。

简单图中的路可以完全用顶点来表示，k i i i v v v P 10=。 若1m p p =，称闭的(closed)；反之，称为开的(open)。 闭途径(closed walk)：起点和终点相同的途径。

闭迹(closed trail)：起点和终点相同的迹，也称为回路(circuit)。 圈(cycle)：起点和终点相同的路。

途径（闭途径）、迹（闭迹）、路（圈）上所含的边的个数称为它的长度(length)。 简单图G 中长度为奇数和偶数的圈分别称为奇圈(odd cycle)和偶圈(even cycle)。 对任意,()u v V G ∈，从x 到y 的具有最小长度的路称为x 到y 的最短路(shortest path)，其长度称为x 到y 的距离(distance)，记为(,)G d u v 。

图G 的直径(diameter)：max{(,)|,()}G D d u v u v V G =?∈。

简单图G 中最短圈的长度称为图G 的围长(girth)，最长圈的长度称为图G 的周长(perimeter)。

1.1.4. 连通性 Connectivity

连通(connected)：在图G 中，两个顶点间，至少存在一条路径，称两个顶点连通的(connected)；反之，称非连通(unconnected)。

强连通(strongly connected)：在有向图G 中，两个顶点间，至少存在一条路径，称两个顶点强连通。

弱连通(weakly connected)：在有向图G 中，两个顶点间，若不考虑G 中边的方向的图才连通的，称原有向图为弱连通。

连通图(connected graph)：图G 中任二顶点都连通。

连通分量或连通分支(connected branch, component)：非连通无向图的极大连通子图

(maximally connected sub-graph)。具体说，若图G 的顶点集V (G )可划分为若干非空子集

ωV V V ,,,21 ，使得两顶点属于同一子集当且仅当它们在G 中连通，则称每个子图][i V G 为图G

的一个连通分支（ω,,2,1 =i ）。图G 的连通分支是G 的一个极大连通子图。图G 连通当且仅当1＝ω。

强连通分量(strongly connected branch)：非强连通图有向图的极大强连通子图。 割(cut)：

点割集(vertex cut)：点集'V V ∈，若G 删除了'V 后不连通，但删除了'V 的任意真子集后G 仍然连通。则称'V 点割集。若某一结点就构成就了点割集，则称此结点割点(cut vertex)。点数最少的点割集称为点连通度k(G)。

边割集(edge cut set)：边集'E E ∈，若G 删除了'E 后不连通，但删除了'E 的任意真子集后G 仍然连通。则称'E 点割集。若某一边就构成就了边割集，则称此结点割边(cut edge)或桥(bridge)。边数最少的边割集称为边连通度k ’(G)。

记号],[S S '表示一端在S 中另一端在S '中的所有边的集合。 块(block)是指没有割点的极大连通子图。

1.1.5. 图论中特殊的集合 Sets in graph

点覆盖(集)(vertex covering (set))：'V V ∈，满足对于e E ?∈，有'v V ?∈，v 关联e 。即一个点集，使得所有边至少有一个端点在集合里。或者说是“点” 覆盖了所有“边”。极小点覆盖(minimal vertex covering)：本身为点覆盖，其真子集都不是。最小点覆盖(minimum vertex covering)：点最少的点覆盖。点覆盖数(vertex covering number)：最小点覆盖的点数，记为()V G α

一般说覆盖集就是指点覆盖集。

边覆盖(集)(edge covering (set))：'E E ∈，满足对于v V ?∈，有'e E ?∈，e 关联v 。即一个边集，使得所有点都与集合里的边邻接。或者说是“边” 覆盖了所有“点”。 极小边覆盖(minimal edge covering)：本身是边覆盖，其真子集都不是。最小边覆盖(minimum edge

covering)：边最少的边覆盖。边覆盖数(edge covering number)：最小边覆盖的边数，记为()E G α。

独立集(independent set)：'V V ∈，满足对于,'u v V ?∈，有(,)u v E ?。即一个点集，集合中任两个结点不相邻，则称'V 为独立集。或者说是导出的子图是零图（没有边）的点集。极大独立集(maximal independent set)：本身为独立集，再加入任何点都不是。最大独立集(maximum independent set)：点最多的独立集。独立数(independent number)：最大独立集的点数，记为()V G β。

团(clique)：'V V ∈，满足对于,'u v V ?∈，有(,)u v E ∈。即一个点集，集合中任两个结点相邻。或者说是导出的子图是完全图的点集。极大团(maximal clique)：本身为团，再加入任何点都不是。最大团(maximum clique)：点最多的团。团数(clique number)：最大团的点数，记为()G ω。

边独立集(edge independent set)：'E E ∈，满足对于,'e f E ?∈，有,e f 不邻接。即一个边集，满足边集中的任两边不邻接。极大边独立集(maximal edge independent set)：本身为边独立集，再加入任何边都不是。最大边独立集(maximum edge independent set)：边最多的边独立集。边独立数(edge independent number)：最大边独立集的边数，记为()E G β。

边独立集又称匹配(matching)，相应的有极大匹配(maximal matching)，最大匹配(maximum matching)，匹配数(matching number)。

支配集(dominating set)：'V V ∈，满足对于'u V V ?∈-，有'v V ?∈，(,)u v E ∈。即一个点集，使得所有其他点至少有一个相邻点在集合里。或者说是一部分的“点”支配了所有“点”。 极小支配集(minimal dominating set)：本身为支配集，其真子集都不是。最小支配集(minimum dominating set)：点最少的支配集。支配数(dominating number)：最小支配集的点数，记为

()V G γ。

边支配集(edge dominating set)：'E E ∈，满足对于'e E E ?∈-，有'f E ?∈，,e f 邻接。即一个边集，使得所有边至少有一条邻接边在集合里。或者说是一部分的“边”支配了所有“边”。极小边支配集(minimal edge dominating set)：本身是边支配集，其真子集都不是。最小边支配集(minimum edge dominating set)：边最少的边支配集。边支配数(edge dominating number)：

最小边支配集的边数，记为()E G γ。

定理：若G 中无孤立点，D 为支配集，则D=V(G)-D 也是一个支配集。 定理：一个独立集是极大独立集，当且仅当它是支配集。 关系：

定理：无向图G 无孤立点，1V 是极小支配集，则存在2V 是极小支配集，且12V V ?=?。 定理：无向图G 无孤立点，'V 是极大独立集，则'V 是极小支配集。逆命题不成立。

()()V V G G βγ≥。

定理：连通图中，'V 是点覆盖，则'V 是支配集。极小点覆盖不一定是极小支配集。支配集不一定是点覆盖。

定理：无向图G 无孤立点，'V 是(极，最小)点覆盖，充要于'V V -是(极，最大)独立集。

()()||V V G G V αβ+=。

定理：无向图G ，'V 是G 的(极，最大)团，充要于'V 是G 的(极，最大)独立集。()()V G G ωβ=。 由上述定理知，()V G α，()V G β，()G ω三者互相确定，但都是NPC 的。但是二分图中，点覆盖数是匹配数。

M 是匹配，W 是边覆盖，N 是点覆盖，Y 是点独立集。 定理：无向图G 无孤立点，|M|<=|N|,|Y|<=|W|

定理：无向图G 无孤立点，()()||E E G G V αβ+=。先取一个最大匹配M ，1条边盖两个点；剩下的一个未盖点要用一条边来覆盖，边覆盖数=|M| +(|V|-2|M|)= |V|-|M|。

定理：无向图G 无孤立点，()E G β=()V G α，()V G β=()E G α。 定理：无向图G 无孤立点，()G ω=()V G β。 求匹配数是P 的，所以边覆盖和匹配都是易求的。

最小路径覆盖(path covering)：是“路径”覆盖“点”，即用尽量少的不相交简单路径覆盖有向无环图G的所有顶点，即每个顶点严格属于一条路径。路径的长度可能为0(单个点)。

最小路径覆盖数＝G的点数－最小路径覆盖中的边数。应该使得最小路径覆盖中的边数尽量多，但是又不能让两条边在同一个顶点相交。拆点：将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息，从X部往Y部引边。所有边的方向都是由X部到Y部。因此，所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。因此由最小路径覆盖数＝原图G的顶点数－二分图的最大匹配数便可以得解。

1.1.6.匹配Matching

匹配(matching)是一个边集，满足边集中的边两两不邻接。匹配又称边独立集(edge independent set)。

在匹配中的点称为匹配点(matched vertex)或饱和点；反之，称为未匹配点(unmatched vertex)或未饱和点。

交错轨(alternating path)是图的一条简单路径，满足任意相邻的两条边，一条在匹配内，一条不在匹配内。

增广轨(augmenting path)：是一个始点与终点都为未匹配点的交错轨。

最大匹配(maximum matching)是具有最多边的匹配。

匹配数(matching number)是最大匹配的大小。

完美匹配(perfect matching)是匹配了所有点的匹配。

完备匹配(complete matching)是匹配了二分图较小部份的所有点的匹配。

增广轨定理：一个匹配是最大匹配当且仅当没有增广轨。

综上，在二分图中，最小覆盖数=最大匹配数。边覆盖数=最大独立数=|V|-最大匹配数。

1.1.7.树Tree

G=(V, E)为一个图，则下列命题等价：(1)G是一棵树；(2)G连通，且|E|=|V|-1；(3)G无圈，

且|E|=|V|-1；(4)G 的任何两个顶点之间存在唯一的一条路；(5)G 连通，且将G 的任何一条弧删去之后，该图成为非连通图；(6)G 无圈，且在G 的任何两个不相邻顶点之间加入一条弧之后，该图正好含有一个圈。

Cayley 公式：在n 阶完全图n K 中，不同生成树的个数为2n n -。

1.1.8. 组合优化 Combinatorial optimization

从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为(最)优化(optimization)问题。

所谓组合(最)优化(combinatorial optimization)又称离散优化(discrete optimization)，它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等. 这类问题可用数学模型描述为：

min ()

..()0,f x s t g x x D

≥∈

其中D 表示有限个点组成的集合(定义域)，f 为目标函数,{|,()0}F x x D g x =∈≥为可行域。

网络优化(network optimization)就是研究与(赋权)图有关的组合优化问题。

常见的P 类网络优化问题：最小生成树，最短路，最大流，最小费用最大流，最大匹配，中国邮路问题。

常见的NP 类网络优化问题：旅行商问题。

参考文献：

[1]Dictionary of Algorithms and Data Structures NIST ，https://www.wendangku.net/doc/542367338.html,/dads/ [2]Wikipedia ，https://www.wendangku.net/doc/542367338.html,/wiki/Graph_theory [3]谢金星，清华大学数学科学系<<网络优化>>讲义 https://www.wendangku.net/doc/542367338.html,/~jxie/courses/netopt

1.2. 图的表示 Expressions of graph

下面介绍几种表示图的数据结构。并统一用下图做例子：

1.2.1. 邻接矩阵 Adjacency matrix

用二元数组(,)A u v ，来表示图。这种表示法一般用于稠密图。当图不是简单图，邻接矩阵法不能用。

在无权图中，若边(,)u v 存在，(,)A u v =1；否则(,)A u v =0。

,,0,(,)(){0,1},1,(,)n n

u v n n u v

u v E

A a a u v E ????=∈=?

∈?

无权图的例子：

110000010010000010100110??

????????

??????

在有权图中, 若边(,)u v 存在,则(,)A u v 为它的权值；否则人为的规定(,)A u v =∞或-∞。∞是一个足够大的数。

,,(,),(,)(),,(,)u v n n u v

w u v u v E

A a a u v E ???==?

∞∈?

无向图中，邻接矩阵是按矩阵副对角线对称的。

3

5

1.2.2. 关联矩阵 Incidence matrix

用二元数组(,)B u k ，来表示无权有向图。一般不用这种表示法。

若边k 与点u 关联，若k 是u 的出边，则(,)B u k =1；若k 是u 的入边(,)B u k =-1；否则

(,)B u k =0。

,,1,,(,),(){1,0,1},1,,(,)0,n m u k n m u k

v V k u v E B b b v V k v u E else

???∈=∈??=∈-=-?∈=∈???

，

无权图的例子：

1100000010110000010110100010110100000111????--????---??--????-??

1.2.3. 邻接表 Adjacency list

图的邻接表是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧的集合，含有终点，权值等信息。

对于有向图G=(V,E)，一般用A(v)表示节点v 的邻接表，即节点v 的所有出弧构成的集合或链表(实际上只需要列出弧的另一个端点，即弧的尾)。

一般图都适用。邻接表方法增加或删除一条弧所需的计算工作量很少。 有权图的例子：A(1)={2,3}，A(2)={4}，A(3)={2}，A(4)={3,5}，A(5)={3,4}

1.2.4.弧表Arc list

所谓图的弧表, 也就是图的弧集合中的所有有序对以表格的方式来表示。弧表表示法直接列出所有弧的起点和终点，以及权值。一般用于稀疏图。缺点是无法通过一些信息(起点，终点)定位一条边。

用S(i),F(i),W(i)分别表示起点，终点，权值。

有权图的例子：

1.2.5.星形表示Star

星形表示法就是对弧表的缺点的改进，使之可以通过起点或终点定位边。由于很多时候，算法只需事先知道起点，通过枚举边扩展，而不需要事先知道终点；如图的遍历，松弛操作。

按定位方式，又分前向星形(forwards star)与反向星形(reverse star)。前向星形：通过起点定位边。反向星形：通过终点定位边。实际上，反向星形几乎没用。故本文只讨论前向星形。

通常有两种方法实现这种对弧表改进：边排序法，链表法。

边排序法：把弧表按起点为第一关键字，终点为第二关键字来排序。排序用不用额外空间的快速排序O(mlogm)或用额外空间O(m)的计数排序O(m)均可。之后用数组last(u)记录以结点u为起点的最后一条边的编号，并规定last(0)=0。这样以结点u为起点的边编号就是last(u-1)+1到last(u)。有权图的例子：

就是将相同结点的边用链表串起来。last(u)存以u为起点的最后一条边的编号。有权图的例子：

星形表示法的优点是占用的存贮空间较少。一般图都适用。边排序法的优点是已知起点和终点的情况下可以精确定位边，容易在起点定位的范围内二分查找终点，在反向边的定位中常用；缺点是代码麻烦，时间抑或空间上都有额外开销。链表法的优点很多，不仅代码简单，而且没有太多的时空开销，对于反向边的定位只要多加一个数据项纪录下反向边即可；除了终点定位性，几乎没缺点。

参考文献：

[1]谢金星，清华大学数学科学系<<网络优化>>讲义 https://www.wendangku.net/doc/542367338.html,/~jxie/courses/netopt [2]刘汝佳，黄亮，<<算法艺术与信息学竞赛>>，P60

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.桥一定是DFS 树中的边；2.桥一定不在圈中。

圈是由一条后向边(u,v)与DFS 树中u 到v 的路径组成。也就是说u 到v 的路径上的边都不可能是桥，应该给以标记。记f(x)为x 与其子孙的后向边所连到的最老祖先(深度最浅)，表示x 到f(x) 上的边均不为桥。然而维护f(x)比较麻烦，其实只要知道f(x)的拓扑序数就可以了。所谓拓扑序数就是满足儿子的序数总比父亲大的一个编号方式。这个拓扑序，常用使用深度d ，或者使用时间戳(TimeStamp) DFN （DFS 访问的次序）。下面以深度为例：

记()(())g x d f x =，在DFS 树中从x 开始通过前向弧和后向弧所能到达的最小的d 。有以下的动态规划：

()

()min ()(,), ()'.d x g x d y x y is backforward edge y father g c c is x s child ??

=≠???

这里：

1.第一次访问x 时，记录d(x)

2. d(y)自己发出去的后向边所达到的深度。

3. g(c)就是其子孙中的g最小值。

最后，若g(x)=d(x)，即(father,x)不在圈中，则(father, x)就是桥。

1.3.

2.广度优先搜索Breadth first search (BFS)

1.4.拓扑排序Topological sort

拓扑排序是对有向无圈图(DAG)顶点的一种排序，它使得如果存在u,v的有向路径，那么满足序中u在v前。拓扑排序就是由一种偏序(partical order)得到一个全序(称为拓扑有序(topological order))。偏序是满足自反性，反对称性，传递性的序。

拓补排序的思路很简单，就是每次任意找一个入度为0的点输出，并把这个点以及与这个点相关的边删除。实际算法中，用一个队列实现。

算法：

1.把所有入度=0的点入队Q。

2.若队Q非空，则点u出队，输出u；否则转4。

3.把所有与点u相关的边(u,v)删除，若此过程中有点v的入度变为0，则把v入队Q，

转2。

4.若出队点数

算法复杂度: O(m)。

习题：MIPT 012 Correct dictionary

设R为非空集合A上的二元关系，如果R满足自反性(对于每一个x∈A，(x,x)∈R )，反对称性((x,y)∈R∧(y,x)∈R→x=y )和传递性((x,y)∈R∧(y,x)∈R→(x,z)∈R)，则称R为A上的偏序关系，记作≤。如果(x,y)∈R，则记作x≤y，读作“x小于等于y”。存在偏序关系的集合A称为偏序集(partical order)。

拓扑排序的计数。

？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

AOV(activity on vertex network)

AOE(activity on edge network)，其中顶点表示事件event，权表示时间。

1.5.路径与回路Paths and circuits

1.5.1.欧拉路径或回路Eulerian path

对于连通的可重边的图G，若存在一回路，它通过G的所有边一次且仅一次，则这回路称为欧拉路径或回路。

著名的问题：The K?nigsberg Bridges

下面讨论有向性：

1.5.1.1.无向图

习题：Ural 1124 Mosaic

1.5.1.

2.有向图

习题：CEOI 2005 Depot Rearrangement

1.5.1.3.混合图

混合图是指有的边是有向的，有的边是无向的图。

由于无向边只能经过一次，所以不能拆成两条方向相反的有向边，只能给无向边定向，使得定向后的图满足“入度等于出度”。

见LRJ P324。

下面讨论在有权性上的扩展：

1.5.1.4.无权图Unweighted

1.5.1.5.有权图Weighed —中国邮路问题The Chinese post problem

这就是一个经典的问题中国邮路问题：给出一个连通的无向的可重边的有权图G，求最短的回路，使得每边至少遍历1次。

由于每边至少遍历一次，所以最短路的瓶颈就在于重复遍历。由于图一直保持连通性，所以两两奇点之间都存在欧拉路；又两两奇点之间的最短路可求；奇点个数为偶数。所以问题就等价于找一个奇点构成的完全图G’(V,E)的最小权匹配(Perfect Matching in General Graph)。V(G’)为原图G中的奇点，每条边为两奇点对应原图的最短路长度。

算法：

1.确定G中的奇点，构成G’。

2.确定G’两两结点在G中的最短路作为它们在G’中的边权。

3.对G’进行最小权匹配。

4.最小权匹配里的各匹配边所对应的路径在G中被重复遍历一次,得到欧拉图G’’。

5.对G’’找一条欧拉路即可。

图论算法及其MATLAB程序代码

图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法： 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j)

离散数学图论与系中有图题目

离散数学图论与系中有图题目

————————————————————————————————作者：————————————————————————————————日期：

图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1)

测度论基础知识总结

测度论基础知识总结 1.集合论 1.1 集合与基本运算 ·概念：具有一定性质的对象构成的全体（不严格定义）。中间含有的对象叫元素。 全集：要研究的问题涉及到的最大集合。 空集：没有任何元素的集合。 表达方法：{x（集合元素x）|x应该有的性质} ·元素与集合的关系：x A，x?A ·集合之间的关系 只有包含或者不包含 若对于任意元素x A，x B则A包含于B（证明就用这个方法），A是B的子集（A B 则为B的真子集） 包含的特殊情况相等：A=B就是A包含于B同时B包含于A 真子集：A包含于B但A B ·集合的运算 ①单个元素的幂集 对于一个集合X，它的幂集表示所有其子集为元素构成的集合。这种以集合为元素的集合，也叫集合族。 ②两个集合的运算 交：A B={x| x A且x B} 并：A B={x| x A或x B} 差：A\B（或写成A-B）={x| x A且x?B} 补：=U\A（U是问题要研究的全集） 于是有等式A\B=A 积：（直积）A×B={(x,y)| x A且y B }（把A、B中元素构成有序对） ③多个元素的运算 多个交表示所有以λ为角标的集合的并，要求λ，I称为指标集。 类似有多个并 注：可以是无穷个 【例】={x| x>}，A={x| x>0}，则A= ·集合的分析相关性质 ①上限集：一列集合{}，定义上限集为。类似于数列的上极限。

②下限集：一列集合{}，定义下限集为。类似于数列的下极限。 ③集合列的极限：当上限集等于下限集时极限存在，就是上限集（或下限集）。 ④单调集合列：若始终有包含于，也就是集合越来越大，则为递增集合列；反之， 若始终有，则为递减列。 若为递增列，则有极限=；若为递减列，则有=。 1.2映射 ·定义：X、Y是两个集合，对任意x X，存在唯一的y=f(x)Y与之对应，则对应法则f 为X到Y的一个映射，记为f:X→Y。 像集：对于X的一个子集A，像集{f(x)| x A}记为f(A)，显然包含于Y 原像集：对于Y的一个子集B，原像集{x| x记为 ·满射：f(X)=Y，即Y中所有元素都是像 单射：X中不同元素一定对应Y中不同的像 双射：既是单射又是满射。双射是一一对应的映射。 ·逆映射：对于双射，建立一种Y到X的双射，将像映射到原像上。记为:Y→X ·复合映射：f:X→Y，g:Y→Z，它们的复合g o f:X→Z，写成g(f(X)) ·函数，一个（n维实数向量）到R（实数）上的映射 ·性质（映射与交并运算顺序可交换性） 对于f:X→Y，X若干个子集，Y若干个子集 f(U)=Uf() = f()包含于（只有这一个不一定等于！！！） 不等于的例子：A={1} ，B={-1}，f(x)=|x|，则f(A B)f(A)f(B) = 用集合相等定义可证明。 1.3集合的势 ·对等：如果集合A和B之间可以建立双射，则A对等于B。记为A~B 性质：①A到B有单射→A与B子集对等 A到B有满射→B与A子集对等 ②A~B，B~C，则A~C（传递性） ③A~C，B~D，则A×B~C×D

一笔画问题是图论中一个著名的问题

一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题[1]。一般认为，欧拉的研究是图论的开端。 与一笔画问题相对应的一个图论问题是哈密顿问题。 目录[隐藏] 1 问题的提出 2 一笔画定理 2.1 定理一 2.2 定理二 3 例子 3.1 七桥问题 3.2 一个可以一笔画的例子 4 一笔画问题与哈密顿问题 5 参见 6 参考来源 [编辑] 问题的提出 一笔画问题是柯尼斯堡问题经抽象化后的推广，是图遍历问题的一种。在柯尼斯堡问题中，如果将桥所连接的地区视为点，将每座桥视为一条边，那么问题将变成：对于一个有着四个顶点和七条边的连通图G(S,E)，能否找到一个恰好包含了所有的边，并且没有重复的路径。欧拉将这个问题推广为：对于一个给定的连通图，怎样判断是否存在着一个恰好包含了所有的边，并且没有重复的路径？这就是一笔画问题。用图论的术语来说，就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径（一个圈或者一条链），如果路径闭合（一个圈），则称为欧拉回路[1]。 一笔画问题的推广是多笔画问题，即对于不能一笔画的图，探讨最少能用多少笔来画成。 [编辑] 一笔画定理 对于一笔画问题，有两个判断的准则，它们都由欧拉提出并证明[1]。 [编辑] 定理一 有限图G 是链或圈的充要条件是：G为连通图，且其中奇顶点的数目等于0或者2。有限连通图G 是圈当且仅当它没有奇顶点[2]。 证明[2][3]： 必要性：如果一个图能一笔画成，那么对每一个顶点，要么路径中“进入”这个点的边数等于“离开”这个点的边数：这时点的度为偶数。要么两者相差一：这时这个点必然是起点或终点之一。注意到有起点就必然有终点，因此奇顶点的数目要么是0，要么是2。 充分性： 如果图中没有奇顶点，那么随便选一个点出发，连一个圈C1。如果这个圈就是原图，那么

离散数学的基础知识点总结

离散数学的基础知识点总结 第一章命题逻辑 1.前键为真，后键为假才为假；＜—＞，相同为真，不同为假；2?主析取范式：极小项（m）之和；主合取范式：极大项（M）之积； 3.求极小项时，命题变元的肯定为1，否定为0,求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写; 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有2n个极小项或极大项，这2n为（0~2n-1）刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法（=＞）:真值表法；分析法（假定前键为真推出后键为真，假定前键为假推出后键也为假） 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第二章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含T,存在量词用合取“； 3.既有存在又有全称量词时，先消存在量词，再消全称量词；

第四章集合 1.N，表示自然数集，1,2,3……，不包括0; 2.基：集合A中不同元素的个数，|A|; 3.幕集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幕集P(A)有2°个元素，|P(A)|= 2|A|= 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔AXB的基数为mn , A到B上可以定义2mn种不同的关系； 2.若集合A有n个元素，则|A X\|= n2, A上有2n个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全圭寸闭环的性质：自反性，对称性，反对称性，传递性； 4.前域（domR）:所有元素x组成的集合；

外测度的性质与计算小结

外测度的性质与计算 The properties and calculation of the outer measure 姓名： 学号： 学院：数学与信息科学学院 专业：数学与应用数学 指导老师： 完成时间： 外测度的性质与计算 【摘要】Lebesgue外测度是Lebesgue积分的基础,本论文主要论述了它的一些性质及相关的计算.首先,给出了Lebesgue外测度的定义；接着,指出和证明了外测度具有的非负性、单调性、次可数可加性、距离可加性、平移不变性这五大主要性质；同时给出了外测度的介值定理和一些其他的性质,并讨论了在一般情况下,外测度不具备可数可加性；然后讨论了可数集的外测度的性质,着重写出可数

江西师范大学11届学士学位毕业论文 集的外测度具有可数可加性；最后是与外测度计算相关的一些例题.【关键词】Lebesgue外测度，次可数可加性，距离可加性。

The properties and calculation of the outside measure 【abstract 】Lebesgue outer measure is the base of lebesgue integral, this thesis mainly discusses some properties and its related calculation. At first, give the definition of Lebesgue outer measure; then pointed out and proved the outer measure has nonnegative, monotonicity and second countable additive property , distance additive property,translation invariant property ,the five main properties; It also gives the outer measure mean value theorem and some other properties, and discusses the properties under the meaning of general point sets, the outer measure does not have countable additive property. Then discussed the property of outer measure of countable set, and emphatically write that outer measure of countable set has count additive property. And the last is some examples about outer measure computation. 【keywords 】Lebesgue outer measure, Second countable additive property , Distance additive property

第二章 测度论的知识要点与复习自测

第二章 测度论的知识要点与复习自测 一、Lebesgue 外测度的知识要点： ◇ 熟练掌握Lebesgue 外测度的定义和外测度的基本性质（包括基本性质：非负性、单调性、次可数可加性；Lebesgue 外测度的特有性质：距离分离性）； ◇ 会用定义或性质求一些典型集合的外测度（例如：n R 中至多可数集，区间，Cantor （三分）集，黎曼可积函数（特别是连续函数）图象等的外测度）； ◇ 特别注意零测集的含义和性质【如n R 中的任何集合并上零测集或减去零测集外侧度不变；零测集的子集仍为零测集；至多可数个零测集的并集仍为零测集】。 自测题： 1、叙述n R 中Lebesgue 外侧度的定义及性质，并用定义和性质解决如下问题： （1）设n n Q R ?为有理点集，计算*n m Q 0=； （2）设n R E ?为至多可数集，计算* m 0E =； （3）设n ,R E F ?，* m 0E =，则()()***m m m \F E F F E ?==。 2、据理说明下面的结论是否成立：设n R E ?， （1）若E 为有界集，则* m E <+∞； （2）若* m E <+∞，则E 为有界集； （3）若*m E =+∞，则E 为无界集； （4）若E 为无界集，则* m E =+∞。 3、设n R I ?为区间，证明：*m I I =，其中I 表示I 的体积（注意I 分有界和无界 两种情况来证明）；并利用此结论和外侧度的性质再解决如下问题： （1）设1[0,1]R P ??为三分Cantor 集，则* m 0P =；（注意三分Cantor 集的构造） （2）设()f x 为定义在1[,]R a b ?上的黎曼可积函数， {}2()(,)(),[,]R p G f x y y f x x a b ==∈?， ()f x 在[,]a b 的图像，则*m ()0p G f =；（注意黎曼可积的充要条件的使用） （3）设n R E ?有内点，则* m 0E >； （4）（外侧度的介值性）设1 R E ?为有界集，*m 0E >，则对任意* 0m c E ≤≤，存在1E E ?，使得，*1m E c =；（注意构造适当的连续函数，利用连续函数的介值性） （5）（外侧度的介值性的一般形式）设1 R E ?，*m 0E >，则对任意* 0m c E ≤≤，存在1E E ?，使得，*1m E c =。（注意：此结论要用到后面的等测包定理和单调递增可测集列的测度性质） 二、Lebesgue 可测集的知识要点： ◇ 熟练掌握Lebesgue 可测集的卡氏定义（即C.Caratheodory 定义）及等价 条件（如：余集的可测性；对任意的A E ?和c B E ?，总有()*** m A B m A m B ?=+），会用定义或等价条件来证明一些点集的可测性（例如：零测集，区间等）； ◇ 熟练掌握可测集的并、交、差、余运算性质，并会熟练地运用这些性质来判断集合的可测性；

数学建模中的图论方法

数学建模中的图论方法 一、引言 我们知道，数学建模竞赛中有问题A和问题B。一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A题入手快，而B题不好下手。 另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。 图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如： AMCM90B－扫雪问题； AMCM91B－寻找最优Steiner树； AMCM92B－紧急修复系统的研制(最小生成树) AMCM94B－计算机传输数据的最小时间(边染色问题) CMCM93B－足球队排名(特征向量法) CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性) CMCM98B－灾情巡视路线(最优回路) 等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。 本文将从图论的角度来说明如何将一个工程问题转化为合理而且可求解的数学模型，着重介绍图论中的典型算法。这里只是一些基础、简单的介绍，目的在于了解这方面的知识和应用，拓宽大家的思路，希望起到抛砖引玉的作用，要掌握更多还需要我们进一步的学习和实践。

经典图论问题

5经典图论问题 5.1 一笔画问题 一笔画算法即是从起点a开始选择关联边（第一这条边不是往回倒，第二这条边在前面延伸路上没有出现过）向前延伸，如果到达终点b，得到a—b迹，判断路上的的边数是否为图的总边数，是就终止，否则选择迹上某个关联边没有用完的顶点v，用同样方式再搜索v—v的闭迹，添加到a—b迹上，即得到a—v---v—b迹，如果这个迹的边数还没有达到总边数，则再选择迹上某个关联边没有用完的顶点。。。。。。逐步扩展即可。

二、弗罗莱（Fleury ）算法 任取v 0∈V(G)，令P 0=v 0； 设P i =v 0e 1v 1e 2…e i v i 已经行遍，按下面方法从中选取e i+1： （a ）e i+1与v i 相关联； （b ）除非无别的边可供行遍，否则e i+1不应该为G i =G-{e 1,e 2, …, e i }中的桥（所谓桥是一条删除后使连通图不再连通的边）； （c ）当（b ）不能再进行时，算法停止。 5.2 中国邮递员问题（CPP ） 规划模型： 设ij x 为经过边j i v v 的次数，则得如下模型。 ∑∈= E v v ij ij j i x z ?min ∑ ∑ E ∈E ∈∈=j i i k v v i v v ki ij V v x x , E ∈∈≤j i ij v v N x ,1 ..t s

5.3旅行推销员问题（TSP，货郎担问题）（NPC问题） 定义：包含图G的所有定点的路（圈）称为哈密顿路（圈），含有哈密顿圈得图称为哈密顿图。 分析：从一个哈密顿圈出发， 算法一：（哈密顿圈的充要条件：一包含所有顶点的连通子图，二每个顶点度数为2） 象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。 算法二： 算法三：

图论算法及matlab程序的三个案例

图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma)

数学建模入门基本知识

数学建模知识 ——之新手上路一、数学模型的定义 现在数学模型还没有一个统一的准确的定义，因为站在不同的角度可以有不同的定义。不过我们可以给出如下定义：“数学模型是关于部分现实世界和为一种特殊目的而作的一个抽象的、简化的结构。”具体来说，数学模型就是为了某种目的，用字母、数学及其它数学符号建立起来的等式或不等式以及图表、图像、框图等描述客观事物的特征及其内在联系的数学结构表达式。一般来说数学建模过程可用如下框图来表明： 数学是在实际应用的需求中产生的，要解决实际问题就必需建立数学模型，从此意义上讲数学建模和数学一样有古老历史。例如，欧几里德几何就是一个古老的数学模型，牛顿万有引力定律也是数学建模的一个光辉典范。今天，数学以空前的广度和深度向其它科学技术领域渗透，过去很少应用数学的领域现在迅速走向定量化，数量化，需建立大量的数学模型。特别是新技术、新工艺蓬勃兴起，计算机的普及和广泛应用，数学在许多高新技术上起着十分关键的作用。因此数学建模被时代赋予更为重要的意义。 二、建立数学模型的方法和步骤 1. 模型准备 要了解问题的实际背景，明确建模目的，搜集必需的各种信息，尽量弄清对象的特征。 2. 模型假设 根据对象的特征和建模目的，对问题进行必要的、合理的简化，用精确的语言作出假设，是建模至关重要的一步。如果对问题的所有因素一概考虑，无疑是一种有勇气但方法欠佳的行为，所以高超的建模者能充分发挥想象力、洞察力和判断力，善于辨别主次，而且为了使处理方法简单，应尽量使问题线性化、均匀化。 3. 模型构成 根据所作的假设分析对象的因果关系，利用对象的内在规律和适当的数学工具，构造各个量间的等式关系或其它数学结构。这时，我们便会进入一个广阔的应用数学天地，这里在高数、概率老人的膝下，有许多可爱的孩子们，他们是图论、排队论、线性规划、对策论等许多许多，真是泱泱大国，别有洞天。不过我们应当牢记，建立数学模型是为了让更多的人明了并能加以应用，因此工具愈简单愈有价值。 4. 模型求解 可以采用解方程、画图形、证明定理、逻辑运算、数值运算等各种传统的和近代的数学方法，特别是计算机技术。一道实际问题的解决往往需要纷繁的计算，许多时候还得将系统运行情况用计算机模拟出来，因此编程和熟悉数学软件包能力便举足轻重。 5. 模型分析

图论应用案例

题目：最小生成树在城市交通建设中的应用 姓名： 学号： 指导老师： 专业：机械工程 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

离散数学图论与关系中有图题目

图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8 个结点的三次正则图 (2) (1) (3) (2) (1)

图论总结(超强大)78408

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

maab图论程序算法大全

图论算法m a t l a b实现求最小费用最大流算法的 MATLAB 程序代码如下： n=5;C=[0 15 16 0 0 0 0 0 13 14 0 11 0 17 0 0 0 0 0 8 0 0 0 0 0]; %弧容量 b=[0 4 1 0 0 0 0 0 6 1 0 2 0 3 0 0 0 0 0 2 0 0 0 0 0]; %弧上单位流量的费用 wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流 while(1)

for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图 for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;e nd if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 向赋权图中不会含负权回路, 所以不会出现k=n dvt=Inf;t=n; %进入调整过程, dvt 表示调整量 while(1) %计算调整量 if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量 elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量

测度论的知识要点与复习自测

第二章 测度论的知识要点与复习自测 一、Lebesgue 外测度的知识要点： ◇ 熟练掌握Lebesgue 外测度的定义和外测度的基本性质（包括基本性质：非负性、单调性、次可数可加性；Lebesgue 外测度的特有性质：距离分离性）； ◇ 会用定义或性质求一些典型集合的外测度（例如：n R 中至多可数集，区间，Cantor （三分）集，黎曼可积函数（特别是连续函数）图象等的外测度）； ◇ 特别注意零测集的含义和性质【如n R 中的任何集合并上零测集或减去零测集外侧度不变；零测集的子集仍为零测集；至多可数个零测集的并集仍为零测集】。 自测题： 1、叙述n R 中Lebesgue 外侧度的定义及性质，并用定义和性质解决如下问题： （1）设n n Q R ?为有理点集，计算*n m Q 0=； （2）设n R E ?为至多可数集，计算*m 0E =； （3）设n ,R E F ?，*m 0E =，则()()***m m m \F E F F E ?==。 2、据理说明下面的结论是否成立：设n R E ?， （1）若E 为有界集，则*m E <+∞； （2）若*m E <+∞，则E 为有界集； （3）若*m E =+∞，则E 为无界集； （4）若E 为无界集，则*m E =+∞。 3、设n R I ?为区间，证明：*m I I =，其中I 表示I 的体积（注意I 分有界和无界两种情况来证明）；并利用此结论和外侧度的性质再解决如下问题： （1）设1[0,1]R P ??为三分Cantor 集，则*m 0P =；（注意三分Cantor 集的构造） （2）设()f x 为定义在1[,]R a b ?上的黎曼可积函数， {}2()(,)(),[,]R p G f x y y f x x a b ==∈?， ()f x 在[,]a b 的图像，则*m ()0p G f =；（注意黎曼可积的充要条件的使用） （3）设n R E ?有内点，则*m 0E >； （4）（外侧度的介值性）设1R E ?为有界集，*m 0E >，则对任意*0m c E ≤≤，存在1E E ?，使得，*1m E c =；（注意构造适当的连续函数，利用连续函数的介值

图论经典问题

常见问题： 1、图论的历史 图论以图为研究对象的数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论则是研究事物对象在上述表示法中具有的特征与性质的学科。 在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了。另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。 事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。 图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段： 第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)。 东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被河的分支和岛分成了四个部分，各部分通过7座桥彼此相通。如同德国其他城市的居民一样，该城的居民喜欢在星期日绕城散步。于是产生了这样一个问题：从四部分陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。这就是有名的哥尼斯堡七桥问题。 哥尼斯堡七桥问题看起来不复杂，因此立刻吸引所有人的注意，但是实际上很难解决。 瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父。 欧拉把七桥问题抽象成数学问题---一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解。Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在？Euler证明这样的回路是不存在的。 第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树