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