图论基础知识

第一篇：图论基础知识

图论基本知识

对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的„„这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献[1-5]。

本章只给出非平凡的定理的证明，过于简单直观的定理的证明将留给读者。个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。

图的基本概念

图G是指两个集合(V，E)，其中集合E是集合V×V的一个子集。集合V称为图的顶点集，往往被用来代表实际系统中的个体，集合E被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。若{x,y}E，就称图G中有一条从x到y的弧（有向边），记为x→

y，其中顶点x叫做弧的起点，顶点y叫做弧的终点。根据定义，从任意顶点x到y至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。如果再假设图G中不含自己到自己的弧，我们就称图G为简单图，或者更精确地叫做有向简单图。以后如果没有特殊的说明，所有出现的图都是简单图。记G中顶点数为(G)|V|，边数为(G)|E|，分别叫做图G的阶和规模，显然有(G)(G)((G)1)。图2.1a给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。

图2.1：网络拓扑结构示意图。图a是10阶有向图，顶点集为{1,2,3,4,5,6,7,8,9,10}，边

集

为{1→2,1→3,1→4,2→5,2→6,2→7,3→6,4→7,4→8,6→9,7→9,8→10}；图b是6阶无向图，顶点集为{1,2,3,4,5,6}，边集为{13,14,15,23,24,26,36,56}。

从定义中可以看到，从任意顶点x到y不能连接两条或以上边，本文所讨论的图，均符合上述要求，既均为不含多重边的图。如

果弧x→ y与弧y→ x要么同时存在，要么同时不存在，我们就把这两条弧合为一条边，记为xy或yx，这样的图叫做无向图（对称图），可以被看作上述一般图（有向图）的一种特例。显然，对无向图而言，有(G)(G)((G)1)/2，其中(G)表示无向图G中边的数目。图2b给出了一个无向图的示意。以后提到的图，若没有特别的说明，均指无向图。下面介绍的大部分结论都可以自然地从无向图推广到有向图，勿需重复叙述，对于那些本质上有差异的特性，我们会在文中明确指出。

