脑网络研究中的图论指标详解_69

人脑是自然界中最复杂的系统之一, 在复杂系统研究方面，网络研究的方法在21世纪以来被深度应用在多个领域；

在神经科学研究领域中，无论从微观的多个神经元、神经元集群的角度看还是从宏观的多个脑区相互连接成庞杂的结构网络和通过相互作用构建的功能网络看，网络方法都已经延伸到了神经科学研究中的方方面面。

在网络研究中，通过图论方法来表征复杂网络的拓扑关系是研究网络中不同节点、不同连边以及网络的整体特性的重要手段。

但在实际的研究中，研究者往往根据自己的研究目的特定地选择网络属性，因而导致很多研究人员无法全面的了解图论研究中多种指标的实际含义；

同时，随着图论方法的发展，许多新的指标也不断出现。全面和准确的理解图论指标对于使用图论方法研究复杂网络具有重要的意义，只有选对指标才能更好地说明你的研究问题，达到事半功倍的效果。

因此，思影科技汇总了当前网络研究中被研究者经常使用的图论指标，并结合图表示、数学公式的严格定义以及解析的方法对每个指标进行了详述，以更好的帮助各位希望使用网络方法和图论指标进行脑科学研究的研究者。

首先我们来简单的回顾下网络中的不同对象，以便在后文阅读中能够清楚不同术语所描述的网络对象。

下图是一个由11个节点组成的网络，即圆圈，它们表示了网络中的基本对象，连接不同的节点的连线被称为“边”；

在脑网络研究中，节点是被按照不同分割依据所分割的脑区，连边在功能网络中往往通过对不同脑区的时间序列信号的相关计算所得，而结构网络中分为DTI连接和基于灰质变化的协变网络连边。

在这个小的网络中，我们可以看到不同节点由数量不等的连边互相连接起来，为了能够全面的分析这个网络的拓扑结构，我们需要使用不同的图论指标。

接下来我们来一起了解不同的网络指标。

（1）度（node degree）

在网络研究中，最基本和最广泛使用的度量指标是“度”，对于给定节点，度就是与它连接的邻居个数。第i个节点的度计算公式是：

这里，Cij表示节点i和节点j之间的连接状态，当节点i和节点j之间有连接时，Cij=1,当节点i和节点j之间无连接时，Cij=0；

此度量只适用于二值网络（加权网络应用该指标时，作为二值化网络来考虑），它只考虑连接的存在或不存在，不考虑任何权重信息。

参照上图，节点内的值代表节点度，即和此节点有连接的节点个数（或者该节点存有的边的数目，两者是一致的）。

节点度是图论中一个基础的指标，许多指标在计算中都要使用节点度的信息来描述网络中更高阶的拓扑关系。

（2）节点强度

节点强度和节点度密切相关，原因是节点强度也会计算给定节点的邻居个数，但是会把连接权重（例如平均FA值等）考虑进去；第i个节点的强度被定义为连接到它上的所有边的权重之和。

这里，Wij代表节点i和节点j之间的连接权重；

参照上图，节点内的值代表节点强度，由连接到它们的边（粗线为1，细线为0.5）的权重决定。在实际研究中，对加权网络会常常使用节点强度来度量节点的重要性。（3）节点核心

如果我们考虑一个迭代过程，将网络中具有某一度值的节点依次从网络中剥离，会得到一个具有最小度值为k的子网络--被称为k度核；

如果一个节点属于k度核，但是不属于k+1度核，那么它的节点核心就等于k。

参照上图，第一步移除所有度值为1的节点，第二步移除所有度值为2的节点，留下了一个最小度值为3的网络；外侧4个节点（红色）的节点核心等于3，因为它们属于3度核，而且不属于4度核。

节点核心指标可以表示网络中所有节点的节点度特性，往往被用在核心网络发现和节点排序中。（4）富人俱乐部系数（rich club coefficient）

富人俱乐部指的是网络中度值高的节点之间的连接，往往表示出比度值低的节点之间的连接更加紧密的趋势，这些高度值的节点在大脑全局交流中具有重要的作用。

在实际应用中，我们往往通过k度核的方法筛选出那些高度值的节点作为富人俱乐部的成员节点，因此，整个网络就可以被分为rich节点和非rich节点。

一种衡量的方法是连接形式，将rich-club节点之间的连接称为Rich-club 连接；将rich-club与非rich-club节点之间连接称为Feeder连接；将非

rich-club节点之间的连接称为Local连接。

而为了更好的研究rich-club节点之间的连接，可以计算富人俱乐部系数。

该指标是通过将网络分割成等度的节点，然后使用k度节点之间的连接数除以k度节点之间所有可能的连接数，将这个比值作为富人俱乐部系数，该系数越大表明rich-club节点之间的连接更加紧密。

（5）同配系数

同配系数建立在度值矩阵的基础之上，因为它描述了连接节点对的度之间的相关性。在不改变节点度分布的情况下，可以使度大的节点倾向于和其它度大的节点连接。

