離散圖論部分習(xí)題ppt課件-展示頁
2025-05-08 03:20本頁面
【正文】 解 : 由題設(shè)可知 ,圖 G中有 16條邊 ,所以圖 G中各點的度數(shù) 之和為 32. 又由于圖 G中有 3個 4度頂點和 4個 3度頂點 ,這 7個點的度數(shù) 之和為 24,而圖 G中其余點的度數(shù)小于 3,即圖 G中其余點的 度數(shù)只可能是 2或 1(由于圖 G是連通圖 ,所以無零度點 ). 由此可知 ,圖 G中至少有 11個頂點 : 3個 4度點 ,4個 3度點和 4個 2度點 。 （ ） （ 1） 1， 1， 2， 3， 5 （ 2） 1， 2， 3， 4， 5 （ 3） 1， 3， 1， 3， 2 （ 4） 1， 2， 3， 4， 6 13. 如圖是二部圖 ， 求其最大匹配 。 推論 2： n階有向完全圖， 共有 n(n1) 條邊。本章重點 一、掌握有關(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 共有 條邊。 四 、 掌握圖的同構(gòu) 五、 掌握 補(bǔ)圖及自補(bǔ)圖 六、 掌握 二部圖及完全二部圖 七、 掌握求 二部圖的最大匹配的方法 八、 掌握 歐拉圖及半歐拉圖及其應(yīng)用 思考題： 1. 有 9個人一起打乒乓球，已知他們每人至少與其中另外3個人各打過一場球，試證明至少有一人不止和 3個人打過球 . 3. 設(shè) n階圖 G中有 m條邊 ,每個頂點的度數(shù)不是 k就是 k+1, 若 G中有 Nk個 k度頂點 ,Nk+1個 k+1度的頂點 ,試求出頂點個數(shù) Nk的表達(dá)式 . 2. 若無向圖 G有 12條邊， G中有 6個 3度結(jié)點，其余結(jié)點度數(shù) 均為 2，問 G
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1