对于两个图G(V,E)和G'(V',E')，如果V'V,E'E，就称G'是G的子图。若V'V，则称G'是G的生成子图；若在G中所有连接集合V'中两顶点的边都出现在集合E'，则称G'是G的导出子图，记为G'G[V']。如果图H与图G有相同的顶点集，并且图H中两点之间有边相连（相邻）当且仅当在G中这两点是不相邻的，就称图H是图G的余图，记做HG。拥有Cn条边的n阶无向图或拥有Pn条边的n阶有向图叫做完全图，用符号Kn表示，其余图Kn叫做空图。

在无向图G中，与某顶点x关联的所有边的数目叫做x的度，用符号dG(x)表示，在不致混淆的时候，可以简单地记为d(x)。对于有向图，由于需要区分从顶点出去的弧和进入顶点的弧，所以不能简单地用度表示。我们把以顶点x为起点的弧的数目叫做x的出度，把以

d(x)dxx顶点为终点的弧的数目叫做的入度，分别记为和(x)。顶点

22度与边之间有一个显然的关系：

定理2.1：对于无向图G(V,E)有：

(2.1)对于有向图G'(V',E')有：

(2.2)

xV'd(x)2(G)xV

d(x)d(x)(G')xV'

在图G中，以x为起点，y为终点的xy路P是指一系列首尾相连的边组成的集合：E(P){x0x1,x1x2,,xl1xl}

其中x0x,xly，xixj,0ijl。边的数目l被称作路P的长度。如果x0xlE，则称边集{x0x1,x1x2,,xl1xl,xlx0}为圈，其长度为l1。G中最短的xy路的长度称为点x,y的距离，记为dG(x,y)，如果G中不存在xy路，则记d(x,y)。称无向图（有向图）G为连通图（强连通图），如果对G中任意两个不同顶点x,y，都能够找到至少一条xy路。有向图G被称为连通图，如果对G中任意两个不同顶点x,y，至少能找到一条xy路或yx路。

若图G(V,E)的顶点集V可以拆成两个不相交的子集VV1V2，且E中不含两端点同时位于V1中或同时位于V2中的边，就称图G为二部分图。容易证明：

定理2.2：G是二部分图当且仅当G中不含奇圈。

如果图G不含圈，我们就称其为森林，若它同时还是连通图，则被叫做树。定理2.3至定理2.5给出了树的基本性质。

定理2.3：下面几个命题是等价的：(1)G是树；

(2)G是最小连通图，也就是说，任意去掉一条边，G都会变成非连通图；

(3)G是最大无圈图，也就是说，任意加上一条边，G都会变成含圈图；

(4)G是连通图，且G中任意两顶点之间有且只有一条路。定理2.4：n阶树有n1条边。

定理2.5：阶数大于1的树至少有两个度为1的顶点。

直径、平均距离、簇系数与度分布

对复杂网络的研究最早始于对真实网络诸如直径、平均距离、簇系数等参数的取值以及顶点度分布的性质的实证研究，后续的大量研究也是围绕这些概念进行的，因此有必要详细地介绍这些概念的定义以及相关的基本结论，这些介绍将有助于我们更好地理解当前复杂网络研究的物理意义。

在分析传输网络的性能与效率时，有两个因素总是受到特别的关注，即最大传输时延与平均传输时延。在图理论中，它们被近似地抽象为两个参数：直径与平均距离。图G(V,E)的直径与平均距离可分别表为：

d(G)max{dG(x,y)}x,yV

(G)1dG(x,y)v(v1)x,yV

为了叙述方便，后文中使用(G)来代替有关(G)的讨论，其中

(G)v(v1)(G)。

关于图直径和平均距离的研究可以追溯到半个世纪前，Ore给出了无向图直径一个漂亮的紧界[6]，Entringer,Jackson,Slater和Ng,Teh分别就无向图和有向图的情形给出了图平均距离粗糙但具有开创意义的下界[7,8]，再往后Plesnik给出了平均距离只依赖于阶数和直径的下界[9]。Zhou等人通过一种新的构造分析方法，给出了Ore定理的简单证明，此方法可以无困难地将Ore定理推广到有向图形式。利用类似的分析方法，可以得到k直径图平均距离的下界定理，Entringer，Ng等人的结果可以作为该定理的一个自然的推论给出。结合此定理与Ore定理，可以只依赖于阶数和直径的平均距离下界，该下界是目前已知的最好的下界[10-11]。

Ore通过类似于构造广度优先树的方法将无向图分割成一圈圈的等距子图，其证明手法是优美而繁复的。由于其构造中隐含了dG(x,y)dG(y,x)的条件，因此无法直接推广到有向图的形式。

显然，任何v阶图都可以看作从完全无向图或完全有向图中移走若干条边后得到的，下面将从这一简单而直观的角度出发，给出 Ore定理的简单证明。

定理2.6[6,10-11]：对任意无向(v,k)图G，有：

(2.3)

(G)k(vk4)(vk1)12

其中(v,k)图是指阶数为v，直径为k的简单有限图。

证明：用(v,k)表示要得到无向(v,k)图至少需要从完全图Kv中移

走的边的数目，则对任意无向(v,k)图G，有：

(G)(Kv)(v,k)

(2.4)令P{x0,x1,x2,,xk}为G中长为k的最短路，由P的最短性易知P1k(k1)xi,xj|ij|12中两点不相邻，若。这就意味着至少有条边必须从Kv中移走以得到图G。同样由P的最短性知，对于不在P中的顶点x，若P中两点xi,xj满足|ij|2，则x不能同时与xi,xj相邻，即x最多与P中形如xi,xi1,xi2的三个顶点相邻。换句话说，P中至少有(k2)个点不与x相邻。由于G中不在P上的顶点数为(vk1)，即有至少(vk1)(k2)条边必须从Kv中移去以得到G。综上可知：

(2.5)结■ 合(v,k)k(k1)(vk1)(k2)12

(2.4)(2.5)即得(2.3)式。

利用同样的分析方法，可以得到Ore定理的有向图形式，证明略。定理2.7[10-11]：对任意强连通有向(v,k)图G，有：

(2.6)

(G)v(vk1)(k2k4)12

下面两个定理将给出平均距离的下界，由于证明比较复杂，此处省略。

定理2.8[10-11]：设G为无向(v,k)图(k2)，若G的规模为，则有：

(2.7)

112v(v1)2k(k1)(k2)(vk1)(k2)(k4)k为偶32(G)2v(v1)2＋1k(k1)(k2)1(vk1)(k3)2 k为奇32

定理2.9[10-11]: 对任意无向(v,k)图G，有：

112v(v1)2kk(k1)(k2)(vk1)(k24k2v)k为偶32(G)2v(v1)2k1k(k1)(k2)1(vk1)(k24k2v1)k为奇32

(2.8)有向图的下界可以类似的得到，此处不再赘述。

图的簇系数是衡量图的成团特性的参数。对于无向图G(V,E)，记某顶点x的邻点集合为A(x)，显然d(x)|A(x)|，顶点x的簇系数被定义为它所有相邻节点之间连边的数目占可能的最大连边数目的比例，即：

CG(x)2(G[A(x)])d(x)(d(x)1)

图G的簇系数则被定义为所有顶点簇系数的平均值：

C(G)1C(x)(G)xVG

在下一节我们可以通过随机图论的方法，得到关于簇系数的一些基本性质。

对于无向图G(V,E)，记度为k的顶点数目为P(k)，则p(k)P(k)(G)给出了图G的顶点度分布。类似地，关于顶点度分布的基本性质，需要到第三节才能给出。

随机图的基本模型与主要结论

随机图论起源于20世纪40年代一些零星的文章，其中Sezle的文章给出了目前已知的最早利用概率方法证明的非平凡的图论定理[12-14]。1959年到1961年，Erdös和Rényi三篇著名的文献，使得随机图论开始成为图论一个正式的分支，他们所构建的随机图的模型在后来被称作ER模型[15-17]。下面的三篇重要文献向我们展现了随机图论的全貌，也包含了我们将要讨论到的大部分问题[1,18-19]。

考虑一个n阶无向图G(V,E)，Erdös和Rényi给出了两种相似但又不完全相同的随机图的模型。如果任意两点之间独立地以概率p连边，以概率q(1p)不连边，就得到第一种ER随机图，习惯上记做Gn,p；如果完全随机地选择m条边作为边集E，则得到第二种ER随机图，习惯上记做Gn,m。本节主要讨论Gn,p的性质，其中大多数的结论对于图Gn,m也是适用的（这里显然有

mpn(n1)2）。

设n且p0（实际物理应用时只需要n足够大，p足够小既可以近似地求解），使得节点平均度zp(n1)为有限常数。只需注意到任意节点度为k的概率为

n1kzkezn1kpkp(1p)k!

k

(2.9)即可得到下面显然但却常用的定理：

定理2.10：若Gn,p满足n，p0且zp(n1)为有限常数，则

其度分布为均值为z的泊松分布，因此Gn,p常被叫做泊松网络。

我们将图的顶点标号，以便彼此区别，对于某个k阶图F，NF被定义为Kk中与F同构的图的数目。定理2.11给出了在Gn,p中特定结构出现的频次。

定理2.11：记XF为图Gn,p中与F同构的子图的数目，则XF的期望值为：

nk!(F)Ep(XF)pka

(2.10)其中a是F自同构群的阶数。

nk!NFEp(XF)NFp(F)ka，证明：显然有，且根据同构计数原理有故■ 可得（2.10）式。

定理2.11虽然简单，但是是随机图论最基本的定理之一，有着广泛的应用。作为例子，下面我们给出定理2.11两个直接的推论。

推论2.12：记Xs为Gn,p中子图Ks的数目，则有：

sn2Ep(Xs)ps

(2.11)推论2.13：记Xk为Gn,p中导出子图为k圈图的点集数目，则有：

nk!kk(k3)2Ep(Xk)pqk2k

(2.12)

需要提醒注意的是，由于推论2.13中要求的是导出子图，所以k(k3)2q多了一个因子。

仍然假设n，用n,p表示第一种ER随机图构成的概率空间，定理2.14给出了一个似乎不那么直观但易于证明的结果。

(hk)为给定的自然数，定理2.14：设h1则在n,p中几乎所有（概率趋于1）图都满足：对于任意一个长度为k的点序列，图中至少存在一个点，它与前h个点相邻，而与后(kh)个点不相邻。

证明：我们考察“存在一个长度为k的点序列，使图Gn,p中不存在任何点，它与前h个点相邻，而与后(kh)个点不相邻”的概率。长度为k的点序列的不同选取方法共有(n)kn(n1)(nk1)种，对于某个选定的点序列，没有任何顶点与前h个点相邻，而与后(kh)个

hkhnk(1pq)。故有： 点不相邻的概率为

(2.13)此■ 结limlim(n)k(1phqkh)nklimnk(1phqkh)nk0nnn

论与定理2.14等价。

由定理2.14可以得到一些有趣的推论：

推论2.15：对给定的正整数k，几乎所有图Gn,p都满足(G)k，其中(G)表示G的最小度。

推论2.16：几乎所有图Gn,p的直径都为2。

对某种性质Q，如果在任意具有该性质的图上添加一条边后得到的图依然具有性质Q，则称性质Q是单调递增的性质。Erdös和Rényi 的研究表明，随着p的增加，很多单调递增的性质会以某种很突然的方式涌现。对于给定的单调递增的性质Q，称pl(n)为n,p的下极限函数，如果当ppl(n)时，几乎所有图Gn,p都不含性质Q；类似地，称pu(n)为n,p的下极限函数，如果当ppu(n)时，几乎所有图Gn,p都含有性质Q。

事实上，在很多情况下，下极限函数和上极限函数靠得非常近，因此我们才说相应的性质出现得非常突然。物理学家往往把这种现象看作一种相变，定理2.17给出的例子就可以被看作从不连通相向连通相的一个突变。

定理2.17：记(n),且(n)logloglogn，令pupl1(logn(n))n，1(logn(n))n，则几乎所有的图Gn,pl都不连通，而几乎所有的u图Gn,p都连通。

这里我们不打算给出定理的证明，但需要特别强调的一点是，很多物理学家在研究网络时依然保留着在推导定理后再设计实验进行验证的习惯，这种习惯在网络研究中是危险的，因此必须特别地谨慎。比如对于定理2.17，Bollobás认为n必须足够大以保证(n)10，这种量级的n显然不是当前计算机能力所能处理的。因此，如果只是随便选取n10或10进行实验，那么不管结果怎样，都只是一种假象。

下面的定理给出了一个经典的相变图景，物理学家关于逾渗模型[20-21]很多重要的结论可以作为该定理的一个自然推论或利用类似的分析方法容易地得到。

定理2.18：考虑一个每次在图G上随机添加一条边的随机过程，Gn(n1)2其生成的图序列记为Gt，显然G0为空图，为完全图。令c0,h1cn2，为确定的常数，(n)与定理2.17一致。取c1logc,tt(n)有：

如果c1，则对任意的1ih和几乎所有的图Gt，有：

L(i)(Gt)15lognloglogn(n)2

(2.14)(1)(2)L(G)L(G)是图G各连通片按阶的大小排成的非增序其中列。

存在常数0c1c2，对任意的1ih和几乎所有的图

(2.15)如果c1，则对几乎所有的图Gt，有：

(2.16)其中，0(c)1，唯一地由式(2.17)决定：

L(1)(Gt)n(n)n1223c2n23L(i)(G)cn2n2Gn2，有：

ce1

(2.17)进一步的，对所有2ih，式(2.14)成立。

定理2.18的证明请参考文献[16]，更细致的研究结果请参考

第二篇：《离散数学》图论部分习题

《离散数学》图论部分习题

1.已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问G至少有几个顶点？并画出满足条件的一个图形.（24-3*6）/2 +6=9 2.是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶无向简单图G中最大度≤6 3.设d1、d2、…、dn为n个互不相同的正整数.证明：不存在以d1、d2、…、dn为度序列的无向简单图.Max{d1，d2，…，dn}≥n，n阶无向简单图G中最大度≤n-1 4.求下图的补图.5.1)试画一个具有5个顶点的自补图

2)是否存在具有6个顶点的自补图，试说明理由。

