離散圖論部分習題ppt課件(編輯修改稿)
2025-05-26 03:20 本頁面
【文章內(nèi)容簡介】 圖是否同構(gòu) : (1) 度數(shù)列不同 不同構(gòu) (2) 不同構(gòu) 入 (出 )度列不同 (3) 度數(shù)列相同 但不同構(gòu) 解 : 根據(jù)自補圖的定義其對應的完全圖的邊數(shù)是 2m. 6. 一個圖是自補圖 ,設頂點數(shù)為 n,其邊數(shù)為 m,其對應的 完全圖的邊數(shù)是多少 ? 7. 設無向簡單連通圖 G有 16條邊 ,有 3個 4度頂點 ,4個 3度頂點 ,其余頂點的度數(shù)都小于 3,問 G至少有多少個頂點 ,至多有多少個頂點 ? 解 : 由題設可知 ,圖 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度點 。 至多有 15個頂點 : 3個 4度點 ,4個 3度點和 8個 1度點 . 8. 設 G1,G2,G3,G4均是 4階 3條邊的無向簡單圖 ， 則它們之間至少有幾個是同構(gòu)的 ？ 解： 4階 3條邊非同構(gòu)的無向簡單圖共有 3個，因此G1,G2,G3,G4中至少有 2個是同構(gòu)的。 解 : 由于頂點為 n的無向完全圖的邊數(shù)為 . 2)1( ?nn設 G的自補圖為 G’,則 G與 G’的邊數(shù)相等 . 設它們的邊數(shù)各為 m,于是有 m+m= 2)1( ?nn即 m=n(n1)/4, 而 m為正整數(shù) ,所以要么 n=4k或 n=4k+1, 所以不存在 3個頂點和 6個頂點的自補圖 . 9. 是否存在 3個頂點和 6個頂點的自補圖？ 證明 :由于度數(shù)為奇數(shù)的頂點必為偶數(shù)個 ,所以度數(shù)為 5的頂點個數(shù)必為偶數(shù) ,即可能為 0、 9個頂點 ,所以 6度的頂點個數(shù)分別為 1,于是圖 G中至少有 5個 6度的頂點或至少有 6個 5度的頂點 . 10. 無向圖 G中有 9個頂點 ,每個頂點的度數(shù)不是 5就是 6, 證明 :圖 G中至少有 5個 6度的頂點或至少有 6個 5度的頂點 .
教學課件相關(guān)推薦
鄂ICP備17016276號-1