歐美韓國(guó)國(guó)貨護(hù)膚彩妝精油藥妝禮品。。-展示頁(yè)
2025-02-11 15:10本頁(yè)面
【正文】 終點(diǎn)才可能成為奇次頂點(diǎn)，而一個(gè)奇次頂點(diǎn)是不可能的，當(dāng)無(wú)奇次頂點(diǎn)時(shí)，是歐拉回路。3/8/2023 3Deren Chen, Zhejiang Univ.Graphs/圖論圖論[定理 1]（歐拉定理）： 沒(méi)有次為０的孤立頂點(diǎn)的無(wú)向圖存在歐拉道路的充要條件是： (1)圖是連通的； (2)圖中奇次頂點(diǎn)個(gè)數(shù)是０個(gè)或 2個(gè)。將河岸和小島作為圖的頂點(diǎn)，七座橋?yàn)檫?，?gòu)成一個(gè)無(wú)向重圖，問(wèn)題化為圖論中簡(jiǎn)單道路的問(wèn)題：[定義 ]歐拉道路（回路）： Ｇ＝（Ｖ，Ｅ），稱包含Ｅ中所有邊的簡(jiǎn)單道路為 歐拉道路 /Euler Path/E道路 。Graphs/ 圖的概念 /Introduction of Graph 圖的術(shù)語(yǔ) /Graph Terminology 圖的表示與同構(gòu) / Representing Graph and Graph Isomorphism 連通性 /Connectivity 歐拉道路與哈密爾頓道路 / Euler and Hamilton Paths 最短道路問(wèn)題 /Shortest Path Problem 平面圖 /Planar Graphs 圖的著色 /Graph Coloring3/8/2023 1Deren Chen, Zhejiang Univ.Graphs/圖論圖論 Euler and Hamilton PathKonigsberg(哥尼斯堡 )七橋問(wèn)題問(wèn)題：能否從河岸或小島出發(fā)，通過(guò)每一座橋，而且僅僅通過(guò)一次回到原地。3/8/2023 2Deren Chen, Zhejiang Univ.Graphs/圖論圖論 Euler(歐拉 )1736年對(duì)這個(gè)問(wèn)題，給出了否定的回答。 包含Ｅ中所有邊的簡(jiǎn)單回路為 歐拉回路/Euler Circuit/E回路。3/8/2023 4Deren Chen, Zhejiang Univ.Graphs/圖論圖論證明： 必要性： 若存在歐拉道路，且沒(méi)有０次頂點(diǎn)，則每個(gè)頂點(diǎn)都有邊關(guān)聯(lián)，而邊又全在歐拉道路上，故所有頂點(diǎn)都連通。充分性： 若 (1）， (2)成立 ,構(gòu)造歐拉道路 .3/8/2023 5Deren Chen, Zhejiang Univ.Graphs/圖論圖論 若圖Ｇ存在奇次頂點(diǎn)，任取一個(gè)作為起點(diǎn)，若不存在，則任取一個(gè)頂點(diǎn)作為起點(diǎn)。每進(jìn)入或離開一個(gè)頂點(diǎn)，讓此頂點(diǎn)的次減１，由于除了兩個(gè)（或沒(méi)有）奇次頂點(diǎn)外，其余頂點(diǎn)次為偶數(shù)，只要進(jìn)得去，一定出得來(lái)，直至進(jìn)入另一個(gè)奇次頂點(diǎn)（或起點(diǎn)）作為終點(diǎn)。 不然，記走過(guò)的簡(jiǎn)單道路為ｐ 1，ｐ 1上頂點(diǎn)集Ｖ 1，邊集Ｅ 1，Ｇ
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1