離散圖論部分習(xí)題ppt課件(已修改)
2025-05-11 03:20 本頁面
【正文】 本章重點 一、掌握有關(guān)圖的基本概念： 鄰接 關(guān)聯(lián) 有向圖 無向圖 n階圖 底圖 平行邊 多重圖 連通圖 自回路（環(huán)） 簡單圖 二、掌握圖中頂點的度數(shù)，握手定理及其推論 定理：設(shè)圖 G是具有 n個頂點、 m條邊的無向圖， 其中點集 V={v1， v2， … v n }, 則 ???nii mv12)deg ( (握手定理 ) 由該定理可得： 推論 : 度數(shù)為奇數(shù)的頂點的個數(shù)必為偶數(shù)。 三、掌握有向完全圖和無向完全圖及推論 2)1( ?nn推論 1： n階無向完全圖 Kn 共有 條邊。 推論 2： n階有向完全圖， 共有 n(n1) 條邊。 四 、 掌握圖的同構(gòu) 五、 掌握 補圖及自補圖 六、 掌握 二部圖及完全二部圖 七、 掌握求 二部圖的最大匹配的方法 八、 掌握 歐拉圖及半歐拉圖及其應(yīng)用 思考題： 1. 有 9個人一起打乒乓球，已知他們每人至少與其中另外3個人各打過一場球，試證明至少有一人不止和 3個人打過球 . 3. 設(shè) n階圖 G中有 m條邊 ,每個頂點的度數(shù)不是 k就是 k+1, 若 G中有 Nk個 k度頂點 ,Nk+1個 k+1度的頂點 ,試求出頂點個數(shù) Nk的表達式 . 2. 若無向圖 G有 12條邊， G中有 6個 3度結(jié)點，其余結(jié)點度數(shù) 均為 2，問 G中有多少個結(jié)點？ 4. 試畫出 4階 3條邊的所有非同構(gòu)的無向簡單圖 . 5. 判斷下述每一對圖是否同構(gòu) ? (1) (2) (3) 6. 一個圖是自補圖 ,設(shè)頂點數(shù)為 n,其邊數(shù)為 m,其對應(yīng)的 完全圖的邊數(shù)是多少 ? 7. 設(shè)無向簡單連通圖 G有 16條邊 ,有 3個 4度頂點 ,4個 3度頂點 ,其余頂點的度數(shù)都小于 3,問 G至少有多少個頂點 ,至多有多少個頂點 ? 8. 設(shè) G1,G2,G3,G4均是 4階 3條邊的無向簡單圖 ， 則它們之間至少有幾個是同構(gòu)的 ？ 10. 無向圖 G中有 9個頂點 ,每個頂點的度數(shù)不是 5就是 6, 證明 :圖 G中至少有 5個 6度的頂點或至少有
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1