或者去掉一些边后形成一个树.一个连通图去掉一些边后形成的树称之为该连通图的生成树.一般来说,一个连通图的生成树可能不止一个.Р求一个连通图的生成树有一个简单算法,这个算法就是在一个连通图中破掉所有的回路,剩下不含回路的连通图就是原图一个生成树,这个算法叫做“破圈法”. Р图的矩阵Р图的矩阵表示一个图可以用几何图形表示,这种表示有直观形象的优点.图还可以用矩阵表示,它给出一个代数结构,从而可以运用代数的技巧解决图论问题,而且有利于在计算机上进行运算.Р特别应当提到的是,20世纪70年代出现了图的拟阵理论,它的发展对图的研究起到突出的促进作用.一个图由它的邻接性和关联性完全决定,这种信息可用矩阵表示.常用的有邻接矩阵和关联矩阵等.在无向图中前后相继连接的一串边的集合称为路.在有向图中,顺向的首尾相接的一串有向边的集合称为有向路.通常用顺次的节点或边来表示路或有向路,如图(2)中, 为一条路,该路也可用来表示.起点与终点为同一节点的路称为回路(或圈).如果一个图中,任意两个节点之间都存在一条路与之相连,称这种图为连通图.Р图(2)Р3. 无向图的邻接矩阵Р3.1 无向图的邻接矩阵定义及表示Р定义:设是图的结点,则称矩阵为的邻接矩阵,其中,是使邻接的边的条数并且是环时,,否则.Р例如Р则上图的邻接矩阵为:Р再如:Р它的邻接矩阵为:Р Р Р3.2 无向图的邻接矩阵的性质Р性质1 对角线元素全为0当且仅当图没有环.此时是对称矩阵. Р性质2 在没有环的图中,等于对应行或列中1的个数. Р性质3 的第行(或第列)元素之和为结点的度数.Р性质4 给定一个对称的元素0和1的阶矩阵,则必可构造一个图,使的邻接矩阵就是所给的. Р性质5 零图的邻接矩阵为零矩阵.Р例如图所示的图(3)和图(4).请写出其所对应的邻接矩阵Р图(4)Р图(3)Р则:图(3)的邻接矩阵为:Р;Р图(4)的邻接矩阵为:
全文预览
