信息化概念與圖的哈密爾頓性

1、 南京航空航天大學(xué)博士后士學(xué)位論文信息化概念與圖的哈密爾頓性姓名：孫志人申請學(xué)位級別：博士后士專業(yè)：航空宇航制造工程指導(dǎo)教師：丁秋林2001.10.1 痜 畉簅琲、 南京航窄航天人學(xué)博籐仆報告綸腳個競爭異常激烈的全球性的捍鍶場g蟮與發(fā)展侖業(yè)必須加就成為信息社會剝企的必然要住信息社會帶來的一切機會，迎接信息社會的嚴峻挑戰(zhàn)。 云簟蛚學(xué)信息科學(xué)有藪蟮姆共蜒由斕叫磯嗔煊頡嗣荓二經(jīng)認識劍，在現(xiàn)代科學(xué)技顯得很年輕，人類對信息的認識還很不夠，迄今為止，它還未形成很完整的系統(tǒng) 的概念。通俗地說，信息就是消息。這是一種釔氈櫚母拍睿彩巧緇：最流行了信息。這個概念】白，但不準確。廣義地晚，信息足對物質(zhì)存在和運動衣物

2、是客體，但客體是不重要的，重要的是含于窖體奇去的思念和情感，這是物質(zhì)、能量和信息是構(gòu)成客觀唬憾笠;浚畔鬮颙貢芰堪兀嚎課平時中分牟瘓瘸潭取畔皇俏鎦省畔嗆撾锏謀韋的范疇可以概括為：探討信息的本質(zhì)、研究信啟、淞俊糾信息的運動艦碓、信息科學(xué)的研究領(lǐng)域十分廣泛，心問題呵以歸結(jié)為認以佶，魍、和利信型。億認識信息方面，要包括：究信息的本質(zhì)和度量方麗，研究信息的撼水運動規(guī)律，如信息識別、信息提取、信息轉(zhuǎn)換、信息存口信息處理、信息傳遞、信息艙索、信息決策等等的原理和規(guī)律。這些是信啟、論籽芯糠凍?。豪眯畔⒎矫?，卜要包括：研究怎樣利用信息末進行有效控制以及怎樣利用信息來建、，最優(yōu)系統(tǒng)，返制，可以隨時隨地的進行各種

3、格樣的信息交換。綜合業(yè)務(wù)數(shù)字信息網(wǎng)使人類進入學(xué)的結(jié)構(gòu)和體系，改變了科學(xué)的面貌、思維方法和發(fā)展前景。信息系統(tǒng) 。二息系統(tǒng)和情報險索系統(tǒng)。信息系統(tǒng)迷詵锿鷌家中已涉及到兇椴蕒和人 、息系統(tǒng)表示，以定義信包、化?；?。也就，遙8豀吉究的方向。金振玉編著，信息論，北京理工大學(xué)出版社，。 計算機科學(xué)技術(shù)包括科學(xué)與技術(shù)兩個方面。 月：拓了人類認識自然、改造自然的新資源：拓了人類“、識自然、改造然的新資源。提供了人類創(chuàng)造文化的新具： 罐、化概念，心的晰南篒日引起了人類的工作方式與生活方式的變化。社會與經(jīng)濟的發(fā)展使各類社會組織的、止務(wù)信，皂、急劇增長，決策處理科學(xué)化和時效汁算機的發(fā)展 息處理的方法與技術(shù)手段?？茖W(xué)

4、是技術(shù)的依掘，技術(shù)是科學(xué)的體現(xiàn)；技術(shù)得益于科計算機科學(xué)理論 計算機類型可從不同角度來分：數(shù)字計算機、模擬計算機、混合計算機一數(shù) 并把相應(yīng)的控制信號送往各個部件以完成規(guī)定的操作。件的發(fā)展，促進了汁算機科學(xué)技術(shù)的發(fā)展。 為數(shù)拋處理系統(tǒng)，中層為管理信息系統(tǒng)，高三為決策支持系統(tǒng)。 塑皇墮檳級墮竺工魚坐查計算機科學(xué)技術(shù)與汁算機產(chǎn)業(yè)密切相關(guān)。計算機科學(xué)技術(shù)的研究丌發(fā)成果只有通過產(chǎn)、比的商品轉(zhuǎn)化，進入市場，才能產(chǎn)生價值與粱峋瞇?。『开N蠢盯場，帶求與資源，促進計算機科學(xué)技術(shù)的更大發(fā)展。而引算機產(chǎn)、也只有緊密依靠汁算機科學(xué)技術(shù)提供新思想、新方法、新技術(shù)、耨工藝以更新產(chǎn)。是，拓寬市場增強競爭力。二一者相輔相成，從

