離散圖論習題解答

離散圖論習題解答離散圖論習題解答離散圖論習題解答資料僅供參考文件編號：2022年4月離散圖論習題解答版本號：A修改號：1頁次：1.0審核：批準:發(fā)布日期：以下內容供參考！歡迎補充~~~.19.設G是n階自補圖,證明n=4k或n=4k+1,其中k為正整數.設G是n階m條邊的自補圖,則G為n階m條邊的簡單圖,且G??G.于是,?G的邊數m'=m,且m+m'=2m=n(n?1)/2.于是n(n?1)=4m,因而n=4k,或n?1=4k,k為正整數..21.無向圖G如圖所示.(1)求G的全部點割集和邊割集,并指出其中的割點和橋(割邊);(2)求G的點連通度κ(G)和邊連通度λ(G).(1)點割集兩個{a,c},vd5xdfn,d是割點.7個邊割集:{e5},{e1,e3},{e2,e4},{e1,e2},{e2,e3},{e3,e4},{e1,e4},e5是橋.(2)因為既有割點又有橋,所以κ=λ=1..22.無向圖G如圖所示,現(xiàn)將該圖頂點和邊標定.然后求圖中的全部割點和橋,以及圖的點連通度和邊連通度.第14題答圖標定如答圖.3個割點:d,f,h.3個橋:e5,e9,e10.因為既有割點又有橋,所以κ=λ=1..23.求圖所示圖G的κ(G),λ(G)和δ(G).κ=2,λ=3,δ=4..43.有向圖D如圖所示.D中有多少種非同構的圈有多少種非同構的簡單回路答：有2種非同構的圈，長度為2和3；有3種非同構的簡單回路，長度為2，3，5求a到d的短程線和距離d<a,d>.a到d的短程線為aed，d<a,d>=2求d到a的短程線和距離d<d,a>.d到a的短程線為deba，d<d,a>.=3判斷D是哪類連通圖.單向連通圖對D的基圖討論(1),(2),(3)三個問題.答：有4種非同構的圈，長度為2，3，4,5；有7種非同構的簡單回路除了4種非同構的圈外，還有3種非圈的簡單回路。長度為5,6,8；a到d的短程線有3條，d<a,d>=2d到a的短程線有3條d<d,a>=2.14.今有n個人,已知他們中的任何二人合起來認識其余的n?2個人.證明:當n≥3時,這n個人能排成一列,使得中間的任何人都認識兩旁的人,而兩旁的人認識左邊(或右邊)的人.而當n≥4時,這n個人能排成一個圓圈,使得每個人都認識兩旁的人.作n階簡單無向圖G=<V,E>,V=這n個人的集合,E={(u,v)|u,v∈V∧u≠v∧u與v認識}.?u,v∈V,.(1)若u,v相鄰,則d(u)+d(v)≥(n?2)+2=n.(2)若u,v不相鄰,則?w∈V?{u,v},w必與u和v都相鄰.否則,比如u和w不相鄰,則v,w都不鄰接u,于是u和w合起來至多與其余的n?3個人認識,與已知條件不符.因而d(u)+d(v)≥2(n?2).當n≥3時,2(n?2)≥n?1,因此無論第(1)或(2)種情形,都有d(u)+d(v)≥n?1,由定理知G中有哈密頓通路,通路上的人按在通路中的順序排成一列,滿足要求.當n≥4時,2(n?2)≥n,因此無論第(1)或(2)種情形,都有d(u)+d(v)≥n,由定理的推論知G中有哈密頓回路,回路上的人按在回路中的順序排成一個圓圈,滿足要求..15.某工廠生產由6種不同顏色的紗織成的雙色布.已知在品種中,每種顏色至少能與其他5中顏色中的3種相搭配.證明可以挑出3種雙色布,他們恰由6種不同顏色的紗織成.作無向簡單圖G=<V,E>,V={v|v為6種顏色的紗之一},|V|=6,E={(u,v)|u,v∈V∧u≠v∧u與v能搭配}.由給出的條件知,?u,v∈V,有d(u)+d(v)≥3+3=6=|V|.由定理的推論知,G是哈密頓圖,因而有哈密頓回路,設C=vi1vi2vi3vi4vi5vi6vi1為其中的一條.任何兩個頂點在C中相鄰,說明這兩個頂點代表的顏色的紗可以搭配成雙色布.讓vi1與vi2的搭配,vi3與vi4的搭配,vi5與vi6的搭配就可以織成3種雙色布,恰用了6種不同的顏色..26.設T為非平凡樹,Δ(T)≥k,證明T至少有k片樹葉.證法一設T中有x片樹葉,則T中有n?x個分枝點(度數≥2),其中至少有個1個頂點度數為Δ(≥k).由樹的性質及握手定理知2m=2(n?1)=Σd(v)≥x?1+(n?x?1)?2+Δ.整理得x≥Δ≥k..29.設G為n(n≥5)階簡單圖,證明G或?G中必含圈.首先利用第23題的結論確認無圈的圖(森林)的邊數m=n?p≤n?1.(反證法)假如G和?G都不含圈,則1/2n(n?1)=|E(K