网络中的这个重要的结构特性，称之为节点之间的相关性(Correlation)。

如果网络中的节点趋于和它近似的节点相连，就称该网络是同配的(Assortative)；反之，就称该网络是异配的(Disassortative)。

网络同配性(或异配性)的程度可用同配系数(也称Pearson

Coefficient----皮尔森系数)r来刻画。

r>0表示整个网络呈现同配性结构，度大的节点倾向于和度大的节点相连；r<0表示整个网络呈现异配性；r=0表示网络结构不存在相关性。

参照上图，第一张图里的红色节点同配系数是正值，因为它与和自身有相同度的节点连接；

而第二张图里的红色节点同配系数是负值，因为它连接的节点，其度值和自身不相似，因为它自身的度值比它连接的度值小的多;

注意，大的多时也是一样的情况，总之就是要衡量是否是相同度值的节点互相连接。（6）特征路径长度

路径长度是网络分析中使用的一种距离，它描述了连接一对节点所需的“步骤”的数量，例如，下图中节点A和B之间的路径长度值为3意味着它们之间有3条边。

。

节点对之间通常有多个可能的路径，有时计算最短可能的路径长度-即最少边数，也被称为最短路径长度。

参照上图，可以看出节点A与B之间的最短路径长度用2条红色边表示。

特征路径长度是指所有节点对之间所有最短路径长度的平均值。为了获得特征路径长度的表达式，首先对网络中所有节点之间的最短距离(D)求和，以获得总路径长度CT。

为了得到特征路径长度，需要计算CT的平均值。一个节点连接到除它自身外其他所有节点，这样每个节点会有n-1个连接（n是网络中的节点数）。因此，特征路径长度为：

特征路径长度是网络的全局特征，特征路径长度越小表明网络的信息传输速度越快，该指标往往被用在计算“小世界”属性这一指标。

（7）全局和局部效率

“全局效率”是信息流的标量度量，被定义为给定网络中所有最短路径长度的逆。

局部效率和全局效率的计算方法类似，不过它是在单个节点水平上计算，而不是在整个网络水平上计算的。

全局效率度量了网络的全局传输能力。（8）偏心率和直径，半径

偏心率是给定节点与网络中任何其他节点之间的最大路径长度。

参照上图，可以看出节点A与B之间最长路径为4，这被定义为偏心率：

“直径”和“半径”是整个网络水平度量，分别定义为给定网络中所有节点偏心率的最大值和最小值：

在图论研究中，网络的偏心率、直径和半径用来定义网络的规模，在脑网络研究中这三个指标使用较少，少有研究者涉及，这主要和脑网络的规模大小往往是一致的有关。（9）介数中心性

介数中心性是一个度量与某个节点相连的不同节点之间的连接能力的度量指标（也就是说你的朋友们他们互相是否是朋友）。

在数学计算上依赖于将图形解构成路径长度，它是通过给定节点的最短路径条数与网络中所有其他节点之间的最短路径总数之比求得的。

例如，参照上图，可以看到位于中心的节点参与了绿色节点对、红色节点对、黄色节点对和蓝色节点对的最短路径。

因此，位于中心的节点就有高介数中心性。第i个节点的介数中心性可以通过对网络中所有节点对的最短路径求和来计算：

这里，Di(j,k)表示通过节点j和节点k之间通过节点i的最短路径数目，D （j,k）表示节点j和节点k之间所有最短路径数目。

为了比较不同大小的网络，可以将介数中心性进行标准化。对于第i个节点的介数中心性，由于第i个节点被排除在外，对于无向图，一共还有（N-1）*（N-2）/2个节点对。因此，标准化的介数中心性为：

一个点的介性中心度较高，说明其他点之间的最短路径很多甚至全部都必须经过它中转。假如这个点消失了，那么其他点之间的交流会变得困难，甚至可能断开（因为原来的最短路径断开了）。

因此，介数中心度和前文提到的节点度类似，都是衡量节点的重要度量指标。（10）特征向量中心性

近年来，随着互联网搜索引擎网页排序算法的兴起，一种新的图形度量指标得到了相当大的关注，它是“特征向量中心性”。

这个度量是自身参考的，如果节点连接到其他本身就很重要的节点，那么就赋予节点高度的重要性。

简单来说，特征向量中心性表示的是一个节点的相邻节点的度值高低的指标。也就是说，与你连接的人越重要，你也就越重要。

网络中第i个节点的特征向量中心性可以通过二值或者加权的邻接矩阵进行计算。在加权邻接矩阵的情况下，进一步以高中心性节点间连接强度的形式进行维数划分有助于分类。

第一个节点的特征向量中心性等于其所有邻居的特征向量中心性之和：

这里aij表示节点i和节点j之间的连接状态，λ表示比例常数。这还可以写为特征向量方程：

有多个值使得这个特征向量方程的解存在。然而，我们可能会限制lambda 必须为正值，因为负连接状态不是一个合理的场景。

