《连通性支配定理证明》由会员分享，可在线阅读，更多相关《连通性支配定理证明（2页珍藏版）》请在装配图网上搜索。
1、定理： 给定图 g1，g2 和 g3, 如果 mccs(g1, g2) 的连通性支配了 g2 的连通性或者 mccs(g3, g2)的连通性支配了g2 的连通性，则 dist(gl, g3) W dist(gl, g2) + dist(g2, g3).证明：首先证明如果mccs(g1, g2)的连通性支配了 g2的连通性，则定理成立。假定F是从mccs(g1, g2)到g2的子图同构匹配，由此，如果在mccs(gl, g2)中 删除了边集导致mccs(g1, g2)不连通，那么在g2中删除F(S)会导致g2的不连通。注意 F(mccs(g1, g2)和mccs(g2, g3)均是g2的子图，现
2、证明F(mccs(g1, g2)与mccs(g2, g3) 的共有部分(记为F(mccs(g1, g2) A mccs(g2, g3)或者为0，或者为g2的联通子 图。假设F(mccs(g1, g2) A mccs(g2, g3)(丰)是不连通的。那么在F(mccs(g1, g2) A mccs(g2, g3)中至少有两个连通的部分存在。记c1和c2是F(mccs(g1, g2) A mccs(g2, g3)中两个最大连通部分且彼此不连通。Let Sbe the set of edges in F(mccs (g1, g2) each of which is either incident t
3、o avertex in c1 or to a vertex in c2 but is not contained in c1 or c2. It is immediate that S A E(mccs(g2, g3) = 0 since c1 and c2 are maximum in F(mccs(g1, g2) A mccs(g2, g3).According to the definition ofS , the removal ofS makesF(mccs(g1, g2) disconnected. Hence, the removal ofF-1(S ) makesmccs(g
4、1, g2) disconnected. Therefore, the removal ofSmakesg2 disconnected according to the assumption; thatis, g2 - S is disconnected. Since SA E(mccs(g2, g3) = 0, c1 u mccs (g2, g3),c2 u mccs(g2, g3), and g2 一 S is disconnected, it is immediate that mccs(g2, g3) is disconnected.Contradicting! Therefore,F
5、(mccs(g1, g2) A mccs(g2, g3) is either 0 or connected. Thus,|E(mccs(g1, g3)| |E(F(mccs(g1, g2) A E(mccs(g2, g3) |(1)We can represent |E(g2)| as follows where a ( 0) is the number of edges in g2 not included in F(mccs(g1, g2) nor in mccs(g2, g3).|g2| = a + IE(F(mccs(g1, g2)| + IE(mccs(g2, g3)|一 IE(F(
6、mccs(g1, g2) A mccs(g2, g3)|(2)From (1) and (2), together with the definition of graph relaxation distance, the theorem follows.Similarly, we can prove the theorem if the connectivity mccs(g3, g2) dominates g2.r呂9LOLIL2L3Algorithm 1: FixHead Verify (a, g、seq. I)Input ;(7 也 且 given query relaxation t
7、hresliold; is a data gr:seq is ql QI-Sequence;I is the current depth, initially 1;if UnmatchedEdges(se*7h Q a then return true ; while Next Match ( f .sEdge g) dot= MissingBackwardEdge5(i,!irfe5, :if e 1 Ar J 2 then GetNewSeq &eq ElrsEd-ge);if | I thene： MissingEdgesi El Ede);if e thenif FixHeadVerify(r e3 gr seqf, i) then | return TrueL4 return false
连通性支配定理证明
