第2章图论基础.pptVIP

第2章图论基础第1页，共23页，星期日，2025年，2月5日图“节点”，以及哪些节点之间有“边”第2页，共23页，星期日，2025年，2月5日作为一个数学概念的“图”（graph）节点，边（圆括号表示（x,y）中的元素次序无关）标号图（labeledgraph），无标号图（graph）同构，异构第3页，共23页，星期日，2025年，2月5日（不一样的）图的个数（枚举）给定节点数（n）标号图？无标号图？Polya定理告诉我们如何计算无标号图的个数如何判断两个图是否“同构”依然是图论的最基本挑战之一第4页，共23页，星期日，2025年，2月5日无标号图的个数第5页，共23页，星期日，2025年，2月5日无向图，有向图（directedgraph）也可以是标号或者无标号的x,y和y,x有可能同时存在第6页，共23页，星期日，2025年，2月5日路，距离，连通，连通分量路（path，路径，通路）：节点序列，相邻两个节点之间存在一条边长度：节点数减1；或者，所涉及边的条数简单路径，回路（仅端点相同的路径）距离：两个节点之间最短路径的长度连通图：任何两个节点之间都存在一条路连通分量连通子图不被真包含在任何其他连通子图中第7页，共23页，星期日，2025年，2月5日例子：路，距离，连通分量节点I和M之间有多少不同的路？有多少不同的简单路径？它们之间的距离？({A,B},{(A,B)})是不是连通分量？({H,L,M},{(H,L),(L,M),(H,M)})是不是连通分量？第8页，共23页，星期日，2025年，2月5日大规模社会网络中的超大连通分量第9页，共23页，星期日，2025年，2月5日桥，捷径（localbridge）桥：具有特别性质的边，删除它，其两个端点之间就不再有路删除它，增加图的连通分量的个数捷径：也是一种边，删除它，其两个端点之间的距离至少为3。桥可以看成是捷径的一个特例第10页，共23页，星期日，2025年，2月5日对于有向图：有向路径，强连通分量有向路径：节点序列，相邻节点之间有从前往后的有向边强连通分量任意两个节点之间存在有向路径（两个方向）的有向子图不被真包含在任何其他满足性质(1)的子图中({B,C,D},{B,C,C,D,D,B})第11页，共23页，星期日，2025年，2月5日二部图，图上的广度优先有哪些信誉好的足球投注网站二部图（bipartitegraph）：节点可以被分成两组，组内没有边图上的广度优先有哪些信誉好的足球投注网站（breadth-firstsearch）从某一点开始，对图的节点的一种“遍历”方式第12页，共23页，星期日，2025年，2月5日从LINC开始广度优先有哪些信誉好的足球投注网站{LINC}{MIT,CASE}{CARN,BBN,UTAH}{HARV,SDC,RAND,SRI}{UCSB,UCLA,STAN}BFS从概念上对图中的节点进行了一个“分层”，所涉及到的边“自然形成了”一个二部图第13页，共23页，星期日，2025年，2月5日典型现实网络（图）合作图例如，一群学者之间合著关系（co-authorship）节点：人；边：当且仅当两个人有合著的文章交流网例如，一所大学师生之间的电子邮件关系网节点：人；边：两人之间发过一定量的往返邮件信息链接网（有向）万维网上的网页之间的链接关系论文之间的引用关系…第14页，共23页，星期日，2025年，2月5日网络数据的计算机表示邻接矩阵（adjacencymatrix）相邻节点列表关联矩阵（incidencematrix）边序列相邻节点列表1：2,3,42：1,43：1,44：1,2,3边序列1,21,31,42,43,4第15页，共23页，星期日，2025年，2月5日图的展示与分析工具现实应用中，图一般都是首先从描述节点和边的数据而来根据那些数据，适当地给出一个“形象表示”（即画出一个图），常常是很有必要的；而根据那些数据，得出某些结论更是网络分析所追求的目标为此，人们开发了许多工具Pajek,UCINET,NetMiner,MultiNet,X-Rime，等Cuttlefish，一个简单易用工具的例子第16页，共23页，星期日，2025年，2月5日小结第17页，共23页，星期日，2025年，2月5日这一张讨论几个计数问题，特别提出“散点图”，“完全图”*学生签到：姓名，性别，学号，院系，年级*