对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整 数，n=4k或n=4k+1，不存在6阶自补图。

6.设图G为n(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现

7.无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。

只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分支上，每个分支上仅有一个奇度顶点，与握手引理相矛盾。

8.图G如下图所示：

1)写出上图的一个生成子图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v)| vV } ；κ(G)=min{ |V’| |V’是图G的点割集} ； λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下无向完全图Kn为欧拉图？

n为奇数时

10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数； 桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分支上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分支上只有一个奇度顶点，与握手引理矛盾。

11.证明：有桥的图不是哈密尔顿图.若G是K2，显然不是哈密尔顿图；

否则n≥3，则桥的两个端点u和v至少有一个不是悬挂顶点（容易证明悬挂顶点不是割点）；设u不是悬挂点，则u是割点，存在割点显然不是哈密尔顿图。

12.树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？

X+2*4+3*3=2*（2+3+x-1）

x=9 13.证明：最大度Δ（T）≥k的树T至少有k片树叶。

设有n个顶点，其中x片树叶

2*（n-1）≥1*K+（n-x-1）*2+x*1

x≥k 14.已知具有3个连通分支的平面图G有4个面，9条边，求G的阶数.n-9+4=3+1

n=9

15.给出全部互不同构的4阶简单无向图的平面图形。

16.如果G是平面图, 有n个顶点、m条边、f个面，G有k个连通分支。试利用欧拉公式证明:：n-m+f=k+1.

