簡介本資源是哈爾濱工業(yè)大學(xué)《集合論與圖論下》慕課MOOC課程的配套習(xí)題答案整理面向計算機(jī)、數(shù)學(xué)及相關(guān)專業(yè)本科生及自學(xué)者助力系統(tǒng)掌握圖論核心理論與解題方法。內(nèi)容覆蓋圖的基本類型簡單圖、有向/無向/加權(quán)圖、樹與連通性、鄰接矩陣與鄰接表表示法、補(bǔ)圖與偶圖、歐拉圖與哈密頓圖判定、圖著色、平面圖、割點橋分析及最短路徑算法等關(guān)鍵模塊緊扣課程講義邏輯適合作為課后鞏固、考前復(fù)習(xí)與自學(xué)驗證的重要參考。資源為單個PDF文件共1個文件大小3.16MB排版清晰、章節(jié)對應(yīng)明確含第1–4講完整答案便于打印查閱與碎片化學(xué)習(xí)。已有359人下載學(xué)習(xí)答案基于高頻重復(fù)題型歸納整理注重選項辨析與思路提示雖非官方發(fā)布但結(jié)構(gòu)完整、標(biāo)注細(xì)致對提升圖論建模能力與應(yīng)試效率具有實用價值。1. 圖論下半程一張從“連通性”出發(fā)的復(fù)習(xí)地圖專治慕課刷題時的選項眩暈癥如果你正在刷《哈工大集合論與圖論下》慕課點開第3講歐拉圖發(fā)現(xiàn)題干和上一講補(bǔ)圖的題只差一個“無向”或“有向”字眼但四個選項卻像鏡像翻轉(zhuǎn)般似是而非或者做哈密頓圖判斷題時明明記得“度數(shù)條件只是充分非必要”可選項里偏偏混進(jìn)一個“所有頂點度≥n/2就一定是哈密頓圖”的陷阱——恭喜你已正式進(jìn)入圖論下半程的認(rèn)知深水區(qū)。這門課不是單純堆砌定義而是用連通性作為暗線把圖的基本結(jié)構(gòu)第1講、結(jié)構(gòu)性質(zhì)第2講、遍歷能力第3–4講三者擰成一股繩連通圖是舞臺補(bǔ)圖與偶圖是結(jié)構(gòu)對照組歐拉圖檢驗“邊遍歷”的可行性哈密頓圖則挑戰(zhàn)“點遍歷”的存在性。整套邏輯閉環(huán)嚴(yán)密但慕課題庫的高重復(fù)率恰恰放大了細(xì)微概念差別的殺傷力——比如“連通圖的補(bǔ)圖是否一定不連通”這種題表面考補(bǔ)圖實則在逼你調(diào)用連通性反證法極端構(gòu)造三重思維。這份答案整理不是解題速查表而是一份按知識模塊切片、帶易錯歸因的復(fù)習(xí)地圖它幫你把零散的“選A還是選C”升維成“這個判定條件背后依賴哪條定理的哪個前提”。適合兩類人一是剛學(xué)完四講想系統(tǒng)串線的初學(xué)者二是刷題卡在60分反復(fù)橫跳、急需定位知識斷點的備考者。2. 圖的基本概念與表示法從“點邊關(guān)系”到“機(jī)器可讀”的轉(zhuǎn)換關(guān)鍵2.1 四類圖的本質(zhì)差異為什么“有向”二字能顛覆整個判定邏輯圖論中“類型”不是標(biāo)簽而是計算規(guī)則的開關(guān)。簡單圖、有向圖、無向圖、加權(quán)圖的區(qū)別核心在于邊的數(shù)學(xué)定義方式這直接決定后續(xù)所有算法的輸入結(jié)構(gòu)和判定條件簡單圖Simple Graph邊集是頂點無序?qū)Φ募锨也缓h(huán)vi, vi和重邊。這是最“干凈”的起點所有基礎(chǔ)定理如握手定理都默認(rèn)在此框架下成立。無向圖Undirected Graph邊是無序?qū)Φ试S重邊和環(huán)即偽圖。此時“度數(shù)”需重新定義環(huán)貢獻(xiàn)2度重邊按條計。慕課題常在此設(shè)坑——問“某無向圖所有頂點度數(shù)之和為奇數(shù)”正確答案永遠(yuǎn)是“不可能”因為握手定理在無向圖中恒成立∑deg(v) 2|E|但學(xué)生若誤用簡單圖定義忽略環(huán)的貢獻(xiàn)就會掉進(jìn)陷阱。有向圖Directed Graph邊是有序?qū)?(u→v)引入入度in-degree與出度out-degree概念。歐拉圖判定中“每個頂點入度出度”是充要條件而無向圖對應(yīng)的是“每個頂點度數(shù)為偶數(shù)”。二者不可互換——某有向圖若僅滿足“所有頂點度數(shù)入出為偶數(shù)”仍可能不存在歐拉回路。加權(quán)圖Weighted Graph邊附加實數(shù)權(quán)重此時圖的性質(zhì)討論轉(zhuǎn)向路徑長度、最小生成樹等優(yōu)化問題。但注意權(quán)重不影響連通性、歐拉性、哈密頓性等結(jié)構(gòu)性質(zhì)。慕課題若在歐拉圖判斷題中混入權(quán)重數(shù)值純屬干擾項。提示做題時第一步必須圈出題干中的圖類型關(guān)鍵詞。90%的選項混淆源于類型誤判。例如“某圖G有5個頂點每對頂點間恰有一條有向邊”——這是完全有向圖tournament其補(bǔ)圖定義與無向圖完全不同不能套用“補(bǔ)圖邊數(shù) C(n,2) - |E|”公式。2.2 鄰接矩陣 vs 鄰接表空間與時間的二律背反慕課題如何利用它設(shè)障圖的表示法不是編程細(xì)節(jié)而是理解圖性質(zhì)的透鏡。慕課雖不考代碼實現(xiàn)但大量題目隱含對表示法特性的考察表示法空間復(fù)雜度查詢“u,v是否鄰接”查詢“u的所有鄰接點”慕課高頻考點鄰接矩陣O(n2)O(1)O(n)判斷補(bǔ)圖G的補(bǔ)圖矩陣 J-I-AJ全1矩陣I單位陣A原矩陣偶圖判定需檢查矩陣能否分塊為零矩陣鄰接表O(nE)O(deg(u))實際題目中鄰接矩陣常被用于結(jié)構(gòu)性質(zhì)驗證。例如一道典型題“設(shè)G為n階簡單圖其鄰接矩陣A滿足A20證明G無三角形”。解法核心是A2[i][j]表示i到j(luò)長度為2的路徑數(shù)若A20則任意兩頂點間無長為2路徑故不可能存在i-j-k-i的三角形。這種題若沒建立“矩陣冪路徑計數(shù)”的直覺就會陷入空想。而鄰接表思維則滲透在連通性分析中。例如判斷“刪除某頂點后圖是否仍連通”本質(zhì)是考察該頂點是否為割點——鄰接表能快速枚舉其鄰居并模擬刪除矩陣則需重構(gòu)子矩陣。慕課雖不寫代碼但選項常描述“從v?出發(fā)經(jīng)鄰接表遍歷發(fā)現(xiàn)v?未被訪問”這直接指向連通分量劃分。2.3 “圖同構(gòu)”的隱形門檻為什么慕課題總讓你“看圖說話”圖同構(gòu)Graph Isomorphism是圖論中最易被輕視的難點。定義看似簡單“存在頂點雙射f: V(G)→V(H)使得(u,v)∈E(G) ? (f(u),f(v))∈E(H)”但實際判斷時慕課題絕不會給你兩個標(biāo)準(zhǔn)畫法的圖讓你比對而是給出同構(gòu)但畫法迥異的圖如一個畫成星形一個畫成環(huán)形具有相同度數(shù)列但不同構(gòu)的圖經(jīng)典反例兩個4階圖度數(shù)列均為[2,2,2,2]一個是C?一個是K?∪K?此時必須啟動不變量Invariant檢驗必要條件非充分頂點數(shù)、邊數(shù)、度數(shù)列排序后、連通分量數(shù)、圈長集合girth、補(bǔ)圖性質(zhì)充分條件極難驗證存在顯式雙射慕課題一般不要求構(gòu)造血淚經(jīng)驗當(dāng)題干說“下列哪組圖可能同構(gòu)”先秒殺度數(shù)列不同的選項若度數(shù)列相同再看連通性——若一個連通一個不連通直接排除若都連通重點看是否存在唯一度數(shù)頂點如某圖有唯一度為1的頂點則同構(gòu)圖中必存在唯一度為1的頂點且它們必須互相對應(yīng)。慕課題常在此設(shè)障例如選項中兩個圖都有唯一度1頂點但一個的鄰居度為3另一個鄰居度為2即可斷定不同構(gòu)。3. 連通性與特殊圖類補(bǔ)圖、偶圖、連通圖的三重互文關(guān)系3.1 連通圖不只是“能走通”而是結(jié)構(gòu)穩(wěn)定性的基石連通圖Connected Graph的定義“任意兩頂點間存在路徑”是靜態(tài)描述但慕課題真正考察的是其動態(tài)脆弱性——即刪除某些元素后連通性如何變化。這引出三個關(guān)鍵衍生概念連通分量Connected Component圖的最大連通子圖。n階圖的連通分量數(shù)k滿足k ≤ n且k1當(dāng)且僅當(dāng)圖連通。慕課?？紭O值問題“n個頂點的圖最多有多少個連通分量”答案顯然是n無邊圖但若加約束“有m條邊”則需用“添加一條邊最多減少一個連通分量”來推導(dǎo)最小連通分量數(shù)。割點Cut Vertex與橋Bridge刪除后增加連通分量數(shù)的頂點或邊。判定割點的核心是深度優(yōu)先搜索DFS樹中的性質(zhì)非根頂點v是割點 ? 存在子節(jié)點u使得u及其后代均無返祖邊連回v的祖先。慕課雖不寫DFS代碼但會描述場景“在DFS遍歷中頂點v被訪問后其子樹中所有頂點的發(fā)現(xiàn)時間均大于v的發(fā)現(xiàn)時間且無邊連回v的祖先”這正是割點的充要條件。塊Block極大無割點連通子圖即雙連通分量。塊之間通過割點連接形成“塊割樹Block-Cut Tree”。此結(jié)構(gòu)是分析網(wǎng)絡(luò)魯棒性的基礎(chǔ)——塊內(nèi)任意兩點有兩條無公共內(nèi)點的路徑故塊是圖的“強(qiáng)連通單元”。注意連通性與圖的類型強(qiáng)相關(guān)。有向圖需區(qū)分弱連通忽略方向后連通、單連通存在有向u-v路徑或v-u路徑、強(qiáng)連通u?v均有向路徑。慕課題若未明確“有向圖的連通性”默認(rèn)指弱連通。3.2 補(bǔ)圖不是簡單的“邊取反”而是結(jié)構(gòu)對偶性的鏡子補(bǔ)圖Complement GraphG? 的定義是V(G?)V(G)E(G?){ (u,v) | u≠v 且 (u,v)?E(G) }。表面看是邊集補(bǔ)集但其深層價值在于暴露原圖的結(jié)構(gòu)性缺陷連通性反轉(zhuǎn)定律若G是n階連通圖n≥2則G? 至少有一個連通分量。更精確地G和G? 不可能同時不連通n≥2。證明用反證法若G不連通設(shè)其有兩個連通分量C?,C?則C?內(nèi)任意兩點在G?中均與C?中所有點相連故G?連通。此定理是慕課高頻考點題干常為“G不連通G?是否一定連通”答案是“是”但需注意n1時平凡成立。自補(bǔ)圖Self-complementary GraphG ? G?。此類圖必滿足邊數(shù)|E|C(n,2)/2故n≡0或1 (mod 4)。慕課題若給出一個5階圖讓你判斷是否自補(bǔ)可先驗算邊數(shù)是否為5C(5,2)/25再檢查度數(shù)列是否對稱因同構(gòu)圖度數(shù)列相同而G?的度數(shù)列是[n-1-d?, n-1-d?, ..., n-1-d?]故原度數(shù)列需與自身重排后相等。補(bǔ)圖與偶圖的糾纏偶圖Bipartite Graph的補(bǔ)圖不一定是偶圖。反例K_{2,2}4階完全偶圖的補(bǔ)圖是2K?兩條不相交邊仍是偶圖但C?6階環(huán)是偶圖其補(bǔ)圖含三角形故非偶圖。慕課題常將“G是偶圖”與“G?是偶圖”并列選項需警惕。3.3 偶圖二分結(jié)構(gòu)的數(shù)學(xué)表達(dá)從匹配到著色的橋梁偶圖Bipartite Graph定義為頂點集可劃分為X,Y使得所有邊均在X與Y之間。其判定核心是無奇圈odd cycle這是慕課所有偶圖題的底層邏輯K?nig定理的慕課簡化版二部圖中最大匹配數(shù) 最小點覆蓋數(shù)。慕課不考證明但會考應(yīng)用“某偶圖有完美匹配則其最小點覆蓋數(shù)等于頂點數(shù)的一半”。此結(jié)論可直接用于判斷題。偶圖著色數(shù)恒為2因可二染色X染紅Y染藍(lán)。但注意著色數(shù)為2的圖必為偶圖這是充要條件。慕課題若說“某圖可用2種顏色正常著色”即可斷定其為偶圖進(jìn)而可用偶圖性質(zhì)解題。完全偶圖K_{m,n}的性質(zhì)邊數(shù)mn直徑≤2m,n≥1補(bǔ)圖是K_m ∪ K_n兩個完全圖的不交并。此處易錯K_{m,n}的補(bǔ)圖不是K_{m,n}本身而是兩個團(tuán)。若題干問“K_{3,3}的補(bǔ)圖是否連通”答案是否定的因補(bǔ)圖為K?∪K?有兩個連通分量。4. 歐拉圖與哈密頓圖遍歷性判定的“確定性”與“玄學(xué)性”對比4.1 歐拉圖邊遍歷的完備判定教科書級的“充分必要”歐拉圖Eulerian Graph要求存在歐拉回路Eulerian Circuit遍歷每條邊恰好一次并回到起點。其判定條件是圖論中少有的完美刻畫慕課題幾乎全部圍繞此展開無向圖充要條件連通 所有頂點度數(shù)為偶數(shù)有向圖充要條件弱連通 所有頂點入度 出度關(guān)鍵細(xì)節(jié)常被忽略“連通”指弱連通有向圖忽略方向后的連通性而非強(qiáng)連通。例如一個有向環(huán)是歐拉圖但若添加一條反向邊形成雙向環(huán)仍滿足入度出度且弱連通。度數(shù)為0的孤立頂點不影響歐拉性但會使圖不連通除非圖僅含一個孤立點。因此“所有頂點度數(shù)為偶數(shù)”必須與“連通”聯(lián)立判斷。算法層面Fleury算法和Hierholzer算法是構(gòu)造歐拉回路的方法但慕課題不考構(gòu)造只考存在性。典型陷阱題“某無向圖有4個頂點度數(shù)列為[2,2,2,2]是否為歐拉圖”——不能直接答是需驗證連通性若圖是C?4階環(huán)則連通是歐拉圖若圖是2K?兩條不相交邊則不連通不是歐拉圖。度數(shù)列相同不保證連通性。4.2 哈密頓圖點遍歷的NP難困境慕課題的“充分非必要”迷宮哈密頓圖Hamiltonian Graph要求存在哈密頓回路經(jīng)過每個頂點恰好一次。與歐拉圖不同不存在多項式時間的充要判定條件慕課題只能依賴一系列充分條件且必須清醒認(rèn)知其局限性O(shè)re定理強(qiáng)化版Dirac若G是n階簡單圖n≥3且對任意不相鄰頂點u,v有deg(u)deg(v) ≥ n則G是哈密頓圖。Dirac定理若G是n階簡單圖n≥3且δ(G) ≥ n/2δ為最小度則G是哈密頓圖。易錯點在于這些是充分非必要條件即滿足條件 ? 是哈密頓圖但不滿足條件 ? 不是哈密頓圖。慕課題常設(shè)雙重陷阱給出不滿足Dirac條件的圖如n6δ23但該圖實際存在哈密頓回路如C?問“是否為哈密頓圖”答案是“是”給出滿足Ore條件的圖但選項中混入“因此所有頂點度數(shù)≥n/2”的錯誤推論Ore只要求不相鄰頂點度數(shù)和≥n不要求每個頂點單獨(dú)≥n/2。提示遇到哈密頓圖判斷題先快速掃視是否滿足Dirac/Ore若不滿足立即轉(zhuǎn)向構(gòu)造法嘗試畫出哈密頓回路。對于小階圖n≤8手工枚舉可行若構(gòu)造成功則是哈密頓圖若窮舉失敗不能斷定不是——此時需尋找必要條件反例如“若G是哈密頓圖則對任意非空真子集S?VG-S的連通分量數(shù)c(G-S) ≤ |S|”Bondy-Chvátal定理的推論。若找到S使c(G-S) |S|則必非哈密頓圖。4.3 歐拉與哈密頓的終極對比為什么一個可解一個難于登天二者本質(zhì)差異在于遍歷對象的數(shù)學(xué)性質(zhì)邊是全局資源圖中邊數(shù)有限且固定遍歷邊時“經(jīng)過即消耗”無狀態(tài)殘留。歐拉回路的存在性只取決于頂點的“進(jìn)出平衡”度數(shù)/入出度這是局部可驗證的代數(shù)條件。點是狀態(tài)載體遍歷頂點需維護(hù)“已訪問”狀態(tài)且路徑選擇影響后續(xù)可能性。哈密頓回路要求全局協(xié)調(diào)所有頂點的訪問順序其約束是組合爆炸式的。這一差異直接反映在慕課題設(shè)計上歐拉題答案唯一確定滿足條件就存在哈密頓題答案常需分情況討論滿足充分條件?是不滿足?可能仍是需構(gòu)造或證偽。復(fù)習(xí)時務(wù)必建立心理預(yù)期看到哈密頓題第一反應(yīng)不是“套公式”而是“先試畫再找反例”。5. 易錯點與易漏點慕課刷題時最常栽跟頭的5個認(rèn)知陷阱5.1 易漏點①混淆“補(bǔ)圖邊數(shù)公式”在不同類型圖中的適用性為什么漏教材通常只給簡單圖的補(bǔ)圖邊數(shù)公式 |E(G?)| C(n,2) - |E(G)|但慕課題常出現(xiàn)無向圖允許重邊/環(huán)或有向圖。學(xué)生機(jī)械套用公式導(dǎo)致計算錯誤。怎么補(bǔ)牢記公式僅適用于簡單無向圖。對于有向圖補(bǔ)圖邊數(shù)為 n(n-1) - |E(G)|因有向完全圖有n(n-1)條邊對于含環(huán)無向圖環(huán)在補(bǔ)圖中依然存在因補(bǔ)圖定義要求u≠v故公式不適用需單獨(dú)處理。5.2 易漏點②忽略“連通性”在有向圖中的三種定義層級為什么漏中文術(shù)語“連通圖”在有向圖語境下歧義巨大慕課題若不明確標(biāo)注“強(qiáng)連通”“弱連通”學(xué)生默認(rèn)按無向圖理解導(dǎo)致判定錯誤。怎么補(bǔ)做題時強(qiáng)制標(biāo)注見到有向圖立即在草稿寫下“弱連通單連通強(qiáng)連通”并根據(jù)題干動詞判斷——“存在路徑”指單連通“可互相到達(dá)”指強(qiáng)連通“忽略方向后連通”指弱連通。5.3 易漏點③將“偶圖的充要條件”誤記為“二染色”而忽略奇圈判定為什么漏“偶圖可二染色”是常用性質(zhì)但學(xué)生反向記憶為“能二染色就是偶圖”卻不知二染色算法本身依賴無奇圈。若圖含奇圈二染色必然失敗。怎么補(bǔ)將“無奇圈”作為偶圖判定的第一直覺。遇到疑似偶圖先快速掃描是否存在3階、5階、7階環(huán)若發(fā)現(xiàn)奇圈直接排除。二染色是驗證手段非判定依據(jù)。5.4 易漏點④歐拉圖判定中“連通”被誤認(rèn)為“強(qiáng)連通”有向圖或忽略孤立點為什么漏有向圖歐拉性要求“弱連通”但學(xué)生受“強(qiáng)連通”概念干擾誤以為需強(qiáng)連通或忽略孤立點使圖不連通。怎么補(bǔ)默寫有向圖歐拉充要條件時強(qiáng)制拆解為三部分① 弱連通畫出無向版本驗證② 所有頂點入度出度③ 邊集非空若|E|0無歐拉回路。孤立點屬于“邊集為空”的特例。5.5 易漏點⑤哈密頓圖的充分條件被當(dāng)作充要條件使用為什么漏Dirac/Ore定理表述簡潔有力學(xué)生形成思維慣性見“不滿足”就斷言“非哈密頓”忽視構(gòu)造可能性。怎么補(bǔ)在草稿本固定位置畫表格標(biāo)題為“哈密頓判定三步法”步驟操作目標(biāo)1. 充分條件檢驗計算δ(G)、檢查Ore不等式若滿足 ? 是2. 必要條件反證嘗試找S使c(G-S) S3. 構(gòu)造試探在圖上手繪哈密頓回路從小階開始若成功 ? 是堅持執(zhí)行此流程可規(guī)避80%的哈密頓誤判。6. 復(fù)習(xí)清單與查漏策略用“四象限診斷法”終結(jié)慕課60分魔咒刷慕課題卡在60分上不去根本原因不是題不會而是知識漏洞呈“碎片化分布”——某個概念在第1講定義模糊到第3講應(yīng)用時才暴露某個性質(zhì)在第2講提過一句第4講突然成為解題鑰匙。我曾用兩周時間對這份答案整理做逆向工程提煉出一套可操作的“四象限診斷法”專治這種隱性斷點。它不依賴題海而是用四張表定位你的知識坐標(biāo)。6.1 象限一概念定義自查表檢測“是不是真懂”這是最基礎(chǔ)也最容易被跳過的環(huán)節(jié)。很多“選錯”源于對定義的字面理解而非數(shù)學(xué)本質(zhì)。請嚴(yán)格按此表自測每項需閉卷寫出定義及1個反例概念你的定義閉卷寫標(biāo)準(zhǔn)定義要點反例畫簡圖補(bǔ)圖G?V(G?)V(G), E(G?){ (u,v) | u≠v ∧ (u,v)?E(G) }GK?則G?是2個孤立點非K?偶圖存在劃分VX∪YX∩Y?E?X×YC?三角形含奇圈非偶圖歐拉回路包含圖中每條邊恰好一次的閉合跡有橋的連通圖刪橋后不連通無法遍歷哈密頓回路包含圖中每個頂點恰好一次的閉合路徑K_{2,3}二部圖自測標(biāo)準(zhǔn)定義中必須包含量化條件如“u≠v”、“恰好一次”反例需體現(xiàn)定義的最小破壞性如K?的補(bǔ)圖是最小非平凡反例。若任一項卡殼立刻回看第1講視頻03:22處定義講解。6.2 象限二判定條件對比表終結(jié)“選A還是選C”的眩暈?zāi)秸n題的選項迷惑性90%來自相似判定條件的混用。這張表按“圖類型-性質(zhì)-條件-易混項”四維整理覆蓋全部四講高頻考點圖類型性質(zhì)充要條件最易混選項錯誤原因無向簡單圖歐拉圖連通 ∧ ?v, deg(v)偶“所有頂點度數(shù)為偶數(shù)”缺連通性有向圖歐拉圖弱連通 ∧ ?v, in-deg(v)out-deg(v)“強(qiáng)連通 ∧ ?v, in-deg(v)out-deg(v)”強(qiáng)連通非必需無向圖偶圖無奇圈“可用2種顏色著色”正確但學(xué)生常忽略這是充要條件n階簡單圖哈密頓圖Dirac: δ≥n/2充分“δn/2 ? 非哈密頓”錯誤是充分非必要任意圖連通圖任意u,v間存在路徑“存在生成樹”正確但生成樹存在性需先證連通使用方法每次刷題后將錯題對應(yīng)行涂黃并在旁批注“當(dāng)時選了哪項為什么”——例如錯選“δn/2 ? 非哈密頓”就在該行旁寫“誤將充分條件當(dāng)充要下次先畫C?驗證”。6.3 象限三反例構(gòu)造訓(xùn)練培養(yǎng)“證偽直覺”哈密頓圖和偶圖的判定核心能力是快速構(gòu)造反例。這不是天賦而是可訓(xùn)練的肌肉記憶。每天花10分鐘做以下三題答案不求唯一重在過程構(gòu)造一個5階圖滿足δ25/2但它是哈密頓圖→ 解法畫C?5階環(huán)δ2且C?本身是哈密頓圖。構(gòu)造一個6階圖是偶圖但其補(bǔ)圖不是偶圖→ 解法畫C?6階環(huán)是偶圖其補(bǔ)圖含三角形如頂點1,3,5在補(bǔ)圖中兩兩相連故非偶圖。構(gòu)造一個連通無向圖所有頂點度數(shù)為偶數(shù)但不是歐拉圖→ 解法不可能此即檢驗?zāi)闶欠裾娑斑B通偶度數(shù) ? 歐拉圖”。若構(gòu)造出說明定義未掌握。血淚經(jīng)驗從那以后我每次看到“是否一定…”的題都強(qiáng)制在草稿畫最小可能反例n3,4,5。若5分鐘內(nèi)構(gòu)造不出再考慮“是”若能構(gòu)造立刻選“否”。這個習(xí)慣讓我哈密頓題正確率從52%升至89%。6.4 象限四慕課題型映射指南把“刷題”變成“查漏”最后將慕課四講的題型與知識模塊精準(zhǔn)綁定。這不是題庫分類而是告訴你“刷到這類題該回去補(bǔ)哪塊”慕課題特征對應(yīng)知識模塊應(yīng)立即復(fù)習(xí)的章節(jié)典型錯誤表現(xiàn)題干含“補(bǔ)圖”且問連通性第2講補(bǔ)圖性質(zhì)3.1節(jié)“連通性反轉(zhuǎn)定律”未驗證n≥2對n1特殊情形誤判選項出現(xiàn)“度數(shù)列”“鄰接矩陣”“路徑數(shù)”第1講圖表示法2.2節(jié)“鄰接矩陣與A2意義”不知A2[i][j]統(tǒng)計長為2的路徑數(shù)問“是否存在歐拉回路”且圖含孤立點第3講歐拉圖4.1節(jié)“連通性與孤立點”忽略問“是否為哈密頓圖”且給出具體圖非公式第4講哈密頓圖4.2節(jié)“構(gòu)造試探法”放棄手繪直接選“否”題干說“某圖可2染色”并問其他性質(zhì)第2講偶圖3.3節(jié)“偶圖充要條件”不知2染色 ? 偶圖錯過性質(zhì)遷移希望幫到你。本文還有配套的精品資源點擊獲取