色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發帖/加入社區
會員中心
創作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

如何判斷哈密頓圖_哈密頓圖的必要條件

ss ? 來源:網絡整理 ? 2018-02-01 15:43 ? 次閱讀

一、哈密頓圖定義概念

哈密頓通路(回路)與哈密頓圖(Hamilton圖)通過圖G的每個結點一次,且僅一次的通路(回路),就是哈密頓通路(回路)。存在哈密頓回路的圖就是哈密頓圖。

1.哈密頓通路

設G=《V,E》為一圖(無向圖或有向圖).G中經過每個頂點一次且僅一次的通路稱作哈密頓通路

2.哈密頓回路

G中經過每個頂點一次且僅一次的回路稱作哈密頓回路

3.哈密頓圖

若G中存在哈密頓回路,則稱它是哈密頓圖

4.定義詳解:

(1)存在哈密頓通路(回路)的圖一定是連通圖;

(2)哈密頓通路是初級通路,哈密頓回路是初級回路;

(3)若G中存在哈密頓回路,則它一定存在哈密頓通路,反之不真

(4)只有哈密頓通路,無哈密頓回路的圖不交哈密頓圖;

如何判斷哈密頓圖_哈密頓圖的必要條件

二、判斷條件

與歐拉圖的情形不同,到目前為止還未找到判斷一個圖是否是哈密頓圖的非平凡的充要條件。事實上這是圖論中尚未解決的主要問題之一。哈密頓圖有很多充分條件,例如,

(1)若圖的最小度不小于頂點數的一半,則圖是哈密頓圖;

(2)若圖中每一對不相鄰的頂點的度數之和不小于頂點數,則圖是哈密頓圖。

另外,還有很多用度序列、度和、圖的堅韌度等參數給出的充分條件。

三、哈密頓圖的充分條件和必要條件

定理1:設無向圖G是哈密頓圖,V1是V的任意的非空子集,則

p(G-V1)≤|V1|

其中,p(G-V1)為從G中刪除V1(刪除V1中各頂點及關聯的邊)后所得到的圖的連通分支,|V1|為V1集合中包含的頂點個數。【哈密頓圖存在的必要條件】

推論:有割點的圖一定不是哈密頓圖

設v是圖中的割點,則p(G-v)》=2,由上述定理知G不是哈密頓圖

(2)設G是n(n》=3)階無向簡單圖,若對于G中的每一對不相鄰的頂點u,v,均有

d(u)+d(v)》=n-1

則G中存在哈密頓通路。又若

d(u)+d(v)》=n

則G中存在哈密頓回路,即G為哈密頓圖。【哈密頓圖存在的充分條件】

其中d(u),d(v)分別代表頂點u,v的度數。

定理2:設G是n(n≥3)階無向簡單圖,如果G中任何一對不相鄰的頂點度數之和都大于等于n,則G是哈密頓圖。

推論:設G是n(n≥3)階無向簡單圖,如果G中任何一對不相鄰的頂點的度數之和都大于等于n,則G是哈密頓圖。

如何判斷哈密頓圖_哈密頓圖的必要條件

定理3:在n(n≥2)階有向圖D=中,如果所有有向邊均用無向邊代替,所得無向圖中含生成子圖Kn,則有向圖中存在哈密頓圖。

推論:n(n≥3)階有向完全圖為哈密頓圖。

哈密頓路徑也稱作哈密頓鏈,指在一個圖中沿邊訪問每個頂點恰好一次的路徑。尋找這樣的一個路徑是一個典型的NP-完全(NP-complete)問題。后來人們也證明了,找一條哈密頓路的近似比為常數的近似算法也是NP完全的。

四、如何判斷哈密頓圖

1.常用方法判斷是哈密頓圖:

(1)若能通過觀察找出圖G中的一條哈密頓回路,則G當然是哈密頓圖。

(2)若一個無向圖G滿足上述(2)中的條件,一個有向圖D滿足上述(3)的推論的條件,則G、D都是哈密頓圖。

2.破壞哈密頓圖存在的必要條件,判定不是哈密頓圖:

設n階圖G是哈密頓圖,則G應該滿足以下諸條件:

(1)G必須是連通圖;

(2)G中的邊數m必須大于等于頂點數n;

(3)若G中存在2度頂點v,即d(v)=2,則與v關聯的兩條邊ei,ej必須在G中的任何哈密頓回路上;

(4)若G中存在每條哈密頓回路中出現的邊,不能構成邊數小于n的初級回路(圈);

破壞以上諸條件中的一條,都不是哈密頓圖。

聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。 舉報投訴
  • 哈密頓圖
    +關注

    關注

    0

    文章

    3

    瀏覽量

    1291
