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

whereF={f:fisaninjectivefrom{1,2,···,m}to{1,2,···,n}},and|F|=n(n 1)···(n m+1).LetX={x1,x2,···,xm}andY={y1,y2,···,ym}.Ifa1f(1)a2f(2)···amf(m)=0,thena1f(1)a2f(2)···amf(m)=0denotesthatthesetofedges

EG(x1,yf(1))= ,EG(x2,yf(2))= ,···,EG(xm,yf(m))= .

Thus,a1f(1)a2f(2)···amf(m)isthenumberofthematchingsthatsaturateXandconsistofedgedinthesetofedges

EG(x1,yf(1))∪EG(x2,yf(2))∪···∪EG(xm,yf(m)).

ItfollowsthatthenumberofthematchingsthatsaturateXisequaltoPer(A).

Ex5.2.5(a)ByTheorem5.6,itissu cienttoshowα(G)≤κ(G).Bycontradic-tion,ifα(G)>κ(G)=k,thenthereisanindependentsetIsuchthat|I|=k+1.A¯I)|≤k2<k(k+1)=|(I,I¯)|.contradictioncanbededuceasfollows.|(I,

(b)TheproofissimilartooneofTheorem5.7.Sinceα(G)=1ifandonlyifG～=Kv,assumeα(G)≥2.ChoosealongestcycleCinG.SupposetothecontrarythatCisnotaHamiltoncycle.Then,V(G)\V(C)= andT V(C).Choosex∈V(G)\V(C)andletT={x1,x2,···,xs}andoccursinCinthisorder.BythechoiceofC,anysuccessivetwoverticesin{x1,x2,···,xs}arenotadjacentinC,otherwisewecanconstructalongercyclethanC.→ SpecifyCadirectiontoobtainedadirectedcycleC.LetY={yi:(xi,yi)∈→ E(C),i=1,2,···,s}.ThenY∪{x}isanindependentsetofGandα(G)≥|I|=s+1≥|T|+1,contradictingtothehypothesis.

Ex5.2.6TheproofissimilartooneofTheorem5.7.Withoutlossofgenerality,assumeα(G)≥2.Bycontradiction,assumeα≥δ(G)+1.LetIandSbeamaximumindependentsetandaminimumseparatingsetofG,respectively.Then,foranyx,y∈I,wehave|NG(x)∪NG(y)|≤v α,and

|NG(x)∩NG(y)|=dG(x)+dG(y) |NG(x)∪NG(y)|

≥2δ (v α)≥3δ v+1≥κ+1>|S|.

ThisimpliesthatonlyoneofallcomponentsofG S,sayG1,maycontainverticesinI,thatis,I V(G1)∪S.Sinceα≥2δ+1,thereexistsx∈I∩V(G1).Chooseavertexzinothercomponent,sayG2,ofG S.Then

|NG(x)∪NG(z)|≤v 2 |I∩V(G1)|+1=v α+|I∩S| 1.

SinceNG(x)∩NG(z) S\I,thus,|NG(x)∩NG(z)|≤κ |I∩S|.Thus,weshouldhavethat

2δ≤dG(x)+dG(z)=v α+κ 1≤v+κ δ 2.

11(v+κ 2)<(v+κ).Fromthiswecandeduceacontradictionasfollows.δ≤Ex5.2.7Notethatthisexercisehasanerratum.Theexerciseisrestatedasfollows.LetGbealooplessdigraph.ProvethatGcontainsanindependentsetIsuchthatdG(I,y)≤2foranyy∈V(G)\I,wheredG(I,y)=min{dG(x,y):x∈I}.

10

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