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

nonadjacentverticesx∈X,y∈Y,whereX={x1,x2,···,xn},Y={y1,y2,···,yn}.LetC=(x1,y1,x2,y2,···,xn,yn,x1)beaHamiltoncycleinG+x1y1andlet

I={i:2≤i≤n,x1yi∈E(G)}.

ThenI=NG(x1)andxi 1y1∈/E(G)foranyi∈I.Thus,NG(y1) X\{xi 1:i∈I},andsodG(y1)≤n |I|=n dG(x1),fromwhichacontradictionisdeducedasfollows.dG(x1)+dG(y1)≤n.

(b)From(a),itissu cienttoprovethatdG(x)+dG(y)>nforanytwononadjacentverticesx∈Xandy∈Y.Bycontradiction.Assumethatthereexisttwononadjacentverticesx∈Xandy∈YsuchthatdG(x)+dG(y)≤n.SinceGisbipartiteand|X|=|Y|=n,GcanbeviewedasagraphobtainedfromKn,nbydeletinghedges.Ontheonehand,

h=n2 ε(G)<n2 (n2 n+1)=n 1.

Ontheotherhand,forx∈Xandy∈Y,

h≥[n dG(x)]+[n dG(y)] 1=2n [dG(x)+dG(y)] 1≥n 1.

Thisisacontradiction.

Ex1.10.5(d)LetA =B AandX=(x1,x2,···,xv}beanyvector.Then

T XAX=(xi xj)2≥0,

ij∈E(G)

theequalityholds X=(1,1,···,1).Thus,A semi-positive.

(= )Byinductiononv≥1.Ifv=1,A=O,A =O,andso,rankA =0=1 1.Assumetheassertionholdsforanyconnectedgraphoforderlessthan<v,andletGbeasimpleundirectedgraphoforderv,di=dG(xi)(i=1,2,···,v).Chooseanon-cut-vertexofG(thereareatleasttwosuchverticesbyExample1.5.3).Withoutlossofgenerality,letx1besuchavertexandNG(x1)={x2,x3,···,xd+1}.Therearetwocases.

Case1d1<v 1.Inthiscase,AandtheadjacencymatrixofG x1canbeexpressedas

0J1,d1O1,v d1 1AA1112 ,A11A12A= Jd1,1Av 1=.A21A22Ov d1 1,1A21A22

De netwodiagonalmatricesasfollows.

P1=diag(d2 1,···,dd1+1 1)Id1

Bytheinductionhypothesis,

A v 1= P1 A11 A12

A21P2 A22

3 P2=diag(dd1+2,···,dv)Iv d1 1.T

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