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

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

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