Perron-Frobenius定理表明方阵的元素如果都是正值，那么存在最大特征值，并且特征向量的每个元素都是正的。因此，与最大特征值相关的特征向量的第i个分量给出了第i个节点的特征向量中心性。

（11）最优群落结构

对网络的模块化进行分析的指标往往依赖于最优群落结构的估计。

先来看模块化的概念，模块化指的是网络中内部连接密集但对外连接稀疏的节点集团（如下图）。

一个网络可以被划分为不同的模块，模块中的节点相互之间比与网络中其他节点之间的连接更加紧密。这些子网络可以通过计算最优群落结构找到。

后者产生的模块中，模块间连接的数量被最小化，模块内连接被最大化。

参照上图，可以看出有5个高度互连的节点簇，彼此之间有稀疏的连接。如上图所示，这种图的最优群落结构是被分成5个模块。

在对网络的模块化程度进行探索时，这种方法是快速有效的，它能够帮你快速地确定脑网络中的最优估计的模块化个数。（12）参与系数

参与系数是根据最优社区结构定义的描述单个节点嵌入其局部模块的深度的度量，它被计算为A在其模块内的连接数与整个网络内的连接数之比。

这个值越大，表明这个节点在模块内的连接更多。

参照上图，相比于右图，左图中红色节点的参与系数较高，因为在它的所有连边中，与自身模块内的连边更多，与模块外的连边只有一条。第i个节点在模块m内的连接与其连接总数的比率R可以写如下：

这里Di是第i个节点的度，然后把所有模块的比率加在一起：

然后，我们对所有模块中节点i的模块内连接与总连接的比率进行标准化，并将结果定义为节点i的参与系数P：

从上式可以看出，参与系数P的取值范围为0 ≤ P <1,其中P=0表示第i 个节点仅连接到其自己模块中的节点的情况，即Dmi=Di。

另一方面，当第i个节点与自身模块的连接强度与其他模块的连接强度一样时，P趋向于1，例如Dmi <

（13）集聚系数

节点倾向于聚集在一起的程度由‘集聚’度量量化。集聚系数被定义为节点水平上的三角形数量。

对于一个包含N个节点的网络，第i个节点Ni最多有N-1条入边，因为它可以连接除它自身以外的所有节点。把网络中N个节点求和，共有N(N-1)条连接。

对于无向网络中的节点，和其他一个节点之间的入边和出边被看做是同一条边，所有一共有N（N-1）/2条无向边。

所以对于一个无向网络，最大连边数是N（N-1）/2。局部聚类系数是实际存在的连边数与最多可能连边数之比：

C是实际存在连边的数量，N是节点数目。集聚系数是网络的局部特征，反映了相邻两个人之间朋友圈子的重合度，即该节点的朋友之间也是朋友的程度。

这个指标往往被用来结合特征路径长度来计算“小世界属性”。

对于规则网络，任意两个点（个体）之间的特征路径长度长（通过多少个体联系在一起），但集聚系数高。

对于随机网络，任意两个点之间的特征路径长度短，但集聚系数低。而小世界网络，点之间特征路径长度小，接近随机网络，而聚合系数依旧相当高，接近规则网络。

在脑网络的研究中，“小世界属性”是一个重要的度量指标，以往研究表明大脑的结构网络和功能网络都具有“小世界属性” （14）转移性

“转移性”是聚类系数的标量描述符，定义在网络水平，而不是在单个节点水平。

转移性是基于triplet和三角形结构，triplet细分为两种:开放的(open triplet)和封闭的(closed triplet).如果三个节点之间有2条边，则称为Open triplet；如果存在3条边，则为Close triplet。

例如，在上图中，Open triplet有C-B-E , A-B-E , E-B-D, Close triplet 有A-B-C , B-C-A , C-A-B 。后一组闭合的triplet是三角形，由此可知：

即闭合triplet的数量=3*三角形的数量。网络中的三角形数目可以通过所有节点对之间的连接状态求和来计算：

这里，aij代表第i个节点和第j个节点的连接状态，如果它们之间有连接，连接状态就为1，如果没有连接，连接状态就为0。

等式右边的1/2是因为在分数各向异性的情况下网络是无向的，因此入边和出边被看做是一条边。转移性为closed triplet 的数量与所有open triplet 、closed triplet数量和之比。

在当前的脑网络研究中，使用这一指标的研究还相对较少。（15）通过弹性网络回归减少过拟合

过度拟合是统计分析中一个常见的问题，当模型描述数据中的噪音而不是有意义的信号时就会发生。

因此，过度拟合的模型无法做出准确的预测，这通常是由于相对于观察(例如，受试者)而言，预测因子(例如，图度量)的数量过多。

为了处理预测模型中的过拟合，人们开发了各种技术。这些技术试图通过最小化模型中冗余预测因子的影响来创建有效的模型。

最近的一种技术被称为弹性网络，它是之前两种技术的组合，即最小绝对收缩和选择算子方法(LASSO)和岭回归(Tibshirani, 1996)方法的结合。

