图论及其应用徐俊明课后习题提示(4)

hasrankv 2.SinceA issemi-positive,P1 A22ispositiveandQ=P2 A11

1A12P 1A21issemi-positive.Thus,Q+Id1isinvertible.Ontheotherhand,let

diag(d2,···,dd1+1)Id1 A11 A12S=, A21diag(dd1+2,···,dv)Iv d1 1 A22

theth-(v 1)sub-matrixofA v,itsdeterminantdetS=detP1·det(Q+Id1)=0,and A v·Jv,1=Ov,1,thatis,rank(A)=v 1.

Case2d1=v 1.Inthiscase,

0J1,v 1A=,Jv 1,1Av 1

whereAv 1istheadjacencymatrixofG x1.diag(d2 1,···,dv 1) Av 1issemi-positiveanddiag(d2,···,dv) Av 1istheth-(v 1)sub-matrixofA ,whichisinvertible.SinceA ·Jv 1=Ov,1,rank(A )=v 1.

( =)Assumerank(A )=v 1andGisdisconnected.LetG1,G2,···,GωbeconnectedcomponentsofGwithordersv1,v2,···,vω,respectively.Then

A =diag(A v1,Av2,···,Avω),

whereA viistheLaplacematrixofGi(i=1,2,···,ω).SinceGiisconnected,thus,

rank(A vi)=vi 1,

Itfollowsthat

v 1=ω

i=1i=1,2,···,ω.(vi 1)=v ω,

fromwhich,ω=1,thatis,Gisconnected.

4

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库图论及其应用徐俊明课后习题提示(4)在线全文阅读。