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