第三篇：《矿井通风网络图论》教学大纲

《矿井通风网络图论》教学大纲

课程中文名称：矿井通风网络图论 课程英文名称：Mine Ventilation network

theory 课程类别：专业课

课程编号: 课程归属单位：矿业学院 制定时间： 2006年9月2日

一、课程的性质和任务

1.课程的性质：本课程为采矿工程、安全工程专业本科生的专业选修课。

2.课程的任务：通过本课程的学习，要求学生掌握有关图论的基本概念，网络的基本数学模型，扇风机的运转数学模型。理解网络自然分风的算法框图，并利用所学的计算机程序设计语言编制、解算。另外，通过本课程的学习，学生必须熟练将矿井通风系统图绘制为通风网络图。

3、教学的基本要求

通过本课程的学习，学生应该掌握集合及其基本运算、矩阵代数基础、图论的基本知识、矿井通风网络的基本数学模型、扇风机的运转数学模型。学习通风网络理论的目的，主要是掌握通风网络绘制的基本规律和计算方法，为解决实际通风问题奠定基础。

1）课程的重点及难点：本课程的重点是讲解利用图论的知识绘制矿井通风网络图。难点是根据实际问题建立矿井通风网络数学模型。

2）课程的教学方法：课堂教学主要讲解图论的基础知识，介绍基本的通风网络数学模型。课外布置一定量习题供学生练习外。

