第10章廣義匹配-資料下載頁(yè)
2025-07-20 06:42本頁(yè)面
【正文】 ：連接頂點(diǎn)的直線(xiàn)或曲線(xiàn) ? 邊數(shù)大于等于 1的圖可有無(wú)窮多個(gè)幾何表達(dá) V(G) = {A, B, C} E(G) = {a, b, c, d} 邊 a， b， c均為棱 邊 d為環(huán) 邊 a和 b為重邊 第 32頁(yè) 第 9講 章毓晉 (THEEIE) 圖論簡(jiǎn)介 2. 圖的幾何表達(dá) ? 有色圖表達(dá)示例 頂點(diǎn)色性用 頂 點(diǎn)形狀區(qū)別 連線(xiàn)色性用連線(xiàn)線(xiàn)型區(qū)別 B C連接關(guān)系A(chǔ)上下關(guān)系左右關(guān)系14元件類(lèi)型1元件類(lèi)型2元件類(lèi)型3 2 3第 33頁(yè) 第 9講 章毓晉 (THEEIE) 圖論簡(jiǎn)介 3. 子圖 ? 子圖 H ? G ： V(H) ? V(G)， E(H) ? E(G) ? 生成子圖： H ? G 且 V(H) = V(G) ? 去掉所有重邊和環(huán)而得到的簡(jiǎn)單生成子圖稱(chēng) 為基礎(chǔ)簡(jiǎn)單圖（僅 (d)） 第 34頁(yè) 第 9講 章毓晉 (THEEIE) 圖同構(gòu)和匹配 1. 圖的恒等和同構(gòu) ? 圖 G和 H恒等： V(G) = V(H)， E(G) = E(H) ? 恒等的圖可用相同的幾何表達(dá)來(lái)表示 ? 用相同幾何表達(dá)來(lái)表示的并不一定恒等 第 35頁(yè) 第 9講 章毓晉 (THEEIE) 圖同構(gòu)和匹配 1. 圖的恒等和同構(gòu) ? 圖 G和 H同構(gòu)：記為 G ? H ? 在 V(G)和 V(H)， E(G)和 E(H)之間有如下映射 P和 Q相關(guān)聯(lián) Q(e) = P(u)P(v)， ?e = uv ? E(G) )()(: HVGVP ?)()(: HEGEQ ?第 36頁(yè) 第 9講 章毓晉 (THEEIE) 圖同構(gòu)和匹配 2. 同構(gòu)的判定 (1) 全圖同構(gòu)： (a) ? (b) (2) 子圖同構(gòu)： (a) ? (c) (3) 雙子圖同構(gòu)： (a) ? (d) 第 37頁(yè) 第 9講 章毓晉 (THEEIE) 線(xiàn)條圖標(biāo)記 1. 輪廓標(biāo)記 (1) 刃邊（ blade） (2) 翼邊（ limb） (3) 折痕（ crease） (4) 痕跡（ mark） (5) 陰影（ shade） 第 38頁(yè) 第 9講 章毓晉 (THEEIE) 線(xiàn)條圖標(biāo)記 2. 結(jié)構(gòu)推理 借助 2D圖象中的輪廓結(jié)構(gòu)來(lái)對(duì) 3D目標(biāo)的結(jié)構(gòu)進(jìn)行推理分析 第 39頁(yè) 第 9講 章毓晉 (THEEIE) 線(xiàn)條圖標(biāo)記 2. 結(jié)構(gòu)推理 四類(lèi) 16種邊線(xiàn)連接的（拓?fù)洌┙M合類(lèi)型 第 40頁(yè) 第 9講 章毓晉 (THEEIE) 線(xiàn)條圖標(biāo)記 3. 回溯標(biāo)記 ? 自動(dòng)標(biāo)記線(xiàn)條圖的一種算法 ? 給 2D線(xiàn)條圖中的每條邊賦一個(gè)標(biāo)記 ? 將邊排成序列，以深度優(yōu)先的方式生成通路 ? 依次對(duì)每條邊進(jìn)行所有可能的標(biāo)記 ? 檢驗(yàn)新標(biāo)記與其他邊標(biāo)記的一致性 ? 得到一種標(biāo)記結(jié)果（得到一條到達(dá)樹(shù)葉的完 全通路） {例 } 第 41頁(yè) 第 9講 章毓晉 (THEEIE) ? 通信地址： 北京清華大學(xué)電子工程系 ? 郵政編碼： 100084 ? 辦公地址： 清華大學(xué)東主樓， 9區(qū) 307室 ? 辦公電話(huà) ： (010)62781430 ? 傳真號(hào)碼 ： (010)62770317 ? 電子郵件： ? 個(gè)人主頁(yè)： ~zhangyujin/ ? 實(shí)驗(yàn)室網(wǎng)： 聯(lián) 系 信 息
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1