圖的l1-嵌入性理論及其應用

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

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