3）课程的学习方法：要通过理论与方法学习、习题练习这两个基本环节，来熟练掌握把矿井通风系统图绘制为通风网络图。

4、适用专业及学分（学时）： 采矿工程、安全技术及工程, 2学分/36学时

5、本课程与其他课程的关系：矿井通风网络图论是一门与自然科学和应用技术两者相联系的边缘科学,是平行于工程数学、计算机科学、矿井通风等独立的学科, 必须先修完《工程数学》、《矿井通风》、《高级计算机语言程序设计》等课程。

6、教材、教学参考书： 教材： 贵州大学矿业学院采矿工程教研室自编教材。参考书：

1）《矿井通风系统优化原理与设计计算方法》 徐竹分编著 冶金工业出版社； 2）《通风网络理论》徐瑞龙编著 煤炭工业出版社；

3）《矿井通风网络分析及电算方法》谭国辽 煤炭工业出版社。

7、主要教学方法与媒体要求：课堂教学主要讲解矿井通风网络基本模型。课外布置一定量习题供学生练习。

二、课程内容

第一章 集合与矩阵代数基础（4学时）

（一）、基本内容：

集合及其基本运算、矩阵代数基础。

（二）、要求学生掌握的基本概念、理论、原理：

1、掌握集合概念及其表示方法。

2、了解集合基数、有限集、无限集、空集的概念。

3、掌握集合间的关系。

4、掌握集合的运算。

5、了解集合的图解表示法。

6、掌握集合的运算律。

7、向量及线性空间。

8、矩阵及矩阵的秩。

9、矩阵的运算。

10、分块矩阵。

（三）、本章教学重点和难点：

向量及线性空间、矩阵及矩阵的秩、矩阵的运算、分块矩阵。第二章 图论基础（6学时）

（一）、基本内容：

图的基本概念、图的矩阵表示、生成树的选择。

（二）、要求学生掌握的基本概念、理论、原理：

1、了解图的定义和术语、同构和子图的概念。

2、掌握道路和回路的概念。

3、掌握树的概念。

4、掌握割集的概念。

5、掌握图的节点邻接矩阵。

6、掌握关联矩阵、回路矩阵和割集矩阵，了解图的关联、回路、割集矩阵间的关系。

