图论在实际生活中的应用

摘要

寻找最短的路径到达想要去的地方在这个快节奏的时代已经变得越来越重要，它对于节约人们的时间成本具有重要意义。当前城市的规模越来越大，交通道路状况也越来越复杂，从一个地方到另一个地方可能有很多种路径，如何从众多的路径中选择距离最短或者所需时间最短的路径便成了人们关注的热点。能够选择出一条最符合条件的路径会给我们的日常生活带来极大地方便。本文就通过找重庆邮电大学几个代表性地点之间寻找最短距离路径为例，介绍经典的最短路径算法Floyd算法及其算法的实现。

关键字：最优路径，Floyd算法，寻路

一、图论的基本知识

图论起源于举世闻名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上面有七座桥将河中的岛及岛与河岸是连接起来的,有一个问题是要从这四块陆地中任何一块开始，通过每一座桥而且正好只能一次，再回到起点。然而许多人经过无数次的尝试都没有成功。在1736年欧拉神奇般的解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即用点来代替每一块陆地，将每一座桥用联接相应的两个点的一条线来代替，所以相当于得到一个“图”（如下图）。

柯尼斯堡七桥图

桥转换成图

欧拉证明了这个问题是没有解的，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使得欧拉成为图论〔及拓扑学〕的创始人。

图论其实也是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。它具有以下特点：蕴含了丰富的思想、漂亮的图形以及巧妙的证明；涉及的问题很多而且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法是千变万化，非常灵活，常常是一种问题就有一种解法。图论研究的内容非常广泛，如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。历史上参与研究图论问题的人既有许多天才的数学家，也有不少的业余爱好者。

那么什么是图论中的图呢？在日常生活、生产活动以及科学研究中，人们常用点表示事物，用点与点之间是否有连线表示事物之间是否是有某种关系，这样构成的图形就是图论中的图。其实，集合论中的二元关系的关系图都是图论中的图，在这些图中，人们只关心点与点之间是否有连线，而不关心点的位置，以及连线的曲直。这就是图论中的图与几何中的图形的本质区别。

C

A B

D

(b)

因此在现实世界中，事物的许多状态可以由图形来描述，使其简单直观，便于理解，帮助思维，易于记忆，同时还可以根据图的特点，从不同角度来扩展讨论范围。

1.1、图论概述

图论〔Graph Theory 〕是数学的一个分支，也是一门新兴学科，发展迅速而又应用广泛。它已广泛地应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络管理、社会科学等几乎所有的学科领域。另一方面，随着这些学科的发展，特别是计算机科学的快速发展，又大大的促进了图论的发展。

图论中的研究对象是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 1.2 图论中的最短路问题

路的定义 设G 为无向标定图，G 中顶点与边的交替序列 il

jl j i j i v e e v e v T 2110=

称为0i v 到il v

的通路，其中1-r i v ，r i v 为r j e 的端点，l i i v v l r ,,,,2,10 =分别称为T 始点与终点，T 中的边的条数称为它的长度，若又有l i i v v =0，则称T 为回路。

若T 的所有边各异，则称T 为简单通路。若又有l

i i v v =0，则称T 为简单回路，若

所有的顶点（除0i v 与l i v

可能相同外）各异，所有的边也各异，则称T 为初级通

路或路径，若又有l

i i v v =0，则T 为初级回路或圈，将长度为奇数的圈成为奇圈，长度为偶数的圈为偶圈。

我们要考虑的问题是对任意给定的一个赋权图G ,及G 中两个指点的顶点0u 与0

