歐美韓國國貨護(hù)膚彩妝精油藥妝禮品。。(編輯修改稿)
2025-02-23 15:10 本頁面
【文章內(nèi)容簡介】 不可能有歐拉道路。應(yīng)用與推廣： （ 1） 一筆畫問題； （ 2） 如果齊次頂點(diǎn)個(gè)數(shù)為 2K個(gè)，此問題是 K筆畫問題。 3/8/2023 11Deren Chen, Zhejiang Univ.Graphs/圖論圖論例８個(gè)頂點(diǎn)均為3次，至少要４筆。3/8/2023 12Deren Chen, Zhejiang Univ.Graphs/圖論圖論[推論 ]（歐拉定理）： 沒有次為０的孤立頂點(diǎn)的無向圖存在歐拉回路的充要條件是： (1)圖是連通的； (2)圖中沒有奇次頂點(diǎn)。3/8/2023 13Deren Chen, Zhejiang Univ.Graphs/圖論圖論定理 2（有向圖的歐拉定理）： 不含 出 /入 次為０的孤立頂點(diǎn)的有向圖具有歐拉道路的充要條件是：(1）弱連通；(2) 除了可能有２個(gè)頂點(diǎn)，一個(gè)入次比出次大１，一個(gè)出次比入次大１，其余頂點(diǎn)出次等于入次。推論不含出 /入次為０的孤立頂點(diǎn)的有向圖具有歐拉回路的充要條件是：（ 1）弱連通；（ 2）所有頂點(diǎn)出次等于入次。3/8/2023 14Deren Chen, Zhejiang Univ.Graphs/圖論圖論Hamilton(哈密頓 )道路問題： １８５９年發(fā)明的一種游戲。 在一個(gè)實(shí)心的正十二面體， 20個(gè)頂點(diǎn)標(biāo)上世界著名大城市的名字，要求游戲者從某一城市出發(fā)，遍歷各城市一次，最后回到原地。 這就是 “ 繞行世界 ” 問題。即 找一條經(jīng)過所有頂點(diǎn)（城市）的基本道路（回路）。3/8/2023 15Deren Chen, Zhejiang Univ.Graphs/圖論圖論[定義 ]哈密頓道路 /回路： Ｇ＝（Ｖ，Ｅ）， G中經(jīng)過Ｖ中所有頂點(diǎn)的基本道路稱為 哈密頓道路 /Hamilton Path，簡稱 Ｈ道路 。 Ｇ＝（Ｖ，Ｅ）， G中經(jīng)過Ｖ中所有頂點(diǎn)的基本回路稱為 哈密頓回路 /Hamilton Circuit，簡稱 Ｈ回路 。3/8/2023 16Deren Chen, Zhejiang Univ.Graphs/圖論圖論圖Ａ 每個(gè)頂點(diǎn)都是奇次的，不存在歐拉道路，但有Ｈ道路。 圖Ｂ存在歐拉道路，不存在Ｈ道路。3/8/2023 17Deren Chen, Zhejiang Univ.Graphs/圖論圖論[定理 3]：設(shè)Ｇ＝（Ｖ，Ｅ）是ｎ個(gè)頂點(diǎn)的簡單圖，如果任何一對(duì)頂點(diǎn)的次之和 ≥ｎ－１，則Ｇ中一定有Ｈ道路（ n=2）。證明： Ｇ一定連通，否則Ｇ分為二個(gè)不連通的分圖Ｇ 1，Ｇ 2，其中Ｇ 1有ｎ 1個(gè)頂點(diǎn)，Ｇ 2有ｎ 2個(gè)頂點(diǎn)，Ｇ 1中每個(gè)頂點(diǎn)次 ≤ ｎ 1－
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1