7、掌握生成树选择。

8、掌握独立回路选择。

9、掌握生成数目的计算。

（三）、本章教学重点和难点：

图的节点邻接矩阵、关联矩阵、回路矩阵、割集矩阵、生成树选择、独立回路选择。第三章 矿井通风网络

（6学时）

（一）、基本内容：

矿井通风网络图、矿井通风网络基本数学模型。

（二）、要求学生掌握的基本概念、理论、原理：

1、掌握矿井通风系统。

2、熟练掌握矿井通风网络图。

3、了解矿井通风网络的有关子网络。

4、了解矿井通风网络在电子计算机中的存贮。

5、掌握矿井通风网络内空气流动的基本规律。

6、掌握矿井通风网络的基本数学模型。

（三）、本章教学重点和难点：

矿井通风网络图、矿井通风网络内空气流动的基本规律、矿井通风网络的基本数学模型。第四章 矿井通风机运转特性及分析

（6学时）

（一）、基本内容：

通风机工作特性数学描述、通风机工况点求解与分析。

（二）、要求学生掌握的基本概念、理论、原理：

1、掌握通风机的特性方程。

2、掌握通风机特性方程的确定。

3、了解通风机特性方程的变换。

4、掌握通风机工况点参数的求解方法。

5、掌握通风机工况分析。

（三）、本章教学重点、难点：

通风机特性方程及其确定、通风机工况点参数的求解方法。第五章 通风网络工况的计算与分析（6学时）

（一）、基本内容：

网络自然分风数学模型、计算方法。

（二）、要求学生掌握的基本概念、理论、原理：

1、掌握网络自然分风数学模型。

2、了解斯考德－恒斯雷法。

3、掌握牛顿法。

4、了解两种计算方法的分析。

（三）、本章教学重点与难点： 网络自然分风数学模型和牛顿法。第六章 通风网络风流控制与调节（8学时）

（一）、基本内容：

矿井通风网络的风流控制、调节方法、风量调节计算、井下发生火灾时期的风流控制。

（二）、要求学生掌握的基本概念、理论、原理：

1、掌握矿井通风网络的风流控制。

2、掌握调节方法。

3、掌握自然分风子网络的风量计算。

4、掌握风量调节计算。

5、掌握火灾时期受灾区域的确定。

6、掌握火灾时期风流控制的基本要求和原则。

（三）、本章教学重点、难点：

矿井通风网络的风流控制、调节方法、风量调节计算、火灾时期受灾区域的确定、火灾时期风流控制的基本要求和原则。

五、考核

闭卷考试（考试成绩除笔试外，还包括平时上课、作业和实验成绩）。

第四篇：图论在道路建设中的应用

龙源期刊网 http://.cn

图论在道路建设中的应用

作者：张可波 郑大斌

来源：《科技创新导报》2012年第03期

摘要：在修建道路的过程中，如何既保证各地之间运输的需求又节约资源。这就是我们需要解决的问题。本文从当前我国经济已经进入到了一个以资源节约．提高效率为主的时代的前提出发。利用图论中的相关理论。较好地解决了道路网的量优化修建问题．井对这一类问题的解决提供一种新的思路。

关键词；道路建设 最优化

最小生成树Dijkstra算法 Greedy算法

第五篇：离散数学图论习题

第4章图论

综合练习

一、单项选择题

1．设L是n阶无向图G上的一条通路，则下面命题为假的是()．

(A)L可以不是简单路径，而是基本路径

(B)L可以既是简单路径,又是基本路径

(C)L可以既不是简单路径，又不是基本路径

(D)L可以是简单路径，而不是基本路径

答案：A

2．下列定义正确的是()．

(A)含平行边或环的图称为多重图(B)不含平行边或环的图称为简单图

(C)含平行边和环的图称为多重图(D)不含平行边和环的图称为简单图答案：D

3．以下结论正确是()．

(A)仅有一个孤立结点构成的图是零图

(B)无向完全图Kn每个结点的度数是n

(C)有n(n>1)个孤立结点构成的图是平凡图

(D)图中的基本回路都是简单回路

答案：D

4．下列数组中，不能构成无向图的度数列的数组是()．

(A)(1,1,1,2,3)(B)(1,2,3,4,5)(C)(2,2,2,2,2)(D)(1,3,3,3)

答案：B

