介绍几个图论和复杂网络的程序库

介绍几个图论和复杂网络的程序库

刚加入复杂网络圈子，暂时还没有成熟的研究内容，先发个资料性的东西占坑：）

作复杂网络研究离不开对各种实际或模拟网络的统计、计算、绘图等工作。对于一般性的工作，我们可以用Pajek、Netdraw和Ucinet等软件完成。但对一些特殊应用（比如自己开发了一个新模型），现有的软件不能提供相应的建模或计算功能，这时就必须要通过编程的办法来解决问题了。

在这篇文章中，向大家介绍我使用过的4个面向图论及复杂网络分析的程序库，它们可以（分别或同时）用C、C++、C#和Python等语言调用。同时这些库都是开源的，可以通过研读它们的源代码提高编程水平。

好，下边开始介绍，第一位出场的是：

一、Boost Graph Library ——“准”C++标准库

Boost Graph Library（BGL）是C++ Boost库的成员之一。Boost是一个经过千锤百炼的C++库，作为标准模板库STL的后备，是C++标准化进程的发动机之一。Boost库由C++标准委员会库工作组成员发起，在C++社区中影响甚大，是不折不扣的“准”标准库。

BGL的特点是灵活性和高运行效率。BGL是以模板的形式提供的，这意味着你可以在模板的基础上创建自己的类型，比如自定义的节点类。BGL的开发者是世界上最顶尖的C++专家，这个库中实现的各种图算法具有非常高的执行效率，而且BGL本身具有工业强度，你可以放心的使用它。此外，BGL的代码结构良好，是非常值得研读的精品，对于学习算法与数据结构会有很大的帮助。

从我的角度来看，BGL的缺点是没有提供复杂网络分析的算法，所以在实际中我使用的还不多。建议对于分析大规模的网络问题时使用这个库，利用它良好的图数据结构，开发自己的复杂网络分析算法，将会获得很高的执行效率。

参考资源：

BGL官方网站：https://www.sodocs.net/doc/178876723.html,/doc/libs/1_42_0/libs/graph/

技术书籍《The Boost Graph Library》，作者: Jeremy G. Siek，Lie-Quan Lee，Andrew Lumsdaine，见：https://www.sodocs.net/doc/178876723.html,/subject/1463103/

《使用Boost Graph library》，一个简短的BGL使用介绍，适合快速上手，见：https://www.sodocs.net/doc/178876723.html,/2009/0408/100.html

《Boost Graph Library 学习笔记》，讨论学习BGL中遇到的问题，见：https://www.sodocs.net/doc/178876723.html,/magicblue/archive/2009/05/22/4208976.aspx

二、QuickGraph —— .NET平台下的BGL

QuickGraph是一个用C#语言编写的.NET组件库，所提供的算法与BGL类似，可以看作是Boost Graph Library在.NET平台下的实现。目前QuickGraph的最高版本是3.3，支

持.NET 2.0和.NET 3.5平台。

对于复杂网络研究，QuickGraph能够提供的帮助与BGL基本类似。如果你对C#语言（以及其它支持.NET的语言）比较熟悉，可以考虑选择这个库。但由于.NET程序是在虚拟机下运行的原因，所以效率不够高，不适合处理大规模的计算问题。

参考资源：

QuickGraph官方网站：https://www.sodocs.net/doc/178876723.html,/quickgraph

中文资料暂时还找不到。

三、igraph —— C语言写的复杂网络分析库

igraph是一个建立和操纵无向图、有向图的开源C程序库，它既包含经典图论里的各种算法（例如最小支撑树、网络流等），也包含了最近的出现的一些网络分析算法（如社团结构搜索等）。

igraph是C写的，这意味着你很容易在C/C++中使用它。如果你不熟悉这两种语言，或者觉得用C/C++太繁琐的话，igraph还提供了R语言（一种国外很流行的统计分析语言）和Python语言的接口，所以也很适合科研人员使用（我现在用的是Python，调用igraph很简单）。

参考资料：

igraph官方网站：https://www.sodocs.net/doc/178876723.html,/

关于Python语言的介绍，见：https://www.sodocs.net/doc/178876723.html,/wiki/Python

关于R语言的介绍，见：https://www.sodocs.net/doc/178876723.html,/wiki/R语言

四、NetworkX ——全面支持复杂网络分析的Python包

