正文之前
本次我們要介紹與歐拉圖相對應(yīng)的哈密頓圖的有關(guān)內(nèi)容：
- 哈密頓回路(Hamiltonian cycle)
- 哈密頓圖(Hamiltonian Path)
- 旅行推銷員問題簡介(Travelling salesman problem)
正文
哈密頓回路
1. 定義：
在一個回路中熊楼，除了經(jīng)過初始結(jié)點兩次以外霹娄，恰好經(jīng)過每個結(jié)點一次，則稱此回路為哈密頓回路孙蒙，哈密頓回路中每個結(jié)點都為偶結(jié)點
2. 證明
- 由于現(xiàn)在還沒有判斷一個圖中是否存在哈密頓回路的定理项棠，所以我們只能根據(jù)自己的經(jīng)驗來判斷，下文分別以一個簡單的圖和一個復(fù)雜的圖來證明
簡單的圖
在上圖中挎峦，共有5個結(jié)點香追，可想而知，如果存在哈密頓回路坦胶，就必須有5條邊透典，且每個結(jié)點都為偶結(jié)點。
所以我們嘗試刪去某一些邊來達到目的顿苇，v1和v3為奇結(jié)點峭咒，我們從此下手，分別去掉一條與v1和v3相關(guān)聯(lián)的邊纪岁，那么只剩下4條邊凑队，不符合條件，所以此圖中不存在哈密頓回路幔翰。
復(fù)雜的圖
在上圖中漩氨，假設(shè)有一個哈密頓回路，由于v1和v3是度數(shù)為2的結(jié)點遗增，所以v1和v3所關(guān)聯(lián)的邊(v1,v8)叫惊、(v1,v2)、(v2,v3)做修、(v3,v4)一定在回路中霍狰。
結(jié)點v2，v7饰及，v5度數(shù)不為2蔗坯，所以我們刪去邊(v2,v7)和(v2,v5)
結(jié)點v5，v6燎含，v7的度數(shù)為2步悠，所以現(xiàn)在形成了一個回路(v1,v2,v3,v4,v5,v6,v7,v8)
圖中還存在結(jié)點v9，將v9加入回路中就勢必會增加某些點的度數(shù)瘫镇，所以使得某些點的度數(shù)大于2
通過上述幾點鼎兽，可得出上圖中不存在哈密頓回路
哈密頓圖
定義：在圖G中，若含有哈密頓回路铣除，則稱圖G為哈密頓圖
- 上圖中谚咬，存在哈密頓回路(v1,v2,v5,v3,v4,v1)，所以上圖可稱為哈密頓圖
旅行推銷員問題簡介
問題內(nèi)容
給定一系列城市和每對城市之間的距離尚粘，求解訪問每一座城市一次并回到起始城市的最短回路择卦。?????????????——Wikipedia
這個問題是基于尋找哈密頓回路的基礎(chǔ)上，只不過所對應(yīng)的圖是加權(quán)無向圖郎嫁，在接下來秉继。
這一篇的內(nèi)容就到此為止了，接下來會有一篇文章專門介紹旅行推銷員問題問題泽铛，謝謝大家尚辑！