如果一个给定的数据集包含多个高度相关的预测因子(在我们的研究中就是这种情况)，岭回归将同时降低这些预测因子组的影响，但不会将它们一直降到零。

这对我们的研究没有用处，因为我们希望从模型中完全消除冗余的图度量，以便只留下最有价值的。

另一方面，LASSO能够将预测能力很低的因素置为0，但一次只能消除一个冗余预测因子。

这对于我们的目的来说也不是很理想，因为被移除的单个预测因子可能与许多其他预测因子高度相关，而LASSO将在模型中保留这些预测因子。

弹性网络方法能够同时惩罚一组高度相关的预测因子，同时将它们从模型中完全排除。

因此，弹性网络利用了LASSO和岭回归的特性，创建了一个非常适合我们这样的研究的混合模型。在实际的计算中，这种方法可以帮助我们更高效地选择机器学习中用于分类或者预测的特征，是有效的特征降维方法。总结：

本文对当前网络研究中常用的图论指标进行了计算方法和度量意义的汇总和简介，其中一些指标是已经在脑网络研究中长期被使用并具有固定研究方法的，如节点度、介数中心度“小世界属性”、特征路径长度等等。

这些指标虽然常用，但是也需要研究者清晰地了解其计算过程才能准确运用。

除此以外，本文还介绍了一些在脑网络研究中较少被使用的指标，如特征向量中心性、转移性等指标，这些指标有着被进一步应用在脑网络研究中的潜力，可以更多的发掘脑网络中的拓扑信息。

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

离散数学的基础知识点总结 第一章命题逻辑 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组成的集合；

数学建模入门基本知识

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

复杂网络基础2(M.Chang)

复杂网络基础理论 第二章网络拓扑结构与静态特征

第二章网络拓扑结构与静态特征 l2.1 引言 l2.2 网络的基本静态几何特征 l2.3 无向网络的静态特征 l2.4 有向网络的静态特征 l2.5 加权网络的静态特征 l2.6 网络的其他静态特征 l2.7 复杂网络分析软件 2

2.1 引言 与图论的研究有所不同，复杂网络的研究更侧重 于从各种实际网络的现象之上抽象出一般的网络几何 量，并用这些一般性质指导更多实际网络的研究，进 而通过讨论实际网络上的具体现象发展网络模型的一 般方法，最后讨论网络本身的形成机制。 统计物理学在模型研究、演化机制与结构稳定性 方面的丰富的研究经验是统计物理学在复杂网络研究 领域得到广泛应用的原因；而图论与社会网络分析提 供的网络静态几何量及其分析方法是复杂网络研究的 基础。 3

2.1 引言 静态特征指给定网络的微观量的统计分布或宏观 统计平均值。 在本章中我们将对网络的各种静态特征做一小结 。由于有向网络与加权网络有其特有的特征量，我们 将分开讨论无向、有向与加权网络。 4 返回目录

2.2 网络的基本静态几何特征 ￠2.2.1 平均距离 ￠2.2.2 集聚系数 ￠2.2.3 度分布 ￠2.2.4 实际网络的统计特征 5

2.2.1 平均距离 1.网络的直径与平均距离 网络中的两节点v i和v j之间经历边数最少的一条简 单路径（经历的边各不相同），称为测地线。 测地线的边数d ij称为两节点v i和v j之间的距离（或 叫测地线距离）。 1／d ij称为节点v i和v j之间的效率，记为εij。通常 效率用来度量节点间的信息传递速度。当v i和v j之间没 有路径连通时，d ij＝∞，而εij＝0，所以效率更适合度 量非全通网络。 网络的直径D定义为所有距离d ij中的最大值 6

图论基础知识

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

信息技术-信息技术网络分析与网络计划 62页 精品

第六章网络分析与网络计划 网络分析是图论的一个应用分支．它主要是应用图论的理论与方法来解决具有网络性质的管理决策问题．在现实生活和生产实践中，网络分析方法有很广泛的应用．如在企业管理中，如何制订管理计划或设备购置计划，使收益最大或费用最小；在组织生产中，如何使各工序衔接好，使生产任务完成得既快又好；在交通网络中，如何使调运的物资数量多且费用最小等．由于网络分析具有图形直观，方法简便，容易掌握的特点，因此得到迅速的发展，且广泛地应用在各个领域，成为经济活动中许多管理决策的优化问题的重要手段． 网络计划方法是上世纪50年代发展起来的计划控制技术，主要包括计划评审技术(programme evaluation and review technique，简称PERT)和关键路径方法(critical path method或critical path analysis，简称CPM、CPA)．网络计划方法特别适用于现代管理中的多因素多环节的复杂计划的优化控制，成为管理运筹学的重要应用分支． 本章在引入有关图的一些基本概念的基础上，介绍最小生成树、网络最短路、最大流、最小费用最大流等网络分析模型及其解法；并对网络计划图（统筹图）的制作、作业时间参数计算、关键线路方法和计划评审技术等网络计划基本技术和方法进行初步介绍． 第一节图的基本概念 一、图 现实世界中有许多具体事物及关系可以用图形来抽象表示．例如，路线关系、工序安排、区位规划等都可以用图来表达． 我们先通过几个直观的例子，来认识什么是图． 例6-1 歌尼斯堡七桥问题 哥尼斯堡(Konigsbergs)城域有一个普雷格尔河系，由新河、旧河及其交汇 而成的大河组成，它把该城分成了一岛三岸共四块陆地，陆地之间有七座桥连通，如图6-1(a)所示．当时城内居民在散步时热衷于这样一个问题：从某陆

