圖的l1-嵌入性理論及其應(yīng)用

　　現(xiàn)實(shí)世界中，許多問(wèn)題都可以用圖來(lái)表示。這里的“圖”是指由點(diǎn)和線構(gòu)成的圖形，例如，點(diǎn)代表車站，線代表鐵路構(gòu)成的鐵路網(wǎng)絡(luò)圖；點(diǎn)代表計(jì)算機(jī)，線代表連接計(jì)算機(jī)的網(wǎng)線構(gòu)成的計(jì)算機(jī)網(wǎng)絡(luò)圖；點(diǎn)代表電子元件，線代表電子元件之間連接的物理導(dǎo)線構(gòu)成的電網(wǎng)絡(luò)圖等，事實(shí)上，對(duì)給定的對(duì)象集合，對(duì)象間定義一種二元關(guān)系，兩個(gè)對(duì)象之間具有此二元關(guān)系，則連接一條線，否則不連線，這就構(gòu)成了一個(gè)圖，圖論正是研究這類圖的結(jié)構(gòu)和性質(zhì)等問(wèn)題的一門(mén)學(xué)科。自1736年Euler發(fā)表*篇圖論論文——《哥尼斯堡的七座橋》開(kāi)始，特別是20世紀(jì)70年代隨著計(jì)算機(jī)科學(xué)的發(fā)展，圖論發(fā)展十分迅速，應(yīng)用也十分廣泛。它在物理學(xué)、化學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、網(wǎng)絡(luò)理論等方面均有應(yīng)用。度量（或距離）空間是泛函分析中基本的概念，它為統(tǒng)一處理分析學(xué)各分支的重要問(wèn)題提供了一個(gè)共同基礎(chǔ)，它研究的范圍非常廣泛，包括了在工程技術(shù)、物理學(xué)和數(shù)學(xué)中遇到的許多有用的函數(shù)空間。同時(shí)，度量（或距離）也是圖論、組合優(yōu)化等離散數(shù)學(xué)中非常核心的研究對(duì)象，比如兩點(diǎn)之間的短路問(wèn)題、中國(guó)郵遞員問(wèn)題、網(wǎng)絡(luò)大流等問(wèn)題。它在其他數(shù)學(xué)領(lǐng)域及應(yīng)用中也都出現(xiàn)過(guò)，比如距離幾何（distancegeometry），組合矩陣論、設(shè)計(jì)理論、量子力學(xué)、統(tǒng)計(jì)物理、分析和概率論等。除了數(shù)學(xué)理論上的研究，度量還在其他領(lǐng)域有很多應(yīng)用。在計(jì)算機(jī)科學(xué)中，許多基本的問(wèn)題都涉及數(shù)據(jù)點(diǎn)集以及它們之間的相似性或異樣。數(shù)據(jù)分類、*近鄰點(diǎn)搜索、點(diǎn)集直徑的計(jì)算以及網(wǎng)絡(luò)搜索等都屬于這個(gè)范疇，在生物學(xué)中，許多計(jì)算基因組學(xué)的應(yīng)用需要DNA或蛋白質(zhì)序列的數(shù)據(jù)庫(kù)的搜索或聚類，為了解決此類問(wèn)題，人們通常是利用問(wèn)題對(duì)象所處的空間來(lái)獲得更好的算法。但遺憾的是，很多有意義的度量空間尚未被深入研究，因而其中很多有用的結(jié)構(gòu)定理尚不為人所知。受此問(wèn)題的驅(qū)動(dòng)，一個(gè)自然的想法是將考慮的問(wèn)題對(duì)象放到一些研究很成熟的基本度量空間中，然后利用基本度量空間的特殊結(jié)構(gòu)性質(zhì)來(lái)獲得更有效的算法。例如圖的Wiener指標(biāo)，即圖中所有點(diǎn)對(duì)之間的距離和，直接利用定義公式計(jì)算，其復(fù)雜度為頂點(diǎn)立方階的。但若圖是l1-嵌入的，其計(jì)算復(fù)雜度則可以降為頂點(diǎn)線性階的。因此研究圖的伴隨度量空間能否等距離嵌入到l1-空間中，具有重要的意義。

暫缺《圖的l1-嵌入性理論及其應(yīng)用》作者簡(jiǎn)介