5、而構(gòu)成計算機事業(yè)發(fā)展的良性循耶。甏跗 最早清楚地使用了多面體組合的方法。年，他在一篇文章中利用了一個本質(zhì)上是引理的定理，該定理可從凸集論很自然地得到。然而，多面體組合發(fā)展的第一個階段真正開始于二十世紀五十年代，它伴隨著線性規(guī)劃單純形算法的發(fā)現(xiàn)而發(fā)展。許多組合問題，尤其是各種網(wǎng)絡(luò)流問題，都能表述成整數(shù)線性規(guī)劃，而其約束矩陣都是全單位模的。于是，這些“整數(shù)”線性規(guī)劃實際上就是線性規(guī)劃。因此，可以應(yīng)用單純形算法以及更重要的線性規(guī)劃對偶來解決。不是充分的“。對這些問題的約束集，通過加入可能是指數(shù)個約束而得到這個問題的一個完全的線性描述。對這個描述，即使不能用單純形算法，也能用線性規(guī)劃對偶。然后，利用并

6、證明一般的對偶關(guān)系，對這些問題設(shè)計多項式界的算法。有了這些成功后，人們?yōu)榱说玫叫┓浅！袄щy”問題的完全的線性描述而花費了大量的努力一一這些 隨著線性規(guī)劃橢球算法的發(fā)展，年，多面體組合開始了其發(fā)展的第三個階段。多面體組合的重要性不僅在于線性規(guī)劃能在多項式時間內(nèi)解決，而且更重要地在于其算法形式。它的成功在于能夠有效地證明給定點是否是線性不等式組的解，如果不是，就給出一個矛盾的不等式。這樣，如果這個分類問題墻猓故遣皇墻能夠有效地得到解決，那么相應(yīng)的優(yōu)化問題也能夠有效地解決。此外，反過來也是對的：如果能夠有效地解決一個最優(yōu)化問題，那么我們也能夠解決上面這個分類問題。這引起了對分類問題的極大興趣，更主要