NetworkX是一个创建和操纵复杂网络，并对复杂网络的结构、功能和动力学进行研究的Python包，它提供了目前应用最广泛的一些复杂网络分析算法，当然也包括基本的经典图论算法。NetworkX目前只能在Python语言中使用（这也是我学Python的原因之一，见《从C#到Python ——谈谈我学习Python一周来的体会》）。

我个人认为NetworkX比igraph要好用，因为NetworkX的文档更清晰易读，程序结构组织得也很好，我现在主要在用这个包。但NetworkX的执行效率多数情况下会比igraph要低（见Drew Conway所作的对比：https://www.sodocs.net/doc/178876723.html,/1406240/sna_in_R.pdf）。所以也不适合作太大规模的网络分析计算。此外，NetworkX和Python的一个绘图包——Matplotlib 结合得很好，可很方便地进行复杂网络可视化。

参考资源：

NetworkX官方网站：https://www.sodocs.net/doc/178876723.html,/

Matplotlib（科学绘图的Python包）：https://www.sodocs.net/doc/178876723.html,

五、总结

本文介绍了图论与复杂网络研究常用的一些程序库。用好这些程序库（以及其它一些软件工

具），可以避免我们无谓的re-invent the wheel，从而提高工作效率。在网上了解到，国外同行用这些库的很多，而在国内还很少搜索到这方面的资料（除了BGL）。作为我进复杂网络圈的敲门砖，向各位圈友推荐这几个库。另外，我近期正在学习Python和NetworkX，如果您感兴趣，欢迎和我交流：）

附：几个库的开发及调用语言对比（*看来学Python还是不错的，这几个库都可以调用-_-）库名称原始开发语言可用某语言调用

BGL C++ C++/ Python（通过boost-python）

QuickGrap C#

支持.NET平台的任何语言(Python程序员可用IronPython)

igrap C C/C++/R/Python（理论上至少有50种语言可直接或间接调用C程序）

Network Python Python

图论及其应用

图和子图 图 图 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 ??)

图论及其应用(精)

图论及其应用 学时：40 学分：2 课程属性：专业选修课开课单位：理学院 先修课程：高等代数后续课程：无 一、课程的性质 《图论及其应用》是数学与应用数学专业的专业选修课程。 二、教学目的 通过教学，使学生掌握图论及其算法的基本理论和基本技巧，初步掌握图论及其算法的基本应用手段、基本算法设计及编程，并能用所学理论解决一些应用问题。 三、教学内容 1.图的基本概念 2.图的连通性 3.树的基本性质及其应用 4.Euler Graphs and Hamilton Graphs with Applications 5.平面图性质 6.匹配，求最大匹配算法及应用 7.图的染色及应用 8.极图理论 四、学时分配 章课程内容学时 1 图的基本概念 4 2 图的连通性 6 3 树的基本性质及其应用 6 4 Euler Graphs and Hamilton Graphs with Applications 4 5 平面图性质 6 6 匹配，求最大匹配算法及应用 6

7 图的染色及应用 4 8 极图理论 4 合计40 五、教学方式 本课程采用多媒体课堂讲授，结合实际范例深入浅出讲解讨论。 六、考核方式 本课程考核采用平时与期末考核相结合的办法，特别注重平时的考核，作业采用简单练习、论文等形式，期末考试采用简单考题或论文形式。 七、教材及教学参考书 参考教材： [1] J.A.Bondy and U.S.R.Murty. Graph Theory with Applications, The Macmillan Press LTD,1976. [2] 蒋长浩．图论与网络流．北京：中国林业出版社，2000． 参考书目： [1] Bela Bollobas．Modern Graph Theory（现代图论，影印版）．北京：科学出版社，2001． [2] 殷剑宏、吴开亚．图论及其算法．合肥：中国科学技术大学出版社，2003． [3] 谢金星、邢文训．网络优化．北京：清华大学出版社．2000． [4] 程理民、吴江、张玉林．运筹学模型与方法教程．北京：清华大学出版社，2000． [5] 三味工作室．SPSS V10.0 for Windows 实用基础教程．北京：北京希望电子出版社2001． [６] 孙魁明、张海彤．Mathematica工具软件大全．北京：中国铁道出版社，1994． [７] 楼顺天、于卫、闫华梁．MATLAB程序设计语言．西安：西安电子科技大学出版社，1997．八、教学基本内容及要求 第一章图的基本概念 1．教学基本要求 掌握的图的基本概念、特殊图概念，了解最短路问题。 2．教学具体内容 图的基本概念，路和圈，最短路问题。

复杂网络基础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

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

