離散數(shù)學(xué)及其應(yīng)用圖論部分課后習(xí)題答案-資料下載頁
2025-06-07 21:12本頁面
【正文】 1，2兩個頂點點度為3，其它為偶數(shù)。？哪些是半歐拉圖？對歐拉圖給出一條歐拉回路。對半歐拉圖給出一條歐拉通路。對不是的，說明不是歐拉圖或半歐拉圖的理由。解答：（a）為半歐拉圖，a,c兩點的出度和入度都相等；b點的入度比出度大1；c點的入度比出度小1.（b）為歐拉圖，每個頂點的入度和出度都相等。判斷命題的真假。（1）完全圖是歐拉圖。（2）階有向完全圖是歐拉圖。（3）當r,s為正偶數(shù)時，完全二部分圖是歐拉圖。解答：（1）為假，因為當n為偶數(shù)時，每個點的點度都為奇數(shù)。（2）真；有向完全圖的出度和入度必然相等。（3）真，完全二部分圖中，一部分點的點度全為r,另外一部分點的點度全為s。，也不半哈密頓圖的理由。解答：（a）刪掉畫圈的3個頂點，還剩下5個連通分支；（b）刪掉畫圈的4個頂點，還剩下6個連通分支。，也不半哈密頓圖。1設(shè)G是無向連通圖，證明：若G中有橋或者割點，則G不是哈密頓圖。證明：① 若G中有者割點，取，則，G不是哈密頓圖。② 若G中有者割邊，如果和的點度都為1，則該圖只有一條邊，顯然不為哈密頓圖；③ 如果和的點度至少有一個大于1，不妨設(shè)的點度大于1，取，則，G不是哈密頓圖。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1