7、的原因在于，一般看來分類問題與相伴隨的優(yōu)化算法非常不同。 不等式，于是有瑀。必要性得證。反過來，設(shè)，蔖。由線性規(guī)劃對偶理論，令米钚擔(dān)琛瑂韞不引起誤會，我們就略去上標丁某個目標函數(shù)在這個子集上達到淖畬籩怠貢礱鰨琍的面與募蟮姆強照婷娉莆狿的極大面蝗舳閱掣??！蔖，設(shè)。狪的有限子集。如果對任意，；類似地，如果對任意蔿。，。：蕏 向量組是仿射無關(guān)的當(dāng)且僅當(dāng)對該向量組的每一個向量增加一量，因而，在多面體組合中仿射無關(guān)比線性無關(guān)更有用。為姆律滸。命題勻我獾腟耐，總有甴，則，。瑂。 南京航空航天大學(xué)博士后研究工作報告設(shè)蔍“，誓停鑀為多面體?，{對任意的蔖、刪。維數(shù)與定義線性組的等式集之間的如下關(guān)系：【，且設(shè)性行

8、秩。由定理 ，葉勻我獾?。∈P有。瓶邸蔖啊為適合不等式躱導(dǎo)出的面。的關(guān)系。設(shè)尸是一個多面體，【，弦， 定理，緖也矛盾。口設(shè)遜，則稱俏猚、，庋摹莆獂的凸組合。 南京航空航天大學(xué)博士后研究工作報告輳珿給出了多面體理論的一個基本結(jié)果：理，錐可由有限個向量唬生成，即鰲籄反過來，設(shè)存在一。，伽叫。溝枚勻我狻蔖省辬月恪簉即 南京航空航天大學(xué)博士后研究工作報告。騮，蛭h我舛悴荒鼙硎疚狿的其它點的凸組合。限線性組的解集。多面體組合的很大部分涉及到如何確定這樣的線設(shè)舉：，私鉤碎黕水 南京航空航天大學(xué)博士后研究工作報告所謂覆蓋咎餼褪茄罷乙桓蔆，使得而分解問題就是尋找一個，蔘，使得我們可將它們改述成整數(shù)規(guī)劃問題，為此

9、，先給出一些符號和定似麓器。是蛄 有這樣兩個有趣的問題：給定一個整矩陣保甦滿足什么條件時，對任意整向量條件下，對任意使得， 南京航空航天大學(xué)博士后研究工作報告狿的極小面，這里為廠的整向量。口有整數(shù)最優(yōu)解。這個定理的簡單證明。模的；設(shè)p新鵲摹眤不難證明如下命題。 ，簉欽牡鼻醫(yī)齙保為單位模的。注意到的對偶線性規(guī)劃是有最優(yōu)解的就稱線性組！躡具有全對偶整數(shù)性有頂點，欽蛄浚正明】用反證法。設(shè)有頂點皇欽恪環(huán)遼鑪，不是整數(shù)。根且有因為對應(yīng)于。和的線性規(guī)劃性虼俗畬籩刀際欽蔈猨，也是整數(shù)，矛盾。 的乇鸕?，P的每一個頂點都是整值的。輳珿和琤給出了上面結(jié)果的逆方向?，s是整值的。此外，拿扛齜強彰婧愕鼻醫(yī)齙眀是整值的。

10、完美圖定理一一點無關(guān)數(shù)，即最大點無關(guān)集的點數(shù)； 都有。，虺仆糋是一個完美圖畖 南京航空航天大學(xué)博士后研究工作報告假如有。的某一列只，使設(shè)有某點無關(guān)集，使剩記掣縣則作如下的變換后吼嵋，幣弧盛。的一“因為“，一哪。，故躸幣籲有巳一。胍蛭2蝗壞幕埃櫨型臗使得的數(shù)積。因此， 的一個最優(yōu)解。由璣，根據(jù)】 篈蝝狪瓹籒 設(shè)峭跡雜謖齠令設(shè)牽階渙虻跡舳雜諶我獾膡，有雜諶我鈏唬琲蕒，一搖苚則對于拿扛鱟畛荄一圈 設(shè)莕階簡單圖，而產(chǎn)琣是對于圖淖油薊淖蛹痎與令插點引理中其插入邊為的最后一個頂點，則將“，迦氳獎遳，中并且，稱邊集胰帳荊的一個分支再設(shè)，海瓼。闚 信息化概念與圖的哈密爾頓性對于蕒，設(shè)“鬐中的頂點簍對于“，唬若

11、骸?！尽盎』∈f蒥，則若剩堋搿瑃，隊畑瑉，一衛(wèi)瑌飫，簂、，：蔛甚這里竣嬖赼琋瑉設(shè)絹蔆，。，瑃，一、荂磺則，一唬，冢弦灰且，則 信息化概念與圖的哈密爾頓性魄陜黴注意到，長為腃獂口?？诳?、啦 顯然，?？　坎访芏ⅰ柏戤s弧渴又由引理，蔿，矛盾爿熱椋骸譯日，蕒 信息化概念與圖的哈密爾頓性躷，人，：下面證明一系列斷言，最后得到矛盾 從而，躿。日痷畗謔強縥 信息化概念與圖的哈密爾頓性由此，、獾劍瑂品島、獾劍琻于是，有口罰鴝，：，畂且當(dāng)：時，有：省【且當(dāng)盯十簟對于任意甇卜堍 信息化概念與圖的哈密爾頓性幻。飫飛；膟騛，。事實上，由一序列的定義，有。日下面依次證明所述結(jié)論：集合恰含一個元素對此劃分，顯然滿足械奶跫

12、謟”島，】于是，由及 盯浚簔堋篶簂，：氏浚：，從而：蕇珻：。，： 信息化概念與圖的哈密爾頓性于是，當(dāng)口時，有，】于是，由及“躭，有盯】：莖口】：于是，當(dāng)口】：保校簂瑉對于任意獾劍眤】、謔牽，有痾 繁是。牟迦氡嘸壞眏保珻的每個頂點都是瞎賾贑畍咐甲啦一使其插入邊屬于牡諞桓齠悖換蛘遅牡諞桓齠悖璐瞬迦氡呶猼。安遙鮮雋秸咔【悠湟唬鼻罷呤保鑉：甜澹叫隴，窘，蛾“蠆小?，u件?；，u薄首頤，勘， 信息化概念與圖的哈密爾頓性盯若則抑械那潿疾皇莑的大和區(qū)間雜二；盛痭遙傘及斷言，“圩 信息化概念與圖的哈密爾頓性設(shè)拼是鑪，：；兇詈笠桓鍪粲赟的頂點便在。，：斜賾卸閌粲趕下面分兩種情形討論：否則礎(chǔ)皕蛘摺皕且“佟啊成立舳雜趛

13、的所有大和區(qū)間，械都不成立，則對于給定的大和區(qū)間由此，褐兄煉嗪幸桓觥俊拇蠛頹鋤【：海當(dāng)后者時，有大和區(qū)間于是，結(jié)論成立、“一】事實上，由斷言可分下列兩種情形來討論；容易看出如睯鐘啥涎鋅： 信息化概念與圖的哈密爾頓性日。恰痷如恰再由斷言】，由斷言，一再由閑及斷言，有盯盯。是，結(jié)論成立瓸甁疭，甃甧甈琯琂 痏瓸篴吣毗鬻螄。一”。輔膃韍?！埃?信息化概念與圖的哈密爾頓性她瑪產(chǎn)甦癑?，b叫州瓼痚 ?，S戶“ 信息化概念與圖的哈密爾頓性搿甃，硭蔛，一。：甌、，埽賘琎，琣。，一。一琤。一甦 琎” 信息化概念與圖的哈密爾頓性，瓵甧瓽、甂 唬蔿”蒞 南京航空航天大學(xué)博士后研究工作報告甌產(chǎn)痜 甗郔聊畃蔞蔔”“，畐痠啵甪猵瑃猵譼 可饑”笹”。，引虬。 凡，“甃埃瑉甃 。痚】 吲猵“，、築痶，盛“、毛，。丁甞“，琭緐籡孑琹眤瑆 南京航空航天大學(xué)博士后研究工作報告如琧瓵篎猵痺鮣篠痶簑：己猧瑉 南京航空航天大學(xué)博士后研究工作報告口：孑、“一：郟產(chǎn) 痝“瑃 甗 生培養(yǎng)都產(chǎn)生了積極的影響。毫無疑問，本研究工作得到了國家自然科學(xué)基金以及