收藏 人收藏

    評論

    相關推薦

    #硬聲創作季 2.2.1 哈密頓算子視頻

    電磁場物理量與定理
    Mr_haohao
    發布于 :2022年09月01日 20:56:14

    請問多態的必要條件是什么?

    什么是多態?多態的必要條件是什么?
    發表于 11-06 06:22

    DNA編碼的學習

    成熟,數學上很多NP-hard問題傳統計算機難以有效解決,1994年,Adleman教授用脫氧核糖核苷酸分子為計算介質,以現代分子生物技術為手段,解決了7個定點的有向哈密頓路。總結來說就是以生化反應來解決數
    發表于 07-23 06:05

    電子關聯對聚乙炔雙激子態的影響

    在SSH哈密頓基礎上,引進擴展的Hubbard關聯能,對聚乙炔的雙激子態進行自洽變分計算。發現:電子關聯的引入使雙激子吸收峰一分為二,這結果與光誘致吸收實驗觀察到的瞬時雙
    發表于 11-20 12:45 ?8次下載

    LaSrAlO4中Cu2+的自旋哈密頓參量的理論分析

    根據晶體場理論,利用3d9離子在四角對稱(伸長八面體)中自旋哈密頓參量g因子的四階微擾公式以及超精細結構常數A因子的三階微擾公式,對摻Cu2+的LaSrAlO4晶體的自旋哈密頓參量作
    發表于 05-10 12:11 ?24次下載

    ZigBee與哈密瓜不得不說的故事

    新疆哈密中蒙交界地區,ZigBee網絡用于哈密瓜田地自動化滴灌系統,應用區域超過4萬畝。看致遠電子工程師如何使用Zigbee分析儀為種植保駕護航。
    發表于 03-05 17:35 ?744次閱讀

    哈密頓結構修正的控制設計方法及其應用

    哈密頓結構修正的控制設計方法及其應用_曾云
    發表于 01-07 17:16 ?1次下載

    哈密頓回路的應用

    本文主要介紹了哈密頓回路的應用,哈密頓定義概念以及哈密頓的判定定理。哈密頓通路(回路)與
    的頭像 發表于 02-01 15:58 ?4306次閱讀
    <b class='flag-5'>哈密頓</b>回路的應用

    哈密頓回路算法

    本文主要介紹了哈密頓回路算法以及程序設計實現。哈密頓就是從一點出發,經過所有的必須且只能一次,最終回到起點的路徑。圖中有的邊可以不經過,但是不會有邊被經過兩次。設一個無向圖中有N個頂點,若所有頂點的度數大于等于N/2,則
    的頭像 發表于 02-01 16:11 ?9936次閱讀

    永磁同步直線電機位置控制

    針對永磁同步直線電機( PMLSM)的位置控制問題,從能量整型控制的角度進行了研究。基于哈密頓反饋耗散控制方法,結合系統的物理能量特性,在dq旋轉坐標系下建立了包含電能和動能的永磁同步直線電機閉環
    發表于 03-01 14:00 ?12次下載
    永磁同步直線電機位置控制

    模擬量子計算的未來前景將一片光明

    模擬量子計算(analog quantum computing),相對于通用量子計算,有更平易近人的物理實現方式,而且對于玻色采樣、搜索、哈密頓量學習、化學模擬等問題上有明顯的天然對應方式和加速優勢,因此是目前量子信息發展的另一個不可或缺、至關重要的領域。
    發表于 10-18 15:34 ?1163次閱讀

    模擬量子計算有著優異的表現,未來將具有廣泛的應用前景

    模擬量子計算(analog quantum computing),相對于通用量子計算,有更平易近人的物理實現方式,而且對于玻色采樣、搜索、哈密頓量學習、化學模擬等問題上有明顯的天然對應方式和加速優勢,因此是目前量子信息發展的另一個不可或缺、至關重要的領域。
    發表于 11-25 11:35 ?904次閱讀

    模擬量子計算的實力前景不可限量

    模擬量子計算(analog quantum computing),相對于通用量子計算,有更平易近人的物理實現方式,而且對于玻色采樣、搜索、哈密頓量學習、化學模擬等問題上有明顯的天然對應方式和加速優勢。
    發表于 12-12 15:18 ?766次閱讀

    基于量子軟件的量子絕熱近似算法求解

    經典近似算法求解最大割問題時,時間復雜度與的復雜度呈正相關。為提高求解效率,使用量子絕熱近似算法求解無向最大割問題哈密頓量的基態,其基態對應該問題的最優解。該算法的時間復雜度不依賴于
    發表于 05-12 14:28 ?8次下載

    基于高光譜的不同成熟期哈密瓜堅實度研究

    哈密瓜是新疆的特色水果,目前,哈密瓜品種繁多,采收時,不同品種的成熟期不同,在成熟時的表現也不同,因此,簡單地通過外表來分辨哈密瓜的成熟度,會造成判別不一致,影響哈密瓜的貨架期,從而
    的頭像 發表于 03-12 15:41 ?405次閱讀
    基于高光譜的不同成熟期<b class='flag-5'>哈密</b>瓜堅實度研究
    主站蜘蛛池模板: 嫩草成人影院| 中文字幕不卡在线视频| 色欲久久精品AV无码| 一本道高清码| 国产盗摄一区二区三区| 美女裸露100%奶头视频| 亚洲AV无码乱码在线观看浪潮 | 免费成人小视频| 耽肉高h喷汁呻吟| 男人到天堂a在538线| 成人免费视频一区| 欧美日韩看看2015永久免费| 在线视频 中文字幕| 解开白丝老师的短裙猛烈进入| 上原结衣快播| 精品熟女少妇AV免费观看| 亚洲.欧美.中文字幕在线观看| 国产不卡一卡2卡三卡4卡网站| 秋霞成人午夜鲁丝一区二区三区| 97公开超碰在线视频| 酒色.com| 一品道门在线视频| 久久精品美女| 语文老师扒开胸罩喂我奶| 久久久视频2019午夜福利| 成人性生交大片免费看4| 亚洲永久精品ww47| 巨胸美乳中文在线观看| 国产h视频在线观看免费| 2020年国产精品午夜福利在线观看| 麻豆精品传媒2021网站入口| 97夜夜澡人人爽人人模人人喊| 美女张开让男生桶| 国产精品一区二区激情| 亚洲精品无夜久久久久久久久| 黄小飞二人转| 草柳最新地址| 亚洲精品天堂在线观看| 人妻夜夜爽99麻豆AV| 国产精品久久毛片A片软件爽爽| 亚洲 小说 欧美 激情 另类|