《图论基础.pdf》由会员分享，可在线阅读，更多相关《图论基础.pdf（23页珍藏版）》请在三一文库上搜索。
1、图论基础 与网络分析有关的基本概念 图 “节点”，以及哪些节 点之间有“边” 作为一个数学概念的“图”（graph） 节点，边（圆括号表示（节点，边（圆括号表示（x,y）中的元素次序无关）中的元素次序无关 ） 标号图（标号图（labeled graph），无标号图（），无标号图（graph） 同构，异构同构，异构 G(V,E), V =a,b,.,E (x,y)|x,y V,x y （不一样的）图的个数（枚举） 给定节点数（给定节点数（n） 标号图？标号图？ 无标号图？无标号图？ 2 n 2 Polya定理告诉我们如何计算无标号图的个数定理告诉我们如何计算无标号图的个数 如何判断两个图是否“同
2、构”依然是图论的最基如何判断两个图是否“同构”依然是图论的最基 本挑战之一本挑战之一 无 标 号 图 的 个 数 无向图，有向图（directed graph） 也可以是标号或者无标号的也可以是标号或者无标号的 和和有可能同时存在有可能同时存在 G(V,E), V =a,b,.,E |x,y V,x y 路，距离，连通，连通分量 路（路（path，路径，通路）：节点序列，相，路径，通路）：节点序列，相 邻两个节点之间存在一条边邻两个节点之间存在一条边 长度：节点数减长度：节点数减1；或者，所涉及边的条数；或者，所涉及边的条数 简单路径，回路（仅端点相同的路径）简单路径，回路（仅端点相同的路径）
3、 距离：两个节点之间最短路径的长度距离：两个节点之间最短路径的长度 连通图：任何两个节点之间都存在一条路连通图：任何两个节点之间都存在一条路 连通分量连通分量 1.连通子图连通子图 2.不被真包含在任何其他连通子图中不被真包含在任何其他连通子图中 例子：路，距离，连通分量 节点节点I和和M之间有之间有 多少不同的路？多少不同的路？ 有多少不同的简单有多少不同的简单 路径？路径？ 它们之间的距离？它们之间的距离？ (A,B,(A,B)是不是不 是连通分量？是连通分量？ (H,L,M,(H,L),(L,M ),(H,M)是不是连是不是连 通分量？通分量？ 大规模社会网络中的超大连通分量 桥，捷径（
4、local bridge） 桥：具有特别性质的边桥：具有特别性质的边 ，删除它，其两个端点，删除它，其两个端点 之间就不再有路之间就不再有路 删除它，增加图的连通删除它，增加图的连通 分量的个数分量的个数 捷径：也是一种边，删捷径：也是一种边，删 除它，其两个端点之间除它，其两个端点之间 的距离至少为的距离至少为3。 桥可以看成是捷径的一桥可以看成是捷径的一 个特例个特例 对于有向图：有向路径，强连通分量 有向路径：节点序列，有向路径：节点序列， 相邻节点之间有从前往相邻节点之间有从前往 后的有向边后的有向边 强连通分量强连通分量 (1) 任意两个节点之间存在任意两个节点之间存在 有向路径（两
5、个方向）有向路径（两个方向） 的有向子图的有向子图 (2) 不被真包含在任何其他不被真包含在任何其他 满足性质满足性质(1)的子图中的子图中 (B,C,D, ,) 二部图，图上的广度优先搜索 二部图（二部图（bipartite graph）：节点可以）：节点可以 被分成两组，组内没被分成两组，组内没 有边有边 图上的广度优先搜索图上的广度优先搜索 （breadth-first search ） 从某一点开始，对图从某一点开始，对图 的节点的一种“遍历的节点的一种“遍历 ”方式”方式 从LINC开始广 度优先搜索 LINC MIT, CASE CARN, BBN,UTAH HARV, SDC,
6、RAND, SRI UCSB, UCLA, STAN BFS从概念上对图中的节点进行从概念上对图中的节点进行 了一个“分层”，所涉及到的边了一个“分层”，所涉及到的边 “自然形成了”一个二部图“自然形成了”一个二部图 典型现实网络（图） 合作图合作图 例如，一群学者之间合著关系（例如，一群学者之间合著关系（co-authorship） 节点：人；边：当且仅当两个人有合著的文章节点：人；边：当且仅当两个人有合著的文章 交流网交流网 例如，一所大学师生之间的电子邮件关系网例如，一所大学师生之间的电子邮件关系网 节点：人；边：两人之间发过一定量的往返邮件节点：人；边：两人之间发过一定量的往返邮件 信
7、息链接网（有向）信息链接网（有向） 万维网上的网页之间的链接关系万维网上的网页之间的链接关系 论文之间的引用关系论文之间的引用关系 网络数据的计算机表示 邻接矩阵（邻接矩阵（adjacency matrix） 相邻节点列表相邻节点列表 关联矩阵（关联矩阵（incidence matrix） 边序列边序列 0111 1001 1001 1110 1110 1001 0100 0011 0 0 1 1 相邻节点列表相邻节点列表 1：2,3,4 2：1,4 3：1,4 4：1,2,3 边序列边序列 1,2 1,3 1,4 2,4 3,4 图的展示与分析工具 现实应用中，图一般都是首先从描述节点现实应
8、用中，图一般都是首先从描述节点 和边的数据而来和边的数据而来 根据那些数据，适当地给出一个“形象表根据那些数据，适当地给出一个“形象表 示”（即画出一个图），常常是很有必要示”（即画出一个图），常常是很有必要 的；而根据那些数据，得出某些结论更是的；而根据那些数据，得出某些结论更是 网络分析所追求的目标网络分析所追求的目标 为此，人们开发了许多工具为此，人们开发了许多工具 Pajek, UCINET, NetMiner, MultiNet, X-Rime，等 Cuttlefish，一个简单易用工具的例子一个简单易用工具的例子 小结 网络无处不在，行行网络无处不在，行行色色，对社会影响巨大色色，
9、对社会影响巨大 网络作为一门课程学习的两个重要角度：网络作为一门课程学习的两个重要角度： 、；它们不同但相互影响。；它们不同但相互影响。 图论：讨论网络结构的语言图论：讨论网络结构的语言 作业作业 不用交的：阅读不用交的：阅读第第1章，章，第第2章；基于章；基于教材中的教材中的 插图插图2.3，以，以UCLA为起始节点（根节点）画出该为起始节点（根节点）画出该 图图的宽度优先搜索结果的宽度优先搜索结果 下次课前交的：上网搜索，找到下次课前交的：上网搜索，找到3个不同类型的个不同类型的 网络图及其简单说明；第网络图及其简单说明；第2章章练习练习2.1 练习2.1 图论作为有效建模工具的原因之一在
10、于它的灵活性。许多图论作为有效建模工具的原因之一在于它的灵活性。许多 大型系统都可以用图论语言来概括其性质，进而系统地研究其大型系统都可以用图论语言来概括其性质，进而系统地研究其 影响结果。在这第一个练习中，我们利用影响结果。在这第一个练习中，我们利用关键节点关键节点的概念，通的概念，通 过一个例子来考察这个过程。过一个例子来考察这个过程。 首先，第首先，第2章所讲的两节点间最短路径对应该节点间的最短章所讲的两节点间最短路径对应该节点间的最短 距离。对于节点距离。对于节点Y和和Z，若，若X存在于存在于Y和和Z之间所有最短路径上，之间所有最短路径上， 则称则称X为为Y和和Z间的间的关键节点关键节
11、点（假定（假定X是不同于是不同于Y或或Z的节点）。的节点）。 例如，在图例如，在图2.13中，节点中，节点B是节点是节点A和和C之间、之间、A和和D之间的关之间的关 键节点（注意：键节点（注意：B并不是节点并不是节点D和和E之间的关键节点，因为之间的关键节点，因为D和和E 间存在两条不同的最短路径，而其中的一条（包含间存在两条不同的最短路径，而其中的一条（包含C和和F）并不）并不 通过通过B。由此可见，。由此可见，B并不存在于并不存在于D和和E之间的之间的所有所有最短路径上最短路径上 ）。此外，我们能看到节点）。此外，我们能看到节点D不是图中任意两个节点之间的关不是图中任意两个节点之间的关 键
12、节点。键节点。 练习2.1（续） （1）请举一个图例，使其满足以下条件：）请举一个图例，使其满足以下条件： 该图中每个节点均为至少一个节点对的关该图中每个节点均为至少一个节点对的关 键节点。请就你的答案给出解释。键节点。请就你的答案给出解释。 （2）请举一个图例，使其满足以下条件：）请举一个图例，使其满足以下条件： 该图中每个节点均为至少两个节点对的关该图中每个节点均为至少两个节点对的关 键节点。请就你的答案给出解释。键节点。请就你的答案给出解释。 （3）请举一个图例，满足以下条件：该图）请举一个图例，满足以下条件：该图 中包含至少中包含至少4个节点，并存在一个节点个节点，并存在一个节点X，
13、它是图中所有节点对的关键节点（不包括它是图中所有节点对的关键节点（不包括 含含X的节点对）。请就你的答案给出解释。的节点对）。请就你的答案给出解释。 练习2.3 当我们试图就一个图的节点间的距离寻找一个单一的综合当我们试图就一个图的节点间的距离寻找一个单一的综合 衡量指标时，有两个自然的量值得考虑。一个是衡量指标时，有两个自然的量值得考虑。一个是直径直径，我们，我们 定义它为图中所有两节点之间距离的最大值；另一个是定义它为图中所有两节点之间距离的最大值；另一个是平均平均 距离距离，我们定义它为图中所有节点对距离的平均值。，我们定义它为图中所有节点对距离的平均值。 在许多图中，上述两个量在数值上的差别不大。但在有些在许多图中，上述两个量在数值上的差别不大。但在有些 图中它们则可能差的很远。图中它们则可能差的很远。 （1）请给出一个直径比平均距离大三倍的图例；）请给出一个直径比平均距离大三倍的图例； （ （2）请根据你解答问题）请根据你解答问题(1)的方法，说明你可以通过改变某的方法，说明你可以通过改变某 一特定因数的大小，来控制直径比平均距离大的倍数。（换一特定因数的大小，来控制直径比平均距离大的倍数。（换 句话说，对于任意数字句话说，对于任意数字c，你能否构造一个图，使其直径比平，你能否构造一个图，使其直径比平 均距离大均距离大c倍？）倍？）