习题三： ● 证明：是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意及, G 中的路必含. 证明：充分性: 是的割边，故至少含有两个连通分支，设是其中一个连通分支的顶点集，是其余分支的顶点集，对12,u V v V ?∈?∈，因为中的不连通，而在中与连通，所以在每一条路上，中的必含。 必要性：取12,u V v V ∈∈，由假设中所有路均含有边，从而在中不存在从与到的路，这表明不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 ： 是块，任取的一点，一边，在边插入一点，使得成为两条边，由此得到新图，显然的是阶数大于3的块，由定理，中的u,v 位于同一个圈上，于是 中u 与边都位于同一个 圈上。 ： 无环，且任意一点和任意一条边都位于同一个圈上，任取的点u ，边e ，若在上，则三个不同点位于同一个闭路，即位于同一条路，如不在上，由定理，的两点在同一个闭路上，在边插入一个点v ，由此得到新图，显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。 ： 连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，12,x v y v ∈∈，点在每一条的路上，则与已知矛盾，是块。 ● 7.证明：若v 是简单图G 的一个割点，则v 不是补图的割点。 证明：是单图的割点，则有两个连通分支。现任取, 如果不在的

同一分支中，令是与 处于不同分支的点，那么，与在的补图中连通。若在的同一分支中，则它们在的补图中邻接。所以，若是的割点，则不是补图的割点。 ● 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给 出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} ()25G κ= 最小点割{6,7,8,9,10} 2()5G λ= 最小边割{（2,7）…（1,6）} ● 13.设H 是连通图G 的子图，举例说明：有可能k(H)> k(G). 解： 通常. 整个图为，割点左边的图为的的子图， ，则. e H

图论基础知识

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

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

电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：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 由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k 七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X | v v 1 3 图G

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

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

电子科技大学研究生试题图论及其应用参考答案完整版

电子科技大学研究生试题图论及其应用参考答 案 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】

电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k2)棵树构成的森林，则图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 ） 6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四． A C D 1 2 3 A B C D

解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分) 求下图G 的色多项式P k (G). 解：用公式 )(e G P k -G 的色多项式： )3)(3)()(345-++=k k k G P k 。 六．(10分) 一棵树有n 2个顶点的度数为2，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 由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k 七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X |≠|Y |，则G 是非哈密尔顿图。 证明：(1) 若不然，设C=v 1v 2…v m v 1为G 的一个奇圈，不妨设v 1X, v 5 v v v 6 图G

图论及其应用期末论文

在通信领域中，传输信息的方法有两种，其一是等长码制方法，其二是非等长码制方式；字符出现的频率不同,在传输中采用非等长二进制编码传输会提高传输效率,在字符的出现频率已知前提下,采用最优二叉正则树算法,可以得到最佳前缀码。 关键字正则二叉树 前缀码 最优二叉树 哈夫曼编码 频率 java 程序 引言 在通信中,通常采用二进制编码表示符号,如果每个要传输的符号使用频率相同,则采用等长码表示即可,但事实上不同符号在传输过程中出现的频率并不相同,有些符号出现频率相差很大,此时采用非等长编码可节省二进制数位,可达到提高效率的目的。 相关基础知识 下面介绍有关二叉树以及哈夫曼编码的相关知识： 定义1：一个有向图，若不考虑他的方向，他是一棵树，则称这个有向图为有向树。一颗有向树，如果恰有一个结点的入度为0，其余所有结点的入度都为1，则称为根树，其中入度为0的结点称为树根，出度为0的结点称为树叶，出度不为0的结点称为分支点或内点。 在根树中，称从树根到结点v 的距离称为该点的层次。 定义2：在根树中，若从i v 到 j v 可达，则称i v 是j v 的祖先，j v 是i v 的后代，又若),(j i v v 是树根中的有向边，则称i v 是j v 的父亲，j v 是i v 的儿子；如果两个结点是同一结点的儿子，则称这两个结点是兄弟。 定义3：在根树中，任一结点v 及其v 的后代和从v 出发的所有有向路中的边构成的子图称为以v 为根的子路，根树中的结点u 的子树是以u 的儿子为根的子树。 定义4：如果在根树中规定了每一层次上结点的次序，这样的根树称为有序树。在有序树中规定了同一层次结点的次序是从左至右。 定义5：一个有向图，如果他的每个连通分支是有向树，则称该有向图为森林；在森林中，如果所有树都是有序树且给树指定了次序，则称此森林为有序森林。

图论及其应用1-3章习题答案(电子科大) (1)

学号：201321010808 姓名：马涛 习题1 4．证明图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, 1≤j ≤ 10 ) 由图的同构定义知，图1-27的两个图是同构的。 6．设G 是具有m 条边的n 阶简单图。证明：m =???? ??2n 当且仅当G 是完全图。 证明 必要性 若G 为非完全图，则? v ∈V(G),有d(v)< n-1 ? ∑ d(v) < n(n-1) ? 2m

