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

HintstoExercisesinChapter2

Ex2.1.2Theassertion(c)canbeprovedstructurally.

Ex2.1.3v1=v3+2v4+···+( 2)v +2=2+

i=3(i 2)vi=2+ x∈U(dG(x) 2).

Ex2.1.4Therearesomewrongsinthisexercise.Itshouldbecorrectedas“Provethatif{X,Y}isabipartitionofTwith|X|=|Y|=k,thenthereareatleast(k+1)verticesofdegreeoneinX.”Byinductiononk≥0.

Ex2.1.15SinceanytwospanningtreesofXhavethesamenumberofedges,thesymmetricdi erenceoftheiredgesetsiseven,say2m.ToprovethatT(X)isconnected,itissu cienttoshowthatanytwospanningtreesofX,astwovertices,areconnectedinT(X).Wecandothisbyinductiononm≥1.Ifm=1,then,bythede nitionofT(X),thetwospanningtreesareadjacentinT(X),andsoareconnected.AssumeanytwospanningtreesofXareconnectedinT(X)ifthesymmetricdi erenceoftheiredgesetsislessthan2m.

LetTandT betwospanningtreesinXthatthesymmetricdi erenceoftheiredgesetsis2mwithm≥2.letE1=E(T)\E(T )andE2=E(T )\E(T).Then|E1|=|E2|=m.SinceT isaspanningtreeofX,foranedgee∈E1,T +econtainsonlycycle,denotedbyCe.SinceT containsnocycle,thereexistsexactlyoneedgee ∈E2∩E(Ce)suchthatT =T e +eisaspanningthreeofX.Itisclearthatthesymmetricdi erenceofE(T )andE(T )is2,andthus,theyareadjacentinT(X).Also,thesymmetricdi erenceofE(T)andE(T )is2(m 1),andthus,bytheinductionhypothesis,theyareconnectedinT(X).ItfollowsthatTandT areconnectedinT(X).Ex2.3.2SeeExample1.10.2.

Ex2.3.3Theproofsof(a)and(b)aresimilartoExample2.3.2.As(c),ifGisnotbipartite,thenGcontainsanoddcycle.LetCbeashortestoddcycle.Thedeterminantofthesub-matrixofMrespondingtotheverticesandedgesinCisequaltotwo,acontradiction.Conversely,byinductiononk≥1,whichisorderofasub-matrixofM.Intheinductionstep,assumeP +1isasub-matrixofM.Ifthereisexactlyonenon-zeroentryinsomecolumn,thenitiseasytoprovedetP +1=0,±1.Assumethereareexactlytwonon-zeroentriesinP +1below.ItisclearthatdetP +1=0sincethesumofanycolumnistwo.

Ex2.3.6Foreachvertexy=x,selectonein-comingedgeofy.LetTbetheinducedsubgraphbytheseedges.ThenTisanin-treerootedatx,forThasv 1

edges,containsnodirectedcycles,d T(x)=0,dT(y)=1foranyy=x(seeExercise

2.1.1).Conversely,everyin-treerootedoccursinthisway.Hencethenumberof atx

suchin-treesrootedatxis x(G)=d G(y).

y∈V\{x}

5

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