• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    圖論中若干經(jīng)典問(wèn)題

    2023-07-10 00:04:34武育杰王浩王宏立王曉
    電腦知識(shí)與技術(shù) 2023年14期
    關(guān)鍵詞:圖論

    武育杰 王浩 王宏立 王曉

    關(guān)鍵詞:圖論;四色問(wèn)題;中國(guó)郵遞員問(wèn)題;哈密爾頓圖

    中圖分類(lèi)號(hào):O157.5 文獻(xiàn)標(biāo)識(shí)碼:A

    文章編號(hào):1009-3044(2023)14-0106-03

    1 引言

    圖是一個(gè)具有二元代數(shù)結(jié)構(gòu)特征的數(shù)學(xué)模型,由頂點(diǎn)集和邊集構(gòu)成,頂點(diǎn)表示研究對(duì)象,邊表示研究對(duì)象之間的關(guān)系。凡是涉及研究對(duì)象及其關(guān)系的問(wèn)題都可以用“圖”來(lái)建立其拓?fù)鋽?shù)學(xué)結(jié)構(gòu)。圖論作為理論工具,在復(fù)雜網(wǎng)絡(luò)系統(tǒng)、多智能體、分子結(jié)構(gòu)和能量、生物基因譜分析、大數(shù)據(jù)分析以及社交網(wǎng)絡(luò)等諸多領(lǐng)域中都有著廣泛的應(yīng)用。

    圖論作為數(shù)學(xué)學(xué)科的一個(gè)分支,已經(jīng)有200余年的歷史。公認(rèn)的圖論第一篇論文是由瑞士數(shù)學(xué)家歐拉在1736 發(fā)表的關(guān)于哥尼斯堡七橋問(wèn)題的論文[1]。在哥尼斯堡七橋問(wèn)題中,將各個(gè)獨(dú)立的陸地區(qū)域視為頂點(diǎn),每一座橋視為連接兩個(gè)頂點(diǎn)的邊,便構(gòu)造了一個(gè)既簡(jiǎn)潔又直觀的圖。1847年Kirchhoff運(yùn)用圖論作為工具,成功地解決了電路理論中求解聯(lián)立方程的問(wèn)題,引進(jìn)了“樹(shù)”的概念,樹(shù)是圖論也是計(jì)算機(jī)理論中最基本并且是應(yīng)用最多的概念之一[1]。1857年Cayley 在有機(jī)化學(xué)領(lǐng)域利用圖論中的樹(shù)為工具,解決了計(jì)算飽和氫化物同分異構(gòu)體的數(shù)目的問(wèn)題,這使得圖論在化學(xué)領(lǐng)域也發(fā)揮了重要作用。1936年,匈牙利數(shù)學(xué)家Konig出版了圖論的第一部專(zhuān)著《有限圖與無(wú)限圖理論》,這是圖論發(fā)展史上最重要的里程碑,它標(biāo)志著圖論已成為一個(gè)具有完整體系的數(shù)學(xué)分支[2]。

    現(xiàn)實(shí)世界中許多問(wèn)題都可以用圖來(lái)描述其數(shù)學(xué)拓?fù)浣Y(jié)構(gòu),通訊網(wǎng)、交通網(wǎng)、社團(tuán)網(wǎng)、化學(xué)分子結(jié)構(gòu)、生物基因圖譜、大規(guī)模集成電路都可以用圖來(lái)建立其數(shù)學(xué)模型框架。在理論研究上,圖論主要分為結(jié)構(gòu)圖論、極值圖論、代數(shù)圖論、隨機(jī)圖論、拓?fù)鋱D論等幾個(gè)主要模塊,這幾個(gè)方面相互促進(jìn)相互影響,共同促進(jìn)圖論的發(fā)展。

    一個(gè)好的數(shù)學(xué)問(wèn)題應(yīng)該具有描述的簡(jiǎn)潔性、結(jié)論的出乎意料性、應(yīng)用上的一般性。圖論中的四色問(wèn)題、歐拉圖問(wèn)題和哈密爾頓問(wèn)題就完整地具備這些特征。由四色問(wèn)題衍生出圖的著色理論,已成為結(jié)構(gòu)圖論中最經(jīng)典的部分[3];中國(guó)郵遞員問(wèn)題來(lái)源于歐拉圖問(wèn)題,是中國(guó)學(xué)者研究圖論的典型結(jié)果之一[4];哈密爾頓圖問(wèn)題也稱(chēng)為周游世界問(wèn)題,是一個(gè)經(jīng)典的NP-困難問(wèn)題,對(duì)NP問(wèn)題的研究起到了重要的促進(jìn)作用[5]。通過(guò)對(duì)圖論中一些經(jīng)典問(wèn)題的起源、發(fā)展及影響的概述,可以促進(jìn)圖論知識(shí)的普及,吸引更多研究者深入研究圖論理論及其應(yīng)用。

    2 圖論的起源——哥尼斯堡七橋問(wèn)題

    十八世紀(jì)的哥尼斯堡(現(xiàn)為俄羅斯的加里寧格勒),普列戈利亞河橫穿其中,河上有七座橋,連接著A、B、C、D四塊陸地,如圖1所示。當(dāng)?shù)亓鱾髦粋€(gè)著名的游戲謎題:能否從某塊陸地出發(fā),恰好把每座橋走一次,最后又回到原地?1735年幾名大學(xué)生給當(dāng)時(shí)的數(shù)學(xué)家歐拉寫(xiě)信,請(qǐng)教這個(gè)問(wèn)題。一年之后,歐拉證明了哥尼斯堡七橋問(wèn)題是無(wú)解的,并引入了圖的概念,由此開(kāi)創(chuàng)了圖論這一新的數(shù)學(xué)分支。

    歐拉將A、B、C、D四塊陸地看作頂點(diǎn),連接它們的橋看作邊,七橋問(wèn)題就轉(zhuǎn)化為圖1中右邊的圖是否有經(jīng)過(guò)每一條邊恰好一次的回路的問(wèn)題。這樣的回路稱(chēng)為歐拉回路,歐拉證明了圖論中最古老的定理(歐拉定理):無(wú)奇度頂點(diǎn)的連通圖存在歐拉回路且可分解成邊不交的圈。同時(shí),歐拉處理七橋問(wèn)題的方法也蘊(yùn)含著拓?fù)鋵W(xué)的思想,拓?fù)鋵W(xué)只關(guān)注圖形形狀的連接性,而并不關(guān)注自身的具體的大小和距離。交通網(wǎng)絡(luò)圖、通信網(wǎng)絡(luò)圖、社交網(wǎng)絡(luò)圖等都是以圖為基本結(jié)構(gòu)來(lái)建立現(xiàn)實(shí)問(wèn)題的數(shù)學(xué)拓?fù)淠P汀?/p>

    山東師范大學(xué)的管梅谷教授在20世紀(jì)60年代提出一個(gè)運(yùn)籌學(xué)問(wèn)題:郵遞員每天從郵局出發(fā),走遍該地區(qū)所有的街道再返回郵局,他如何安排送信路線可以使所走的總路程最短?這個(gè)問(wèn)題被稱(chēng)為中國(guó)郵遞員問(wèn)題,其數(shù)學(xué)描述為:在賦權(quán)圖中找一條回路,使得過(guò)每條邊至少一次,且邊的權(quán)之和最小,即為帶權(quán)最優(yōu)歐拉回路問(wèn)題。管梅谷給出了奇偶點(diǎn)圖上作業(yè)法,求解中國(guó)郵遞員問(wèn)題。1985年Edmonds給出了中國(guó)郵遞員問(wèn)題的多項(xiàng)式算法[6]。

    由歐拉定理可知?dú)W拉圖的邊可以分解為邊不交的圈,但是最少可以分解成多少個(gè)邊不交的圈呢?Hajos曾給出猜想(被稱(chēng)為Hajos猜想):n個(gè)頂點(diǎn)的歐拉圖至多可以分解為n/2個(gè)邊不交的圈[7]。1966年,Erd?s、Goodman和Posa將此猜想弱化,猜想存在常數(shù)c使得n個(gè)頂點(diǎn)的歐拉圖可分解成cn個(gè)邊不交的圈。這兩個(gè)猜想被Pyber認(rèn)為是“out of reach at present”。

    認(rèn)哥尼斯堡七橋問(wèn)題為起源,歐拉引出了“圖”這一數(shù)學(xué)模型結(jié)構(gòu),構(gòu)建了圖論的雛形。隨著中國(guó)郵遞員問(wèn)題、歐拉圖的圈分解問(wèn)題等的出現(xiàn),進(jìn)一步促進(jìn)了圖論的發(fā)展。

    3 圖論發(fā)展的動(dòng)力——四色問(wèn)題

    四色問(wèn)題曾和費(fèi)馬猜想(1994年已由英國(guó)數(shù)學(xué)家證明,被稱(chēng)為費(fèi)馬大定理)、哥德巴赫猜想被稱(chēng)為世界三大數(shù)學(xué)猜想。1852 年Morgan 教授的一位學(xué)生問(wèn)他,能否證明:只需四種顏色就可以給任意地圖的每個(gè)國(guó)家著色,使得任意有共同邊界的國(guó)家所著的顏色不同。把地圖看作一個(gè)平面圖,國(guó)界看作是邊,不同國(guó)界的相交處看作是頂點(diǎn),每個(gè)國(guó)家的區(qū)域就是面,則上述問(wèn)題就是:任意一個(gè)平面圖最多用四種顏色給每個(gè)面著色,就可以使得有任何有公共邊的面所著的顏色都不同。如圖2,用4種顏色就可以把中國(guó)地圖各個(gè)相鄰的省份區(qū)分開(kāi)。

    1872年,英國(guó)數(shù)學(xué)家Cayley正式向倫敦?cái)?shù)學(xué)學(xué)會(huì)提出了四色問(wèn)題。自此以后,四色問(wèn)題逐漸成為世界數(shù)學(xué)界關(guān)注的研究對(duì)象,吸引了一批優(yōu)秀的數(shù)學(xué)家不斷地進(jìn)行探索。一百多年來(lái),這個(gè)看似簡(jiǎn)單的問(wèn)題,卻讓許多一流的數(shù)學(xué)家“折戟沉沙”。后人評(píng)價(jià)德國(guó)著名數(shù)學(xué)家Minkowski(曾是愛(ài)因斯坦的老師),最讓他尷尬的不是他曾罵愛(ài)因斯坦是“懶蟲(chóng)”,而是他被四色問(wèn)題掛在了黑板上。

    1878年到1880年之間,數(shù)學(xué)家Kempe和Tait先后發(fā)表了關(guān)于四色問(wèn)題的論文,宣布四色問(wèn)題已獲得證明。大家都認(rèn)為四色問(wèn)題從此也就解決了,然而十年后,人們卻發(fā)現(xiàn)這兩人的證明都是錯(cuò)誤的。1890年Heawood給出了Kempe證明中的一個(gè)反例(即為著名的Heawood 圖),從而推翻他的證明,并且利用Heawood的方法卻可以很容易就得到平面圖的5-色定理。Tait證明的錯(cuò)誤之處是他認(rèn)為3-正則且3-連通的平面是哈密爾頓圖(有一個(gè)圈包含圖中所有的頂點(diǎn))。1946年,數(shù)學(xué)家Tutte給出了一個(gè)3-正則且3- 連通的平面圖不是哈密爾頓圖,從而徹底宣告了Tait 證明中的錯(cuò)誤是無(wú)法修補(bǔ)的。雖然Kempe和Tait關(guān)于四色問(wèn)題的證明是錯(cuò)誤的,但是他們二人均為之后四色問(wèn)題的證明奠定了基礎(chǔ),并為之后圖論的發(fā)展做出了不可磨滅的貢獻(xiàn)。

    20世紀(jì)以后,數(shù)學(xué)家關(guān)于四色問(wèn)題的探索基本上是沿著Kempe 的思路進(jìn)行。1936 年,美國(guó)數(shù)學(xué)家Franklin證明了22個(gè)面以?xún)?nèi)的平面圖都是4-可面著色的。沿用此思路,四色問(wèn)題在1950年被改進(jìn)到了35個(gè)面,隨后又被改進(jìn)到了50個(gè)面。1976年,美國(guó)數(shù)學(xué)家Appel和Haken與計(jì)算機(jī)專(zhuān)家Kock三人合作完成了四色問(wèn)題的證明[8-9],這也開(kāi)創(chuàng)了利用計(jì)算機(jī)來(lái)證明數(shù)學(xué)重大問(wèn)題的先河。1994年,Seymour在第22屆國(guó)際數(shù)學(xué)家大會(huì)上做了1小時(shí)報(bào)告,報(bào)告的主題就是關(guān)于四色問(wèn)題的證明。

    給出Tait證明四色問(wèn)題反例的數(shù)學(xué)家Tutte,一直致力于研究從純粹數(shù)學(xué)的角度來(lái)證明四色問(wèn)題,希望找到純推理的方法來(lái)證明。為此,Tutte創(chuàng)立了整數(shù)流理論[10],從更大的框架內(nèi)來(lái)研究四色問(wèn)題。Tutte提出了三個(gè)整數(shù)流猜想,形成了整數(shù)流研究的核心問(wèn)題。目前,整數(shù)流理論已成為圖論研究的前沿問(wèn)題之一。

    4 圖論的NP-困難問(wèn)題——哈密爾頓圖

    1856年愛(ài)爾蘭數(shù)學(xué)家哈密爾頓(他也是第一個(gè)給出復(fù)數(shù)的代數(shù)表示的數(shù)學(xué)家)設(shè)計(jì)了一個(gè)游戲:給定一個(gè)十二面體(如圖3所示),每個(gè)點(diǎn)代表一個(gè)城市,每條棱代表兩個(gè)城市之間的一條路,是否存在從某一城市出發(fā),經(jīng)過(guò)每座城市恰好一次,最后又回到出發(fā)點(diǎn)?此問(wèn)題也稱(chēng)為周游世界問(wèn)題。十二面體的20個(gè)點(diǎn)的拓?fù)浣Y(jié)構(gòu)可以用圖3中右圖的平面圖來(lái)表示,周游世界問(wèn)題是有滿(mǎn)足條件的走法的,即圖中存在一個(gè)圈恰好包含每個(gè)頂點(diǎn)一次,這樣的圈稱(chēng)為哈密爾頓圈,含有哈密爾頓圈的圖稱(chēng)為哈密爾頓圖。

    更一般化的周游世界問(wèn)題,或者稱(chēng)為旅行商問(wèn)題,即一個(gè)旅行商從公司出發(fā),訪問(wèn)若干指定城市,最后返回公司,要求設(shè)計(jì)最優(yōu)旅行路線(行程最短或費(fèi)用最小)。數(shù)學(xué)抽象描述為:在賦權(quán)圖中找一條回路使得過(guò)每個(gè)點(diǎn)恰好一次且邊的權(quán)之和最小,即尋找賦權(quán)最優(yōu)哈密頓圈[5]。

    不同于歐拉圖,目前還沒(méi)有一個(gè)判定圖是哈密爾頓圖的非平凡的等價(jià)條件,這也是圖論中最重要的未解決問(wèn)題之一。1952年,Dirac給出了判定哈密爾頓圖的度型條件;1960年,Ore給出了改進(jìn)的度型條件;1972年,Chvátal給出了判定哈密爾頓圖的度序列條件;1976年Bondy和Chvátal給出了判定哈密爾頓圖的閉包條件[1]。

    從算法角度看,判定圖的哈密爾頓性是NP-困難的。研究世紀(jì)猜想——NP問(wèn)題,哈密爾頓圖即為一個(gè)很好的突破口。通常判定一個(gè)圖是否含有哈密頓圈都是用窮舉的方法。Rubin利用推演的方法給出了一個(gè)可優(yōu)化的搜索步驟尋找圖中的哈密爾頓圈,An?gluin和Valiant利用概率方法設(shè)計(jì)了一種尋找哈密爾頓圈的非常有用的方法。

    從應(yīng)用的角度看,從工業(yè)鋪路到農(nóng)業(yè)灌溉,從航空路線到海底偵察,從國(guó)家的發(fā)展到公司的運(yùn)輸都要用到哈密頓圖的基礎(chǔ)數(shù)學(xué)模型結(jié)構(gòu)。對(duì)哈密爾頓圖的研究已經(jīng)顯得越來(lái)越重要,利用哈密爾頓圖的研究結(jié)果,可以大大提高工作的效率和節(jié)約發(fā)展成本,為可持續(xù)發(fā)展提供重要支持。

    5 結(jié)束語(yǔ)

    國(guó)內(nèi)著名圖論學(xué)者范更華教授曾講過(guò),以蒸汽機(jī)為標(biāo)志的工業(yè)革命促進(jìn)了以微積分為基礎(chǔ)的連續(xù)數(shù)學(xué)的發(fā)展,以計(jì)算機(jī)為標(biāo)志的信息革命將極大地促進(jìn)離散數(shù)學(xué)的發(fā)展,而圖論則是離散數(shù)學(xué)最主要的分支之一?,F(xiàn)實(shí)世界中許多問(wèn)題都可以用圖來(lái)描述其數(shù)學(xué)拓?fù)浣Y(jié)構(gòu),四色問(wèn)題、中國(guó)郵遞員問(wèn)題和周游世界問(wèn)題都是圖論中的經(jīng)典問(wèn)題,在圖論學(xué)科的發(fā)展過(guò)程中起著至關(guān)重要的作用。綜述圖論中經(jīng)典問(wèn)題的發(fā)展歷史,可促進(jìn)圖論知識(shí)的普及,吸引更多研究者深入研究圖論理論知識(shí)及其在現(xiàn)實(shí)中的應(yīng)用。

    猜你喜歡
    圖論
    基于圖論的高職院校補(bǔ)考排考算法設(shè)計(jì)
    基于FSM和圖論的繼電電路仿真算法研究
    構(gòu)造圖論模型解競(jìng)賽題
    代數(shù)圖論與矩陣幾何的問(wèn)題分析
    圖論中貪心算法的應(yīng)用
    圖論最短路徑算法的圖形化演示及系統(tǒng)設(shè)計(jì)
    點(diǎn)亮兵書(shū)——《籌海圖編》《海防圖論》
    孫子研究(2016年4期)2016-10-20 02:38:06
    基于圖論的圖像分割技術(shù)探討
    圖論在高校排課中的應(yīng)用
    圖論在變電站風(fēng)險(xiǎn)評(píng)估中的應(yīng)用
    山丹县| 资中县| 乌兰县| 中宁县| 德钦县| 尤溪县| 雷州市| 樟树市| 内丘县| 奉化市| 平罗县| 龙川县| 伊宁市| 钦州市| 拉萨市| 读书| 怀集县| 闽侯县| 晋州市| 留坝县| 闽清县| 新巴尔虎左旗| 云龙县| 绥滨县| 江孜县| 辽阳市| 定陶县| 手游| 依安县| 北碚区| 水城县| 虎林市| 梁山县| 胶南市| 年辖:市辖区| 隆子县| 井冈山市| 大英县| 奉节县| 万全县| 柏乡县|