证明 由于G 为k 正则偶图，所以，k | V 1 | =m = k | V 2 | ? ∣V 1∣= ∣V 2 ∣。 12.证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v 1,v 2,…,v n ｝,对于G 中的路v 1v 2…v k ,若v k 与v 1邻接，则构成一个圈。若v i1v i2…v in 是一条路，由于δ≥ 2，因此，对v in ，存在点v ik 与之邻接，则v ik ?v in v ik 构成一个圈 。 17.证明：若G 不连通，则G 连通。 证明 对)(,_G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。 习题2 证明：每棵恰有两个1度顶点的树均是路。 证明：设树T 为任意一个恰有两个1度顶点的树，则T 是连通的，且无圈，令V 1 、V 2 为度为1的顶点，由于其他的顶点度数均为0或者2，且T 中无圈，则从V 1到V 2 有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。 证明：正整数序列),...,,(21n d d d 是一棵树的度序列当且仅当)1(21-=∑=n d n i i 。 证明：设正整数序列),...,,(21n d d d 是一棵树T 的度序列，则满足E d n i i 21 =∑=，E 为T 的边数，又有边数和顶点的关系1+=E n ，所以)1(21 -=?∑=n d n i i 证明：若e 是n K 的边，则3)2()(--=-n n n n e K τ。 若e 为Kn 的一条边，由Kn 中的边的对称性以及每棵生成树的边数为n-1，Kn 的所有生成树的总边数为：2)1(--n n n ，所以，每条边所对应的生成树的棵数 为： 32 2)1(2 1 )1(--=--n n n n n n n ，所以，K n - e 对应的生成树的棵数为： 332)2(2)(----=-=-n n n n n n n n e K τ Kruskal 算法能否用来求：

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

图与网络模型及方法 §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），距离矩阵：

(完整版)图论及其应用1-3章习题答案(电子科大)

习题一 1. （题14）：证明图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, 1≤j ≤ 10 ) 由图的同构定义知，图1-27的两个图是同构的。 2. （题6）设G 是具有m 条边的n 阶简单图。证明：m =???? ??2n 当且仅当G 是 完全图。 证明 必要性 若G 为非完全图，则? v ∈V(G),有d(v)< n-1 ? ∑ d(v) < n(n-1) ? 2m