5．下列数组能构成简单图的是()．

(A)(0,1,2,3)(B)(2,3,3,3)(C)(3,3,3,3)(D)(4,2,3,3)

答案：C

6．无向完全图K3的不同构的生成子图的个数为（）．

(A)6(B)5(C)4(D)

3答案：C

7．n阶无向完全图Kn中的边数为（）．(A)n(n1)n(n1)(B)(C)n(D)n(n+1)2

2答案：B

8．以下命题正确的是()．

(A)n(n1)阶完全图Kn都是欧拉图

(B)n(n1)阶完全图Kn都是哈密顿图

(C)连通且满足m=n－1的图(V=n,E=m)是树

(D)n(n5)阶完全图Kn都是平面图

答案：C

10．下列结论不正确是()．

(A)无向连通图G是欧拉图的充分必要条件是G不含奇数度结点

(B)无向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点

(C)有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度

(D)有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等

1于出度 答案：D

11．无向完全图K4是（）．

（A）欧拉图（B）哈密顿图（C）树答案：B

12．有4个结点的非同构的无向树有()个．

(A)2(B)3(C)4(D)5 答案：A

13．设G是有n个结点，m条边的连通图，必须删去G的()条边，才能确定G的一棵生成树．

(A)mn1(B)nm(C)mn1(D)nm1 答案：A

14．设G是有6个结点的完全图，从G中删去()条边，则得到树．(A)6(B)9(C)10(D)15 答案：C

二、填空题

1．数组{1，2，3，4，4}是一个能构成无向简单图的度数序列，此命题的真值是.答案：0

2．无向完全图K3的所有非同构生成子图有个． 答案：

43．设图GV,E，其中Vn,Em．则图G是树当且仅当G是连通的，且m． 答案：n－

14．连通图G是欧拉图的充分必要条件是 答案：图G无奇数度结点

5．连通无向图G有6个顶点9条边，从G中删去G的一棵生成树T． 答案：4

6．无向图G为欧拉图，当且仅当G是连通的，且G中无 答案：奇数度

7．设图GV,E是简单图，若图中每对结点的度数之和，则G一定是哈密顿图． 答案：

8．如图1所示带权图中最小生成树的权是．

答案：1

2三、化简解答题

1．设无向图G＝，V={v1，v2，v3，v4，v5，v6}，E={(v1，v2),(v2，v2),(v4，v5),(v3，v4),(v1，v3),(v3，v1),(v2，v4)}．(1)画出图G的图形；

图

1图

2(2)写出结点v2, v4，v6的度数；(3)判断图G是简单图还是多重图．解：(1)图G的图形如图5所示．

(2)deg(v2)4,deg(v4)3,deg(v6)0．

(3)图G是多重图．作图如图2.2．设图G＝，其中

V＝{a,b,c,d,e}, E={(a,b),(b,c),(c,d),(a,e)}

试作出图G的图形，并指出图G是简单图还是多

重图？是连通图吗？说明理由.be

解：图G如图8所示．.图G中既无环，也无平行边，是简单图． cd 图G是连通图．G中任意两点都连通.图

3所以，图G有9个结点．作图如图3．

四、计算题

1．设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图．

解：设图G有x个结点，由握手定理

21+22+34+3（x223）＝12

23x24211827x＝9 故图G有9个结点． 图

4满足该条件的简单无向图如图4所示

2．设图G(如图5表示)是6个结点a,b,c, d,e,f的图，试求，图G的最小生成树，并计算它的权．

c 解：构造连通无圈的图，即最小生成树，用

克鲁斯克尔算法：

第一步： 取ab＝1；第二步： 取af=4第三步： 取fe＝3；第四步： 取ad=9图5第五步： 取bc=2

3如图6．权为1+4+3+9+23=40

3．一棵树T有两个2度顶点，1个3度顶点；3个4

问它有几片树叶？

解：设T有n顶点，则有n－1条边．T中有2个 2度顶点，1个3度顶点，3个4度顶点，其余n－2－1-3个1度顶

点．

由握手定理： 2·2+1·3+3·4+(n－2－1-3)=2(n－1)解得 n=15．于是T有15-6=9片树叶

五、证明题

1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的．

证：用反证法．设G中的两个奇数度结点分别为u和v．假若u和v不连通．

即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点．这与握手定理的推论矛盾．因而u和v一定是连通的．