连通图的一些性质

定义1:对于图中的两个结点A,B,若A,B由一条边相连,那么记边为(A, B),边的长度为L(A, B)  

定义2:对于图中顶点v,u,若存在一组连续的边(v,m1),(m1,m2),...,(mk,u),且v,m1,m2,...,mk,u互不相同,那么称这一组连续的边构建了一条由v到u的路径。

定义3:对于无向图G=(V,E),若对于V中任意结点对v,u,v与u之间总是有一条路径相连接,那么称G是连通图。

定义4:称图中两个顶点A,B的距离为两个顶点之间所有路径的长度中的最小值,记作D(A,B)。

命题1:对于连通图G=(V,E),必然有|E|>=|V|-1。

  证明:首先要认清一个图G=(V,E)必然是由若干个互不关联的子连通图组成的。继而,需要证明每次向图中增加一条边,或者不影响其互不关联的子连通图的数目(这条边落在了一个子连通图的内部),或者使得原图中两个子连通图相互连通,从而新的图中互不关联的子连通图的数目较原图减少1。

命题2:对于连通图G=(V,E),若|E|=|V|-1,则G中无环路(无向图中的环路必须拥有不少于三条边)。

  证明:需要证明对于一个带环连通图,移除环中任意一条边,图依旧连通,而根据命题1知道图连通的必要条件是|E|>=|V|-1,因此可以推导出原图至少有|V|条边。从而利用反证法证明命题的成立。

命题3:对于连通图G=(V,E),若|E|>=|V|,则G中必定有环路。

  证明:首先将V中的结点分为两组,S和U,S中的结点称为选择结点,而U中的结点称为未选择结点。一开始S为空而U=V。之后每次循环都选择一条边(s,u),其中s属于S,u属于U,将u选择,并从U中移除加入到S中,直到S=V。假如上面所述的循环中无法找到符合条件的边,那么我们就可以将图G切分为包含结点集S和U的互不关联的子连通图,这与G是全连通的前提相悖。这样一直到循环结束,我们总共选择了|V|-1条边,而实际上原图G只需要这被选择的|V|-1条边就可以全连通。而向图G中再增加任意一条边(x,y)都会造成环的出现,这是由于x与y在|V|-1条边时连通故已经存在一条路径,而新增的边与路径组合形成了一个环。  

  可以利用深度优先搜索算法在O(n)的时间复杂度内计算出无环连通图中距离最远的两个顶点,以及其距离。下面稍微说明一下具体算法:先选取任意一个顶点作为根结点,这样就构建了一个单结点树。之后对于每个出现在树中的结点N,将所有与N有边连通且未被加入到树中的顶点作为N的子结点加入到树中。由于前提中包含连通图无环这个条件,因此除了N的直属子结点和直属父结点外没有其它结点能通过一条边连接N,而连通图的性质保证所有结点都会被加入到树中。

命题4:对于某个结点R,其两个不同的子结点A和B,以及对于X=A的某子孙结点或A,Y=B的某子孙结点或B,必然有D(X,Y)=D(X,R)+D(Y,R)。

  证明:要证明这个命题,由于无环路,因此连通图中任意两个结点之间的路径唯一,故只需要说明X到R的路径和Y到R的路径除了R外没有重复顶点即可。由于X到A的路径中的所有结点都是A或A的子孙结点,而Y到B的路径中的所有结点都是B或B的子孙结点,因此可以保证X到A与Y到B的路径没有重复顶点。

  利用命题4,可以为每个顶点V维护两个值END,MID,其中V.END记录所有V的子孙结点到V的距离的最大值,而V.MID记录所有V的子孙结点之间的最大值。若已知结点F的所有子结点C1, C2, ..., Ck的END和MID值后,可以利用下面公式推出F的END和MID值:

  F.END= MAX(C1.END+ L(F, C1),  ... , Ck.END+ L(F, Ck))

  F.MID= MAX(

      MAX(C1.END+ L(F, C1),  ... , Ck.END+ L(F, Ck)) + SECONDARY-MAX(C1.END+ L(F, C1),  ... , Ck.ENDEND+ L(F, Ck)),

      MAX(C1.MID, ... , Ck.MID)

      )

  其中F.MID的推导公式可能会有点难理解,需要理解F的距离最远的两个子孙结点或者是F的同一个子结点X的子孙结点或X,此时其距离为X.MID;或者是F的两个不同的子结点本身或子结点X与Y,这时候就需要利用命题4来证明其等于D(X, F) + D(Y, F)。

  因此利用深度优先搜索可以在O(n)的时间复杂度内建立树,并且在O(n)的时间复杂度内利用树带来的父子关系推导出每个结点的END和MID值。而整个连通图中距离最远的两个结点的距离则为ROOT.MID。如果还需要知道距离最大的两个结点,只需要为每个结点多增加几个属性即可。