v ，求出其最短路径。易见。只要考虑简单连通图的情形就够了。这里我们假设每边e 的权)(e w 都是大于0的实数。因为当一条边uv e =的权为0时。我们可以把u 和v 合并成一个顶点。又，我们约定边)(G E e ?当且仅当∞=)(e w 。 1.3 Floyd 算法

Floyd 算法的基本思想：

可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个地点而言，i 到j 的最短距离不外乎存在经过i 与j 之间的k 和不经过k 两种可能，所以可以令k=1，2，3，...，n(n 是地点的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i 到k 与k 到j 的最短距离，因此d(ik)+d(kj)就是i 到j 经过k 的最短距离。所以，若有d(ij)>d(ik)+d(kj)，就表示从i 出发经过k 再到j 的距离要比原来的i 到j 距离短，自然把i 到j 的d(ij)重写为d(ik)+d(kj)，每当一个k 查完了，d(ij)就是目前的i 到j 的最

短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j 之间的最短距离了。

Floyd算法的基本步骤：

定义n×n的方阵序列D-1, D0 , … Dn－1,

初始化： D-1＝C

D-1[i][j]＝边的长度，表示初始的从i到j的最短路径长度，即它是从i到j的中间不经过其他中间点的最短路径。

迭代：设Dk-1已求出，如何得到Dk（0≤k≤n-1）

Dk-1[i][j]表示从i到j的中间点不大于k-1的最短路径p：i…j，考虑将顶点k加入路径p得到顶点序列q：i…k…j，

若q不是路径，则当前的最短路径仍是上一步结果：Dk[i][j]= Dk－1[i][j]；

否则若q的长度小于p的长度，则用q取代p作为从i到j的最短路径。

因为q的两条子路径i…k和k…j皆是中间点不大于k－1的最短路径，所以从i到j中间点不大于k的最短路径长度为：

Dk[i][j]＝min{ Dk-1[i][j], Dk-1[i][k] +Dk-1[k][j] }

二、利用图论知识寻找指定两点最短路径

2.1 把实际问题转化成图论问题

图1 重庆邮电大学地图

上图为邮电大学的地图，我们在地图中选取重邮的八个地方看成是八个点（1、新世纪超市 2、三教学楼 3、数字图书馆 4、二教学楼 5、信科大楼 6、太极操场 7、老图书馆 8、31栋宿舍），用线段把每一个点与其相邻的点连接起

来，从而形成一个无向图。再根据实际情况：不同地点的距离问题；路的畅通与否等给相应的边赋上权值，最后得出一个赋权图，如图2：

图2 赋权图

2.2 Floyd算法用C++实现

#include

#include

#include

using namespace std;

#define MAX_VEX_NUM 10

vector allPath; //向量，用来存放所有的顶点a到顶点i的路径

vector all; //向量，用来存放对应路径的长度

struct MGraph

{

char vexs[MAX_VEX_NUM];

int arcs[MAX_VEX_NUM][MAX_VEX_NUM];

int vexnum,arcnum;

};

MGraph G;

int Locatevex(MGraph G,char v)//图的基本操作，寻找V的位置

{

int i=0;

while(i

i++;

if(i

return i;

else

return -1;

}

int CreateUDG(MGraph &G) //数组邻接矩阵表示法构造无向图

{

char v1,v2;

int weight;

cout<<"请输入图的顶点数和边的条数"<

cin>>G.vexnum>>G.arcnum;

cout<<"请输入顶点的名称(0--9)"<

for(int i=0;i

cin>>G.vexs[i];

for(int q=0;q

for(int p=0;p

G.arcs[q][p]=0;

for(int k=0;k

{

cout<<"输入边的顶点和权值：(格式为：起点终点权值)"<

cin>>v1>>v2>>weight;

int a=Locatevex(G,v1);

int b=Locatevex(G,v2);

G.arcs[a][b]=weight;

G.arcs[b][a]=G.arcs[a][b];

}

cout<<"该图的邻接矩阵表示为：\n";

for(int n=0;n

cout<

cout<

cout<

for(int x=0;x

{

for(int y=0;y

cout<

cout<

}

cout<

cout<

return 1;

}//CreateUDG

void Minway(MGraph G,bool *visited,char vexs,int Long,char vb,string path) //递归求取所有顶点a到顶点i的路径

{

if(vexs==vb)

{

path=path+"-->"+vexs;

allPath.push_back(path);

all.push_back(Long);

cout<<"路径:"<

}

else

{

path=path+"-->"+vexs;

int i=Locatevex(G,vexs);

visited[i]=true;

for(int j=0;j

if((!visited[j])&&(G.arcs[i][j]!=0))

{

Minway(G,visited,G.vexs[j],Long+G.arcs[i][j],vb,path);

}

visited[i]=false;

}

}

void CountMinway(MGraph G) //该函数调用递归部分实现递归

{

char va,vb;

string path;

cout<<"请输入您所处的位置:";

cin>>va;

cout<<"请输入您想到达的位置:";

cin>>vb;

cout<

int i=Locatevex(G,va);

bool visited[100];

for(int j=0;j

visited[j]=false;

visited[i]=true;

int Long=0;

path+=va;

for( j=0;j

if(G.arcs[i][j]!=0)

{

Long=G.arcs[i][j];

Minway(G,visited,G.vexs[j],Long,vb,path);

}

cout<

}

void Minway()//输出最短路径

{

int min=10000;

for(int i=0;i

if(all[i]

min=all[i];

for(int j=0;j

if(all[j]==min)

cout<<"最短路径: "<

cout<

}

void main()

{

CreateUDG(G); //建图

CountMinway(G); //找出所有路径

Minway(); //输出最短路径

}

程序描述：通过输入顶点的个数、边的条数和名称以及两点之间的权值得到一个带权值的矩阵。再输入你所处的位置和你要到的位置，程序将通过Floyd 算法给出可以到达的路径，并给出最优的路径（即权值最小的路径）。

输入图的顶点个数和边的条数，并输入顶点的名称如图3所示。

图3 数据输入图

输入边的权值，输入格式为边的起点名称终点名称和权值，如图4所示。

图4 权值的输入

程序自动生成并输出图的邻接矩阵如图5所示。

图5 图的邻接矩阵

输入所在的位置和想要去的位置，程序给出可以到达的所以路径及其权值，并给出最短的路径及其权值如图6所示。

图6 输出结果

总结

图论其实是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。它具有以下特点：蕴含了丰富的思想、漂亮的图形和巧妙的证明；涉及的问题多且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法千变万化。非常灵活，常常是一种问题一种解法。图论研究的内容非常广泛，如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。

在实际生活中，图论是有很大的利用价值的，应用的范围也很广泛。在教材《图论及其算法》中就介绍了图论在实际生活中各方面的应用，例如解决中国投递员问题，解决旅行推销员问题，解决七桥问题等。

有的时候通过人工计算和处理图论问题很费时费力而且准确性无法保证，所以我们需要将问题抽象出来再进行分析，通过计算机编程实现，在经过调试和修改实现所需要的功能。通过计算机可以快速的处理问题并准确地给出答案。

参考文献：

[1]殷剑宏、吴亚开.图论及其算法[M].合肥:中国科学技术大学出版社,2005

[2]严蔚敏.数据结构（c语言版）[M].北京:清华大学出版社,2009

答案(电子科大版)图论及其应用第一章

习题一： ● 。 证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 ● 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： m=4： (a) v 23 4 (b)

m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 ● 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1） 不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 1 1 12312(1,1,,1,,,)d d n d d d d d π++=---是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若 ，则包含圈。 证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干 个连通的情形来证明。设 , 对于中的路 若与邻接，则构成一个闭路。若是一条路，由于，因 此，对于，存在与之邻接，则构成一个圈。 ● 17.证明：若G 不连通，则连通。 证明：对于任意的 ,若与属于G 的连通分支，显然与在中连通；

组合数学在计算机中的应用

组合数学在计算机中的应用 组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。随着计算机科学的发展,组合数学也在迅猛发展,而组合数学在理论方面的推进也促进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础,组合数学作为大多数计算机软件设计的理论基础,它的重要性也就不言而喻。 就从目前我们在学习c++等语言进行编程解决问题看，组合数学的一些知识就能得到运用。例如Hannoi塔问题。用刚刚学的递推关系分析，设h(n)为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h(1)=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上，共计3个盘次，故h(2)=3。以此类推，当a柱上有n(n>=2)个盘子时，总是先借助c柱把上面的n-1个盘移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动h(n-1)+1+h(n-1)个盘次。所以：h(n)=2h(n-1)+1 （边界条件：h1=1）。而一旦得出了这个递推关系式，就很容易运用递归算法来解决这样一个问题，递归算法因为是运用栈的方式进行加深与回溯，这个栈是系统给出的，故大大减少代码量。因此利用组合数学中的知识很容易抽象出数学模型再用相应的编程技巧来解决问题。 另外，我们最近数据结构正好学到了图这一章节。图是一种非常重要的数据存储结构，而在图的建立，遍历，生成树等问题的解决算法上基本都运用了组合数学中的知识。例如在最小生成树算法中间需要判断是否有环的问题，中间算法思想中就包含了欧拉图判定定理，(1) 无向连通图G是欧拉图=>G不含奇数度的结点(即G的所有结点的度均为偶数(0视为偶数))；(定理1) (2) 非0平凡图G有欧拉通路=>G最多有两个奇数度的结点；(定理1的推论) (3) 有向图D是欧拉图=>D连通且D的所有结点的入度等于出度。有向连通图有欧拉通路=>除两个结点外，其余结点的出度均等于入度，且这两点deg-(v)-deg+(v)=±1。(定理2) 除此之外，在那些我们还没有接触的计算机领域中，处处也有组合数学的身影。如：信息检索是计算机科学中一个基本而又重要的问题。如何组织数据,使用什么样的查找方法,对检索的效率有很大的影响。所熟知的在有序表结构上的二分搜索算法是一种很有效的方法,那么二分搜索是最好的算法吗?Yao利用Ramsey数对这一问题作了肯定的回答。 具体地讲,假设一个表有n个不同的项,其元素取自键空间M={1,2,,, m } ,希望找到在表中存储M的任意n元子集S的方法,使得容易回答下述询问: X在S中吗?如何存储M的n元子集的规则称为一个表结构或( m , n)-表结构。最简单的表结构是有序表结构,它是按上升序列出S中的元素。更一般的是按置换排序的表结构,其方法是固定{1,2,,, n}的一个置换,根据比置换的次序列出S中的元素。 信息检索的计算复杂性依赖于表结构和搜索策略。复杂性的度量是最坏情形下确定x 是否在S中所需要的询问次数。例如,对有序表结构,如果用二分搜索,所需要的询问次数是[log2( n+ 1) ]。复杂性f ( m , n )定义为所有的( m , n)-表结构和搜索策略下的复杂性的最小值。关于f ( m , n ), Yao证明了: 定理1 对每个n ,存在数N ( n) 使得f ( m , n) = [log2 ( n +1 ) ]对所有m>=N ( n) 成立。据此定理,对充分大的m ,就信息检索来说,用有序表结构是最有效的方法。 利用下述两个引理,立即可得此定理的证明。 引理1 若m >=2 n -1 , n >=2 ,对于按置换排序的表结构。无论采用何种策略,在最坏情形

电子科技大学研究生试题《图论及其应用》(参考答案)

电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D

6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G

图论在通信网中的应用

5.3.6 图论在通信网中的应用 网络可靠性是评价网络是否稳定工作的一个非常重要的指标。而网络可靠性的衡量取决于网络的两个重要的指标——结合度和连通度。下面主要就结合度和连通度的定义及其计算作简要描述，并以一个例子加以说明。 1. 网络的结合度和连通度的定义 1）结合度： 网络G 的结合度又称为边连通度，记为()L G ，其大小等于使网络成为不连通图所需去掉链路（边）的最少条数。它反映网络节点间的内聚程度，是网络可靠性的一个基本度量指标。例如, 通过观察易知,图5.29所示的网络的结合度()3L G =。 ? ? ?? ?? ?? 图5.29 2）连通度：网络G 的连通度又称为点连通度，记为()K G ，其大小等于使网络成为不连通图所需去掉的节点的最少个数。例如，图5.29所示的网络的连通度()2K G =。从某种意义上讲，点连通度是比边连通度更重要的网络可靠性度量指标，这是因为在网络中去掉某个节点 就意味着与之关联的所有链路将失去意义。 2. 网络结合度和连通度的算法 1）算法基本思想 通常，要求给定网络(,)G V E =的结合度，需要首先确定任意不同两点的链路割集。设i v 和j v 是的两个不同节点，所谓G 的一个i j v v -链路割集是指这样的链路集合：若去掉其中所有链路，网络G 将被分割成两个分支，一个包含节点i v ，另一个包含节点j v 。假设 ij L 是G 中所有i j v v -链路割集中链路的最小数，则ij L 就是切断i v 和j v 之间所有路由所需 从G 中删去的最小链路数，故网络G 的结合度()L G 可按下式计算： ,,()m in i j i j ij v v V v v L G L ∈≠= 与确定结合度的方法类似，求给定网络(,)G V E =的连通度，则需要首先确定任两个不同节点间的节点割集。设i v 和j v 是的两个不同节点，G 的一个i j v v -节点割集是指这样

图论及其应用答案电子科大

图论及其应用答案电子科 大 This model paper was revised by the Standardization Office on December 10, 2020

习题三： 证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通， 而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。 必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。 （2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,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

图论及应用第一章完整作业

习 题 1 1. 证明在n 阶连通图中 （1） 至少有n -1条边。 （2） 如果边数大于n -1，则至少有一条闭通道。 （3） 如恰有n -1条边，则至少有一个奇度点。 证明 (1) 若对?v ∈V(G),有d(v)≥2,则：2m=∑d(v)≥2n ? m ≥n >n-1,矛盾！ 若G 中有1度顶点，对顶点数n 作数学归纳。 当n=2时，G 显然至少有一条边，结论成立。 设当n=k 时，结论成立， 当n=k+1时，设d(v)=1，则G-v 是k 阶连通图，因此至少有k-1条边，所以G 至少有k 条边。 (2) 考虑v 1→v 2→?→v n 的途径，若该途径是一条路，则长为n-1,但图G 的边数大于n-1,因此存在v i ,v j ,使得v i adgv j ,这样，v i →v i+1→?→v j 并上v i v j 构成一条闭通道；若该途径是一条非路，易知，图G 有闭通道。 (3) 若不然，对?v ∈V(G),有d(v)≥2,则：2m=∑d(v)≥2n ? m ≥n >n-1,与已知矛盾！ 2. 设G 是n 阶完全图，试问 （1） 有多少条闭通道？ （2） 包含G 中某边e 的闭通道有多少？ （3） 任意两点间有多少条路？ 答 (1) (n-2)! (2) (n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n -2)…1. 3. 证明图1-27中的两图不同构： 证明 容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。 4. 证明图1-28中的两图是同构的 证明 将图1-28的两图顶点标号为如下的(a)与(b)图 图 1-27 图1-28

组合数学

组合数学论文 现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好像是有思维的。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。 广义的组合数学就是离散数学，离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。 狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。 组合数学中有几个著名的问题： 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。 船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？ 这是线性规划的问题。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。 货郎问题：一个货郎要去若干城镇卖货，然后会到出发地，给定各个城镇之间的旅行时间，应怎么样计划他的路线，使他可以去每个城镇而且所用的时间最短。这个问题至今都没有有效的算法。 这几个问题将组合数学研究的问题具体表现出来，同时也可以看出他在我们生活中有着很重要的地位。 组合数学中主要可以分成以下几个部分：排列组合与容斥原理、二项式定理、递推关系与生成函数、polya定理。下面我将以这四个部分分别介绍组合数学的各方面问题。 1、排列组合与容斥原理： 排列组合里面的4个重要的基本原理：加法原理、乘法原理、减法原理、除法原理 前面两个最为基本，后面两个是根据前两个派生出来的。乘法原理有的时候的应用很巧妙，可以作为一种打开思路的办法。

图论在网络拓扑发现算法中的应用

小 型 微 型 计 算 机 系 统 Journal of Chinese Computer Systems
2008 年 月 第 期 Vol.28 No. 2008
?
图论在网络拓扑发现算法中的应用
路连兵 1+，胡吉明 2，姜 岩 1
1，2
，2
(河海大学 计算机及信息工程学院,江苏 南京
210098)
E-mail ：famioo@https://www.wendangku.net/doc/bc8997815.html,
摘
要：网络拓扑发现技术已经广泛地应用在各种项目软件中。然而，随着网络结构复杂度升级，这给拓扑发现带来了
挑战。所以我们越来越需要一种高效，准确的网络拓扑算法自动发现网络拓扑结构。目前的拓扑算法主要集中在：(1)路 由层的发现。这个层面的发现算法在技术上比较简单，只需要寻找路由与路由之间，或路由端口与子网之间的连接关系， 利用路由器的自身特性，很容易实现。(2)链路层的发现。直到目前为止，已有的厂商工具很难准确发现网络拓扑，已发 表的理论文献知识也只是理论上阐述，实际应用难度比较大。本论文，提出一种基于图论的骨架树数据存储结构算法，可 以高效推断网络的拓扑关系。 关键词：骨架树;子网;地址转发表;图论；信任节点
Topology Discovery in Networks Based on Graph Theory*
LU Lian-Bing1+, HU Ji-Ming2，Jiang Yan1,2
1,2
(School of Computer Science and Information, Hohai University, Nanjing Jiangsu 210098, China)
Abstract: Topology discovery systems are starting to be introduced in the form of easily and widely deployed software. However, Today's IP network is complex and dynamic. Keeping track of topology information efficiently is a difficult task. So, we need effective algorithms for automatically discovering physical network topology. Earlier work has typically focused on: (1) Layer-3 (network layer) topology, which can only router-to-router interconnections and router interface-to-subnet relationships. This work is relatively easy and has lots of systems can do it. (2)Layer-2(link layer), till now, no tools can discovery the network topology exactly because of bad algorithm. In this paper, Skeleton-tree based on Graph theory is proposed to infer the connections between network nodes. Key words: Skeleton-tree; subnets; Address Forwarding Table; Graph Theory；Trust Node
作者简介: 路连兵(1979－),男,江苏泗洪人,硕士。 主要研究网络自拓扑,软件项目管理,Perl 研究;胡吉明(1967－),男,硕导,副教授,主要研究 领域为计算机应用技术,网络安全,数据挖掘，Z 语言; 姜岩(1979-),男,硕士研究生,主要研究方向,网络应用,中间件

图论及应用第一章完整作业

习题 1 1. 证明在n阶连通图中 （1）至少有n-1条边。 （2）如果边数大于n-1，则至少有一条闭通道。 （3）如恰有n-1条边，则至少有一个奇度点。 证明(1) 若对v V(G),有d(v)2,则：2m=d(v)2n m n n-1,矛盾！ 若G中有1度顶点，对顶点数n作数学归纳。 当n=2时，G显然至少有一条边，结论成立。 设当n=k时，结论成立， 当n=k+1时，设d(v)=1，则G-v是k阶连通图，因此至少有k-1条边，所以G至少有k条边。 (2) 考虑v 1v 2v n的途径，若该途径是一条路，则长为n-1,但图G的边数 大于n-1,因此存在v i,v j,使得v i adgv j,这样，v i v i+1v j并上v i v j构成一条闭通道； 若该途径是一条非路，易知，图G有闭通道。 (3) 若不然，对v V(G),有d(v)2,则：2m=d(v)2n m n n-1,与 已知矛盾！ 2.设G是n阶完全图，试问 （1）有多少条闭通道？ （2）包含G中某边e的闭通道有多少？ （3）任意两点间有多少条路？ 答(1) (n-2)! (2) (n-1)!/2 (3) 1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n-2)…1. 3.证明图1-27中的两图不同构： 图1-27 证明容易观察出两图中的点与边的邻接关系各不相同，因此，两图不同构。 4.证明图1-28中的两图是同构的 图1-28 证明将图1-28的两图顶点标号为如下的(a)与(b)图

作映射f : f(v i )u i (1 i 10) 容易证明，对v i v j E((a)),有f(v i v j )u i u j E((b)) (1 i 10, 1j 10 ) 由图的同构定义知，图1-27的两个图是同构的。 5. 证明：四个顶点的非同构简单图有11个。 证明 m=0 1 2 3 4 5 6 由于四个顶点的简单图至多6条边，因此上表已经穷举了所有情形，由上表知：四个顶点的非同构简单图有11个。 6. 设G 是具有m 条边的n 阶简单图。证明：m =??? ? ??2n 当且仅当G 是完全图。 证明 必要性 若G 为非完全图，则 v V(G),有d(v) n-1 d(v) n(n-1) 2m n(n-1) m n(n-1)/2=??? ? ??2n , 与已知矛盾！ 充分性 若G 为完全图，则 2m= d(v) =n(n-1) m= ??? ? ??2n 。 7. 证明：（1）m (K l ,n ) = ln ， (a) v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9 u 10 (b)

组合数学前沿介绍

组
合
数
学
Combinatorics
马昱春 MA Yuchun myc@https://www.wendangku.net/doc/bc8997815.html,
1

组
合
数
学
Combinatorics
组合数学:有人认为广义的组合数学就是离散数学，也有人认 为离散数学是狭义的组合数学和图论、代数结构、数理逻辑 等的总称。但这只是不同学者在叫法上的区别。总之，组合 数学是一门研究离散对象的科学。
https://www.wendangku.net/doc/bc8997815.html,/zh-cn/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6
Combinatorics: Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics.
https://www.wendangku.net/doc/bc8997815.html,/wiki/Combinatorics 2

组合数学与离散数学
? 狭义的组合数学主要研究满足一定条件的组态（ 也称组合模型）的存在、计数以及构造等方面的 问题。
– 组合数学的主要内容有组合计数、组合设计、组合矩 阵、组合优化等。
? 离散数学(Discrete mathematics)是数学的几个分 支的总称，以研究离散量的结构和相互间的关系 为主要目标，其研究对象一般地是有限个或可数 无穷个元素；因此它充分描述了计算机科学离散 性的特点。
– 离散数学通常研究的领域包括：数理逻辑、集合论、 关系论、函数论、组合学、代数系统与图论。 。
3

南邮通信网复习提纲及答案

第1章 1、传输系统的硬件包括哪些？ 线路接口设备、传输媒介、交叉连接设备等。 2、在垂直结构上，可以将通信网分为哪三层？ 应用层、业务网和传送网。 3、从水平分层观点来看，网络结构是基于用户接入网络实际的物理连接来划分的，如何划分？可以分为用户驻地网、接入网和核心网，或者分为局域网、城域网和广域网等。 4、利用网络的基本结构形式可以构成任意类型的非基本拓扑结构。实际常用的非基本结构形式有哪些？（1）复合网；（2）格形网；（3）树形网； 1、简述现代通信网的定义、构成要素和每一要素的基本功能。 （1）通信网是由一定数量的节点(包括终端节点、交换节点)和连接这些节点的传输系统有 机地组织在一起的，按约定的信令或协议完成任意用户间信息交换的通信体系。 （2）实际的通信网是由软件和硬件按特定方式构成的一个通信系统，每一次通信都需要软 硬件设施的协调配合来完成。从硬件构成来看：通信网由终端设备、交换设备和传输 系统构成，它们完成通信网的基本功能：接入、交换和传输。软件设施则包括信令、 协议、控制、管理、计费等，它们主要完成通信网的控制、管理、运营和维护，实现 通信网的智能化。 2、为什么要在通信网中引入分层结构？ （1）可以更清晰地描述现代通信的网络结构； （2）使网络规范与具体实施方法无关，从而简化了网络的规划和设计； （3）使各层的功能相对独立。 3、分别按以下标准对通信网进行分类：（1）通信服务的范围；（2）通信的活动方式。 （1）按通信服务的范围进行分类：本地通信网、长途通信网和国际通信网或局域网(LAN)、 城域网(MAN)和广域网(WAN)等。 （2）按通信的活动方式进行分类：固定通信网和移动通信网等。 4、通信网组网的基本结构形式有哪四种？假如网络节点数为N ，请写出每种结构的链路数。 （1）全连通网；）（1-2 1N N H = （2）星形网；1-N H = （3）环形网;N H = 5、一般通信网的质量要求可以通过哪几个方面进行衡量？影响接通的任意性和快速性的因素有哪些？ （1）对于一般通信网的质量要求可以通过以下几个方面来衡量:接通的任意性与快速性;信息传输的透明性与传输质量的一致性;网络的可靠性与经济合理性. （2）影响接通的任意性和快速性的因素有：通信网的拓扑结构;通信网的网络资源;通信网的可靠性.

组合数学与图论复习题与参考答案

组合数学与图论复习题及答案 1．Show that if n+1 integers are chosen form the set {1,2, …,2n},then there are always two which differ by at most 2. 从{1,2, …,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。 任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到2n 之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k大的另一个数。 2．Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100. 设52个整数a 1，a 2 ，…，a 52 被100除的余数分别是r 1 ,r 2 ,…,r 52 ，而任意一 个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将 r 1,r 2 ,…,r 52 放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj， 要么有ri＋rj＝100，也就是说ai－aj|100或者ai＋aj|100。 3．从1，2，3，…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。 鸽子洞原理，必有两个数相邻，相邻的两个数互质 4．Prove that Ramsey number R(p,q)≤R(p,q-1)+R(p-1,q). 令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。 在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者F中有R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)≤R(p,q-1)+R(p-1,q) 5．There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。 从10人中随意选一个人p，F表示与p相识的人，S表示与p不相识的人若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。 若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6．In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats? 6个男的先进行圆排列，然后6个女的插入空位。 7．In how many ways can 15 people be seated at round table if B refuses to sit next to A? What if B only refuses to sit on A right?

组合数学学习心得

组合数学学习心得 在进入研究生学习的第一个学期就开设了组合数学这门课程，我感到很庆幸和开心，因为我在学完这门课程之后学到了很多东西，不仅仅是课本上的，还有许多在课本上是学不到了！ 组合数学，对大多数学生来说是一门十分困难的课程，由于自己本科学的是数学，所以学起来还好，也比较喜欢这门课程。组合数学可以一般描述为：组合数学是研究离散结构的存在，计数，分析，和优化等问题的一门学科。经验证发现的组合数学最有力的工具之一为数学归纳法。归纳是一个强有力的过程，在组合数学中尤其是如此。用数学归纳法证明一个结果常常比证明一个弱结果更容易。许多组合问题的解决常常需要某些特别的例证，而且有时需要结合使用一般的理论。我们必须学会建立数学模型，研究模型，抓住问题的要害，灵活的应用智慧来解决问题。“图论”是组合数学课程中比较重要的一部分。在刚接触到“图”这一章的时候我是抱着好奇之心去学习的，因为这章都是关于“图” ，想了解一下和几何图形的差别，所以觉得善长几何的我应该能够把它学好。但是不可否认，随着知识的深入，这一章一定会比前面的更难理解，更难学。因此上课的时候听得格外认真，课后还找了一些相关书籍阅览。在看过这些书籍以后，我才真正了解到它并不是枯燥乏味的，它的用途非常广泛，并且应用于我们整个日常生活中。比如：怎样布线才能使每一部电话互相连通，并且花费最小？从首府到每州州府的最短路线是什么？n 项任务怎样才能最有效地由 n 个人完成？管道网络中从源点到集汇点的单位时间最大流是多少？一个计算机芯片需要多少层才能使得同一层的路线互不相交？怎样安排一个体育联盟季度赛的日程表使其在最少的周数内完成？我们能用4种颜色来为每张地图的各个区域着色并使得相邻的区域具有不同的颜色吗？这些问题以及其他一些实际问题都涉及“图论” 。这里所说的图并不是几何学中的图形，而是客观世界中某些具体事物间联系的一个数学抽象，用顶点代表事物，用边表示各式物间的二元关系，如果所讨论的事物之间有某种二元关系，我们就把相应的顶点练成一条边。这种由顶点及连接这些顶点的边所组成的图就是图论中所研究的图。由于它关系着客观世界的事物，所以对于解决实际问题是相当有效的。总之，图论是数学科学的一个分支，而四色问题是典型的图论课题。通过对图论的初步理解和认识，我深深地认识到，图论的概念虽然有其直观、通俗的方面，但是这许多日常生活用语被引入图论后就都有了其严格、确切的含义。我们既要学会通过术语的通俗含义更快、更好地理解图论概念，又要注意保持术语起码的严格。 学习数学重要的是理解，而不是像其它科目一样死背下来，数学有一个特点,那就是”举一反三”。做会了一道题目，就可以总结这道题目所包含的方法和原理,再用总结的原理去解决这类题，收效就会更好.学习数学还有一点很重要，那就是从基本的下手，稳稳当当的去练，不求全部题都会做，只求做过的题不会忘，会用就行了。在做题的过程中，学习是一生的事情，不要过于着急，一步一个脚印的来,就一定会取得一想不到的效果。数学的学习是一个积累和运用的过程，因此，学好数学的一个必要前提便是要注重平时的积累和运用。而在日常时对于数学的学习还是有许多方法的。数学学习做题是极为必要的，因此做题之后的总结工作也是极为重要的，否则只能是杂而不精，无法将知识融会贯通，合理运用。 组合数学是一门既古老又年轻的数学分支。组合数学不仅在基础数学研究中具有极其重要的地位，在其他的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。如果说微积分和近代数学

图论及其应用

图和子图 图 图 G = (V, E)， 其中 V = {νv v v ,......,,21} V ---顶点集， ν---顶点数 E = {e e e 12,,......,ε} E ---边集， ε---边数 例。 左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G 的几何实现（代表）， 它们有无穷多个。真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。不过今后对两者将经常不加以区别。 称 边 ad 与顶点 a (及d) 相关联。也称 顶点 b(及 f) 与边 bf 相关联。 称顶点a 与e 相邻。称有公共端点的一些边彼此相邻，例如p 与af 。 环（loop ，selfloop ）：如边 l 。 棱（link ）：如边ae 。 重边：如边p 及边q 。 简单图：（simple graph ）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。 记号：νε()(),()().G V G G E G ==。 习题 1.1.1 若G 为简单图，则 εν≤?? ?? ?2 。 1.1.2 n ( ≥ 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。 同构 在下图中， 图G 恒等于图H , 记为 G = H ? V （G)=V(H), E(G)=E(H)。 图G 同构于图F ? V(G)与V(F), E(G)与E(F)之间各存在一一对应关系，且这二对应关系保持关联关系。 记为 G ?F 。 注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。 d e f G = (V, E) y z w c G =(V , E ) w c y z H =(V ?, E ?) ?a ? c ? y ? e ?z ? F=(V ??, E ??)

组合数学与数论1

第一部分：组合数学 第一章计数的基本原则 一．组合数学的历史和内容 1.历史：组合数学最早起源于中世纪的印度，在漫长的历史中，一 直发展缓慢。随着上一世纪计算机的出现，组合数学开始快速地发展。近几年，由于计算机安全领域受到重视以及组合数学在计算机安全领域的应用，组合数学受到越来越多的重视。 2.内容：组合数学主要包括以下几个内容： (1)组合分析（也称为组合计数理论） (2)组合优化（包括线性规划，整数规划等） (3)组合设计（包括区组设计等） (4)组合算法（例如：搜索算法，DFS算法与分支定界法，动态规 划等） *图论本是组合数学这个家族的一个主要成员，但它已成长壮大，独立成一门学科。 3. 本课程介绍的主要内容：组合计数理论 二．加法原则与乘法原则 1. 加法原则： 设事件A有m种产生方式，事件B有n种产生方式，则“事件A 或事件B”有m+n种产生方式。 例子：大于0而小于10的偶数有4个，即：{2，4，6，8}，大于0而小于10的奇数有5个，即：{1，3，5，7，9}。则大于0而小于10

的整数有：4+5=9个，即：{1，2，3，4，5，6，7，8，9}。 *如果A1,A2,?,A n是互不相交的有穷集，那么 |A1∪A2∪?∪A n|=|A1|+|A2|+?+|A n| 2.乘法原则： 若事件A有m种产生方式，事件B有n种产生方式，则“事件A 与事件B”有mn种产生方式。 例1：设一个符号由两个字符组成，第一个字符有a,b,c,d,e五种方式，第二个字符有1,2,3三种方式。则根据乘法原则，该符号具有5×3= 15种方式，即 a1,b1,c1,d1,e1;a2,b2,c2,d2,e2;a3,b3,c3,d3,e3. 例2：从A到B有3条不同的道路，从B到C有2条不同的道路，从A经B到C共有n=3×2=6条不同的道路。 例3：求比10000小的正整数中含有数字1的数的个数。 解：先求所有4位数中不含有数字1的个数，即求由{0，2，3，4，5，6，7，8，9} 9个数字组成的4位数的个数。每一位都有9种出现方式，根据乘法原则，由9个数字组成的4位数个数为：9×9×9×9= 6561，其中包含0000不是正整数。故比10000小不含数字1的4位正整数的个数=6561?1=6560. 所以小于10000含有数字1的4位数个数=9999?6560=3439.