离散数学第七章图的基本概念知识点总结docx

图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图 多重集合: 元素可以重复出现的集合 无序积: A&B={(x,y) | x∈A∧y∈B} 定义无向图G=, 其中 (1) 顶点集V≠?，元素称为顶点 (2) 边集E为V&V的多重子集，其元素称为无向边，简称边. 例如, G=如图所示, 其中V={v1, v2, …,v5}, E={(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} , 定义有向图D=, 其中 (1) V同无向图的顶点集, 元素也称为顶点 (2) 边集E为V?V的多重子集，其元素称为有向边，简称边. 用无向边代替D的所有有向边所得到的无向图称作D的基图，右图是有向图，试写出它的V和E 注意：图的数学定义与图形表示,在同构(待叙)的意义下是一一对应的

通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用e k表示无向边或有向边. V(G), E(G), V(D), E(D): G和D的顶点集, 边集. n 阶图: n个顶点的图 有限图: V, E都是有穷集合的图 零图: E=? 平凡图: 1 阶零图 空图: V=? 顶点和边的关联与相邻：定义设e k=(v i,v j)是无向图G=的一条边, 称v i,v j 为e k的端点, e k与v i (v j)关联. 若v i ≠v j, 则称e k与v i (v j)的关联次数为1;若v i = v j, 则称e k为环, 此时称e k与v i 的关联次数为2; 若v i不是e k端点, 则称e k与v i 的关联次数为0. 无边关联的顶点称作孤立点. 定义设无向图G=, v i,v j∈V, e k,e l∈E,若(v i,v j) ∈E, 则称v i,v j相邻; 若e k,e l 至少有一个公共端点, 则称e k,e l相邻. 对有向图有类似定义. 设e k=?v i,v j?是有向图的一条边,又称v i是e k的始点, v j是e k的终点, v i邻接到v j, v j邻接于v i.

离散数学基本知识

离散数学基本知识 01 什么是“数据结构”？ 这里我就不说那些“官方的定义”，简单谈谈自己的理解吧。 数据结构是一种抽象的封装。 好像还是有点绕脑，不过没关系，我们继续往下看。 说简单点就是，把一堆基本的数据，按照某种顺序给揉成一坨。 相信大家都吃过饭吧？ 做一道菜需要放各种调料，如盐、味精，还有肉等，把它们混在一起就做成了一道菜。 口水鸡是我最喜欢的一道菜，这里我们就以口水鸡为例，来讲一讲什么是数据结构。下图是百度百科中口水鸡的做法。

好，下面我就用程序来表示一下，我写的是伪码，大家能懂就好哈。先来抽象一下“口水鸡”：

对，上述这个结构体就是一个自定义的数据结构，将很多种不同的东西融合在一起；而计算机中的数据结构，则是把一些基本的数据类型，如int、double等融合成一些复杂的数据结构，如map、队列。 抽象完口水鸡再来抽象“你”吧： 然后再来抽象一下“厨师”：

这里的抽象有点随意，不过大家理解就好，我们把一堆很基本的元素抽象成了3个数据结构，这三个元素就是所谓的数据结构。 而平时我们说的链表无非就是把一些基本元素和指针做了融合，树、图也是把指针和一些基本元素融合后再外加一些流程，如函数。 比如python的dict，dict的key，value就是两种相同或者不同的数据类型；dict还提供了一些函数，譬如get()，set()。dict就是一个典型的被封装的数据结构。 所以我说数据结构是一种抽象的封装，当然，数据结构并没有我们举的例子那样简单，但是原理是一样的。 我们平时写程序都是直接去调用这些数据结构，而没有去想它们的内部实现是怎样的。数据结构这门课就是要告诉我们常见的数据结构是如何实现的，比如Vector，map的实现。我们常常听到的譬如平衡二叉树，红黑树，大顶堆等词汇就是出自数据结构这门课。具体了解数据结构后，我们就可以知道队列的内部实现是什么样，词典的内部实现又是什么样。

图论基础知识汇总(适合建模)

图与网络模型及方法 §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22 n n H C 的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决 这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 图与网络是运筹学（Operations Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP －shortest path problem ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两

图论网络规划

图论练习 汪帆2011306200513 土规1202 1某城市要建立一个消防站，为该市所属的七个区服务，如图所示，问应设在那个区，才能使它至最远区的路径最短。 图5.1.1 城市点线模型图 解：分析：要求建立的消防站离最远区的路径最短，即要求出任意两点间最优路径，而后从最优路径中选取最大值中的最小值。具体方法则要运用 Warshall-Foryd算法求出该图的路由表，从而根据路由表中的最优路线，寻求V1-V7到每一点的最优路径，并比较各路径中最长路径的大小，择取最小值即为题中之所问。 （1），建立权矩阵： A=[0 3 inf inf inf inf inf ; 3 0 2 inf 1.8 2.5 inf; Inf 2 0 6 2 inf inf ; Inf inf 6 0 3 inf inf ; Inf 1.8 2 3 0 4 inf; Inf 2.5 inf inf 4 0 1.5; Inf inf inf inf inf 1.5 0] （2），运用Warshall-Foryd算法，调用floyd(A)函数，求出该图的路由表（程序详见附录5.1）：

（3），结果分析：上述n n ij )V (V ?=矩阵为对称阵，主对角线为0，即消防站所建立的位置。其具体涵义为：消防站建立在V i 处时对应各个城市的最短路径，如此可以建立表5.1.2: 表5.1.2 各点建立消防站的最远城市及其两者距离表 消防站点 最远城市 两者距离 V1 V4 7.8 V2 V2 4.8 V3 V7 6 V4 V7 8.5 V5 V7 5.5 V6 V5 7 V7 V4 8.5 从表5.12可以看出，比较最远距离，不难看出，当消防站点选在V2城市时，其离最远城市的最优距离为最优：4.8。故而，应将消防站建立在V2城市。 2某矿区有七个矿点，如图所示，已知各矿点每天的产矿量,现要从这七个矿点选一个来建造矿厂，问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨公里）最小。 图5.2.1 矿区点线模型图 解：分析：总运力与两个因素有关：矿点与矿厂的距离、矿点产矿量，且都是正比的关系，故而应当把矿点与矿厂的距离L 和矿点产矿量X 的成绩当做运力，进而将运力当做权矩阵的元，运用Warshall-Foryd 算法求出该图的路由表，从而根据路由表中的最优路线，寻求V1-V7到每一点的最优路径，再将最优路径加总，进而寻求7个预设厂址中的最优路径总值的最小值的点即为所求矿厂点。 （1），距离矩阵：

§2-1网络图论的基本概念

§2-1 网络图论的基本概念 对于一个电路图，如果用点表示其节点，用线段表示其支路，得到一个由点和线段组成的图，这个图被称为对应电路图的拓扑图，通常用符号G 表示。例如：图2-1-1（a ）所示电路，其对应的拓扑图如图2-1-1 (b) 所示。 拓扑图是线段和点组成的集合，它反映了对应的电路图中的支路数、节点数以及各支路与节点之间相互连接的信息。 在拓扑图中，如果任意两点之间至少有一条连通的途径，那么这样的图称为连通图，例如图2-1-1（b ）所示的图，否则称为非连通图，例如图2-1-2（b ）所示的图。如果图G 1中所有的线段与点均是图G 中的全部或部分线段与点，且线段与点的连接关系与图G 中的一致，那么图G 1称为图G 的子图。例如图2-1-3（b ）（c ）（d ）（e ）均是图2-1-3（a ）的子图。 图 2-1-1 图2-1-2 图2-1-3

下面介绍网络图论中非常重要的一个概念——树。树是连通图G 的一个特殊子图，必须同时满足以下三个条件： （1）子图本身是连通的； （2）包括连通图G 所有节点； （3）不包含任意回路。 组成树的支路称为树支，不包含在树上的支路称为连支（或链支）。如果用t n 表示树支的数目，则： 1t n n =- （式2-1-1） 连支的数目l 等于支路数b 减去树支的数目，即 1l b n =-+ （式2-1-2） 如果将一个电路铺在一个平面上，除节点之外再没有其他交点，这样的电路被称为平面电路，否则，称为非平面电路。 在平面电路中，内部没有任何支路的回路称为网孔。它是一种特殊的回路。 一个有b 条支路、n 个节点的连通平面图的网孔数m 为： 1m b n =-+ （式2-1-3） 接下来介绍割集的概念。割集是连通图G 的一个子图，它满足以下两个条件： （1）移去该子图的全部支路，连通图G 将被分为两个独立部分； （2）当少移去该子图中任一条支路时，则图仍然保持连通。 一个具有n 个节点的连通图，有（n-1）条树，有（n-1）个单树支割集。 (a) (b) 图2-1-7

图的基本知识

完成题库中的P1135、P1138、P1465、P1466、P1471、P1545~ 图的基本知识 一、什么是图 什么是计算机中所说的图?请先看下面的“柯尼斯堡桥问题”。传说在东普鲁士境内，有一座柯尼斯堡城，希雷格尔河流经这个城市的克奈霍福岛后，就将这个城市一分为二，形成如图1—1（左）的A、B、C、D 4个地区。人们建造了7座桥将这4个地区连起来。在游览中有人提出，是否可以从A地出发，各座桥恰好通过一次，最后又回到原来出发地呢? 这个问题在18世纪被数学家欧拉解决了。他把这个问题转化为图1—1右边所示的图。图上用A、B、C、D4个顶点分别表示4个地区，用两点间的线段表示连接各地的桥。这样原来的问题就转化为：从A顶点出发经过其中每一条线段一次，而且仅一次，再回到A点的“一笔画”问题。 欧拉对柯尼斯堡问题作出了否定的结论。因为对于每一个顶点，不论如何经过，必须有一条进路和一条出路，所以对每一个顶点(除起点和终点)来说与它有关的线段(称为边)必须是偶数条。而图1-1(右)的顶点有关的线段都是奇数条，因此不可能一笔画出。而如图1—2中的图形是可以一笔画出的。 欧拉通过对柯尼斯堡桥问题的研究，于1736年发表了著名的关于图论的论文，从而创立了图论的学说。图1—2一类的问题就是图论中所指的图。 又如，有6个足球队之间进行循环赛，他们比赛的场次可以用图1-3(1)来表示。有3个人相互写信，可以用图1—3(2)来表示。

从上面两个例子可看出，我们这里所说的图(graph)，与人们通常所熟悉的图，如圆、四边形、函数图象等是很不相同的。是指某些具体事物和这些事物之间的联系。如果我们用点来表示事物(如地点、队)，用线段来表示两事物之间的联系，那么一个图就是表示事物的点集和表示事物之间联系的线段集合所构成。其中线段仅表示两点的关系，它的长短与曲直是无关紧要的。例如图1-4中3 个图，被认为是同一个图。 图(Graph)是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构有着广泛的应用。奥林匹克信息学竞赛的许多试题，亦需要用图来描述数据元素间的联系。 二、图的基本概念 定义：图G定义为一个偶对(V，E)，记作G：(V，E)。其中 1)V是一个非空有限集合，它的元素称为顶点； 2)E也是一个集合，它是如下集合(它的元素称为边)的子集： E∩{(a,b|a ∈ V，b ∈ V} 例如图4-1中的图有4个顶点，4条边。 或者定义：图G（Graph）是由顶点的集合V和边的集合E所组成的二元组，记作： G =（V，E） 其中V是顶点的集合，E是边的集合。 （一）有向图和无向图 1．有向图 若图G中的每条边都是有方向的，则称G为有向图(Digraph)。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称 为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。例如表示

图论基础知识点

基本知识点： 一、图的基本定义： 平凡图：只有一个顶点无边的图。 非平凡图：其他所有图。 空图：边集合为空的图。 简单图：既没有环也没有重边的图。 复合图：其他所有的图。 同构图：顶点集合之间存在双射（一一对应关系），对应边重数和端点对应相等。 标定图：给图的点和边标上符号。非标定图：不标号。非标定图代表一类相互 同构的图。 完全图：每两个不同顶点之间都有一条边相连的简单图。N 个顶点的完全图只有一个，记为n K 。 偶图（二部图）：具有二分类(,)X Y 的图，他的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。 完全偶图 ：指具有二分类(,)X Y 的简单偶图，其中X 的每个顶点与Y 的每个顶点相连。若,X m Y n ==，则这样额完全偶图记为：,m n K 。 k —正则图：设(,)G V E =为简单图，如果对所有的结点v V ∈，有()d v k =，称G 为k —正则图。 完全图和完全偶图,n n K 均是正则图。 图划分：若一个n 阶简单图G 各点的度为i d ，则分正整数k 为n 个部分的划分i d ∑称为是图划分。 子图：边集合和点集合均是原图的子集，且待判定图中的边的重数不超过原图中对应的边的重数。 生成子图：点集合相等，边集合为原图子集的图。 导出子图：由顶点集为原图G 真子集的所有点，及两端点均在该集合中的边的全体组成的 子图V ‘。 '[]G V 和G v -。 边导出子图：由原图G 边的真子集，该图中边的断点全体为顶点组成的子图E ‘。 ' []G E 和{}G e -。 图的运算： 并，交，差，对称差，联图，积图，合成图，极图 路与图的联通性： 途径： 迹：边互不相同的途径。 路：边和点都互不相同的途径。 连通的：两个顶点之间存在路。 连通图：每一对顶点之间都有一条路。

脑网络研究中的图论指标详解_69

人脑是自然界中最复杂的系统之一, 在复杂系统研究方面，网络研究的方法在21世纪以来被深度应用在多个领域； 在神经科学研究领域中，无论从微观的多个神经元、神经元集群的角度看还是从宏观的多个脑区相互连接成庞杂的结构网络和通过相互作用构建的功能网络看，网络方法都已经延伸到了神经科学研究中的方方面面。 在网络研究中，通过图论方法来表征复杂网络的拓扑关系是研究网络中不同节点、不同连边以及网络的整体特性的重要手段。 但在实际的研究中，研究者往往根据自己的研究目的特定地选择网络属性，因而导致很多研究人员无法全面的了解图论研究中多种指标的实际含义； 同时，随着图论方法的发展，许多新的指标也不断出现。全面和准确的理解图论指标对于使用图论方法研究复杂网络具有重要的意义，只有选对指标才能更好地说明你的研究问题，达到事半功倍的效果。 因此，思影科技汇总了当前网络研究中被研究者经常使用的图论指标，并结合图表示、数学公式的严格定义以及解析的方法对每个指标进行了详述，以更好的帮助各位希望使用网络方法和图论指标进行脑科学研究的研究者。 首先我们来简单的回顾下网络中的不同对象，以便在后文阅读中能够清楚不同术语所描述的网络对象。 下图是一个由11个节点组成的网络，即圆圈，它们表示了网络中的基本对象，连接不同的节点的连线被称为“边”； 在脑网络研究中，节点是被按照不同分割依据所分割的脑区，连边在功能网络中往往通过对不同脑区的时间序列信号的相关计算所得，而结构网络中分为DTI连接和基于灰质变化的协变网络连边。 在这个小的网络中，我们可以看到不同节点由数量不等的连边互相连接起来，为了能够全面的分析这个网络的拓扑结构，我们需要使用不同的图论指标。 接下来我们来一起了解不同的网络指标。 （1）度（node degree） 在网络研究中，最基本和最广泛使用的度量指标是“度”，对于给定节点，度就是与它连接的邻居个数。第i个节点的度计算公式是： 这里，Cij表示节点i和节点j之间的连接状态，当节点i和节点j之间有连接时，Cij=1,当节点i和节点j之间无连接时，Cij=0；

图论习题答案1

图论习题课作业1，3，6，8，10 By jgy

?作业1：第一章：1,2,4,12,20,29,35 ?作业3：第二章：14,28,30第三章：1,5,7,8?作业6：第五章：18,33 ?作业8：第六章：6,12,17 ?作业10：第七章10 第八章5,6,8

作业1 |E(G)|,2|E(G)|2G υυ?? ≤ ??? ?? ??? 1.1 举出两个可以化成图论模型的实际问题略 1.2 证明其中是单图 证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极 端情况为。

?1.20证明每顶皆二次的连通图是圈 ?证明：（思路）易证每顶皆二次的连通图中有圈。设图中最大圈为H，假设除H外还有其他顶点集U，任取u k，因为连通，u k 与H中任意顶均有一条道路，存在H中一顶h j与u k相邻，则h j为三次。 ?1.29 证明二分图的子图是二分图 ?方法一： ?定理1.2 图G是二分图当且仅当G中无奇圈 ?反证：设二分图为G，子图为S，假设S非二分图，由定理1.2知S中有 奇圈，则G中有奇圈，这与G是二分图矛盾。 ?方法二： ?（思路）定义：V(G) = X U Y, X n Y=空, 且X中任二顶不相邻，且Y中任二 顶不相邻。

?证明： ?(a)第一个序列考虑度数7,第二个序列考虑6,6,2 ?(b)将顶点v分成两部分v’和v’’ ?v’ = {v|v= vi , 1≤ i≤ k}, ?v’’ = {v|v= vi , k< I ≤ n} ?以v’点为顶的原图的导出子图度数之和小于 ?然后考虑剩下的点贡献给这k个点的度数之和最大可能为

图论知识及运用举例

图论知识及运用举例 1 概论 图论中的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。 图是运筹学（Operations Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论最短路问题、最大流问题、最小费用流问题和匹配问题等。 2 图的基本概念 2.1 无向图 一个无向图(undirected graph)G 是由一个非空有限集合)(G V 和)(G V 中某些元素的无序对集合)(G E 构成的二元组，记为))(),((G E G V G =。其中 },,,{)(21n v v v G V =称为图G 的顶点集（vertex set ）或节点集（node set ） ， )(G V 中的每一个元素),,2,1(n i v i =称为该图的一个顶点（vertex ）或节点（node ）； },,,{)(21m e e e G E =称为图G 的边集（edge set ） ，)(G E 中的每一个元素k e (即)(G V 中某两个元素j i v v ,的无序对) 记为),(j i k v v e =或i j j i k v v v v e == ),,2,1(m k =，被称为该图的一条从i v 到j v 的边（edge ）。 当边j i k v v e =时，称j i v v ,为边k e 的端点，并称j v 与i v 相邻（adjacent ）；边k e 称为与顶点j i v v ,关联（incident ）。如果某两条边至少有一个公共端点，则称这两条边在图G 中相邻。 边上赋权的无向图称为赋权无向图或无向网络（undirected network ）。我们对图和网络不作严格区分，因为任何图总是可以赋权的。 一个图称为有限图，如果它的顶点集和边集都有限。图G 的顶点数用符号||V 或)(G ν表示，边数用||E 或)(G ε表示。 当讨论的图只有一个时，总是用G 来表示这个图。从而在图论符号中我们常略去字母G ，例如，分别用ν,,E V 和ε代替)(),(),(G G E G V ν和)(G ε。 端点重合为一点的边称为环(loop)。