離散數(shù)學圖論部分綜合練習-全文預覽
【正文】 示)，則圖G的點割集是 ．3．若圖G=V, E中具有一條漢密爾頓回路，則對于結點集V的每個非空子集S，在G中刪除S中的所有結點得到的連通分支數(shù)為W，則S中結點數(shù)|S|與W滿足的關系式為 ．4．無向圖G存在歐拉回路，當且僅當G連通且 ．5．設有向圖D為歐拉圖，則圖D中每個結點的入度 ．6．設完全圖K有n個結點(n179。離散數(shù)學圖論部分綜合練習ooooocabedof圖一1．設圖G＝V, E，則下列結論成立的是 ( )．A．deg(V)=2189。E189。（2）圖G1的歐拉回路為：（不惟一）：ooooov5v1v2v4v6ov3圖九v1(v1, v2) v2 (v2, v3) v3 (v3, v4) v4 (v4, v5)v5 (v5, v2) v2 (v2, v6)v6 (v6, v4) v4 (v4, v1)v13．解：圖G是平面圖．因為只要把結點v2與v6的連線(v2, v6)拽到結點v1的外面，把把結點v3與v6的連線(v3, v6)拽到結點v4, v5的外面，就得到一個平面圖，如圖九所示． 4．解：錯誤． 不滿足“設G是一個有v個結點e條邊的連通簡單平面圖，若v≥3，則e≤3v6．”四、計算題1．oooooa1a2a3a4a5解：（1）圖G是有向圖： （2）圖G是單側連通圖，也是弱連通圖． 2．v1v2v3v4v5ooooo解：（1）圖G如圖十 （3）deg(v1)=2 deg(v2)=3v1v2v3v4v5ooooodeg(v3)=4deg(v4)=3deg(v5)=2 （4）補圖如圖十一 圖十一3．解：（1）G的圖形如圖十二 圖十二 （2）v1，v2，v3，v4，v5結點的度數(shù)依次為1
環(huán)評公示相關推薦
鄂ICP備17016276號-1