证明 由于G 为k 正则偶图，所以，k | V 1 | =m = k | V 2 | ? ∣V 1∣= ∣V 2 ∣。 4. （题12）证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v 1,v 2,…,v n ｝,对于G 中的路v 1v 2…v k ,若v k 与v 1邻接，则构成一个圈。若v i1v i2…v in 是一条路，由于δ≥ 2，因此，对v in ，存在点v ik 与之邻接，则v ik ?v in v ik 构成一个圈 。 5. （题17）证明：若G 不连通，则G 连通。 证明 对)(,_ G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。 习题二 2、证明：每棵恰有两个1度顶点的树均是路。 证明：设树T 为任意一个恰有两个1度顶点的树，则T 是连通的，且无圈，令V 1 、V 2 为度为1的顶点，由于其他的顶点度数均为0或者2，且T 中无圈，则从V 1到V 2 有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。 5、证明：正整数序列),...,,(21n d d d 是一棵树的度序列当且仅当 )1(21 -=∑=n d n i i 。 证明：设正整数序列),...,,(21n d d d 是一棵树T 的度序列，则满足 E d n i i 21 =∑=，E 为T 的边数，又有边数和顶点的关系1+=E n ，所以)1(21 -=? ∑=n d n i i 14、证明：若e 是n K 的边，则3 )2()(--=-n n n n e K τ。 若e 为Kn 的一条边，由Kn 中的边的对称性以及每棵生成树的边数为n-1，Kn 的所有生成树的总边数为：2 )1(--n n n ，所以，每条边所对应的生成树的棵数为： 32 2)1(2 1 )1(--=--n n n n n n n ，所以，K n - e 对应的生成树的棵数为： 332)2(2)(----=-=-n n n n n n n n e K τ 16、Kruskal 算法能否用来求： （1）赋权连通图中的最大权值的树？ （2）赋权图中的最小权的最大森林？如果可以，怎样实现？

§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

图论及其应用1-3章习题答案

习题一 证明将图1-28的两图顶点标号为如下的(a)与(b)图 n(n-1)/2= 2，与已知矛盾! 充分性若G为完全图，则2m= d(v) =n(n-1) 3. (题9)证明：若k正则偶图具有二分类V= V1U V2,则| V1I = | 10) U i (1 i E((a)),有f(v i V j) UU j E((b)) (1 i 10, 1 j 1-27的两个图是同构的。 2.(题6)设G是具有m条边的n阶简单图。证明: ；当且仅当G是 完全图。 证明必要性若G为非完全图，则v V(G),有d(v) n(n-1) 2m n(n-1) n-1 d(v) m= 1.(题14):证明图1-28中的两图是同构的 图1-28 i) V i V 作映射f: f(v 容易 证明，对 10 ) 由图的同构定义知，图 2

证明 由于G 为k 正则偶图，所以，k V i =m= k V 2 V 1 = V 2 。 4. (题12)证明：若3》2,则G 包含圈。 证明 只就连通图证明即可。设 V(G)= {V l ,V 2,…,v n },对于G 中的路V l V 2… V k ,若V k 与V i 邻接，则构成一个圈。若V ii V i2…V in 是一条路，由于 2，因此， 对V in ，存在点V ik 与之邻接，则V ik V in V ik 构成一个圈。 5. (题17)证明：若G 不连通，则G 连通。 证明 对u,V V(G),若u 与V 属于G 的不同连通分支，显然u 与V 在G 中 连通；若u 与V 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶 点，则u 与w, V 与w 分别在G 中连通，因此，u 与V 在G 中连通。 习题二 2、证明：每棵恰有两个 1度顶点的树均是路。 证明：设树T 为任意一个恰有两个1度顶点的树，则 T 是连通的，且无圈，令 V i 、V 2为度为1的顶点，由于其他的顶点度数均为 0或者2，且T 中无圈，则从 M 到V 2有且 只有一条连通路。所以，每棵恰有两个 1度顶点的树均是路。得证。 n 5、证明：正整数序列(d 「d 2,…,d n )是一棵树的度序列当且仅当 d i 2(n 1)。 i 1 n 证明：设正整数序列(d^d ?,…，d n )是一棵树T 的度序列，则满足 d j i 1 n 边数，又有边数和顶点的关系 n E 1，所以 d i 2(n 1) i 1 14、证明：若e 是K n 的边，则(K n e) (n 2)n n 3。 若e 为Kn 的一条边，由Kn 中的边的对称性以及每棵生成树的边数为 n-1，Kn 的所有生 所以，K n - e 对应的生成树的棵数为： n 2 n 3 n 3 (K n e) n 2n (n 2)n 16、Kruskal 算法能否用来求： (1 )赋权连通图中的最大权值的树 2E ，E 为T 的 成树的总边数为：(n 1)n n 2 ,所以，每条边所对应的生成树的棵数为: n 2 (n 1)n 」 n(n 1) 2 小 n 3 2n

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

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

图论的发展及其在现实生活中的几个应用

图论的发展及其在生活中的应用 数学与应用数学张佳丽 指导教师刘秀丽 摘要主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。 关键词图论生活问题应用 Graph Theory Development and the Application in Life Mathematics and applied mathematics Zhang Jiali Tutor Liu Xiuli Abstract This paper mainly introduces the origin and development of graph theory and its several applications in our life, such as: crossing river problem, traveling salesman problem, minimum spanning tree problem, four color problem，arrangement problem，Chinese postman problem．It also researches several methods that are more widely applied in graph theory, for example: the method of most neighboring, the method of solving the minimum spanning tree，the method of the best route，and so on． Key words graph theory life problem application 引言 图论是一门古老的学科，是数学中有广泛应用的一个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数分析等有着密切的联系．图论中以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系．事实上，任何一个包含了二元关系的系统都可以用图论来模拟．而且,图论能把纷杂的信息变的有序、直观、清晰．由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要．图论在自然科学、社会科学等各个领域都有广泛的应用．随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，加速了图论向各个学科的渗透，尤其是网络理论的建立，图论与线性规划、动态规划等优化理论和方法互相渗透。同时，计算机的发展使图论成为数学领域中发展最快的分支之一．