圖 - Embedded中的嵌入和拓撲有什麼區別？

Question

在Algorithm Design Manual，178頁描述圖的一些特性，並且它們中的一個是嵌入與拓撲：

嵌入式與拓撲

的曲線圖被嵌入如果頂點和邊 分配幾何位置。因此，圖 的任何圖形都是嵌入，其可能具有或不具有算法重要性。

偶爾，圖的結構完全由其嵌入的幾何圖形定義。例如，如果我們在飛機中獲得點的集合 ，並且尋求訪問它們的所有 （即，旅行商問題）的最小成本旅遊，則底層拓撲 是連接每對頂點的完整圖。權重 通常由每對點之間的歐幾里得距離定義。

點的網格是幾何拓撲的另一個示例。 n×m網格上的許多問題涉及在相鄰的點之間步行，所以邊從幾何體隱式定義。

我挺不理解：

1. 首先，究竟是什麼意思embedded這裏？只要頂點具有自己的幾何位置，那麼我可以調用嵌入的圖形嗎？
2. any drawing of a graph is an embedding是什麼意思？這是否意味着我在第1點中所說的？
3. Topological是什麼意思？我不認爲這是在本說明中解釋。
4. 這個描述中的例子讓我很困惑。有人可以用最簡單的詞讓我理解圖的這兩個術語嗎？
5. 讓這兩個詞理解真的很重要嗎？

感謝

Answer 1

1. 我提醒你，圖表僅僅是一組頂點和一組上定義的邊緣，所以頂點不擁有自己的幾何位置。圖的繪圖稱爲嵌入，繪製的圖被稱爲嵌入。
2. 這意味着繪製圖的任何方式都稱爲該圖的嵌入。
3. 拓撲圖是一個圖，其頂點和邊分別是點和弧。

Answer 2

Skiena使用地理友誼圖作爲嵌入圖的示例，因爲每個頂點都與朋友生活的這個世界中的地理點相關聯。

摘自該書 - 我的朋友住在我附近嗎？ - 社交網絡不與地理分離。你的許多朋友只是因爲他們碰巧住在你附近（例如，鄰居）或習慣住在你附近（如大學室友）而成爲你的朋友。

因此，對社交網絡的全面理解需要一個嵌入式圖表，其中每個頂點與他們生活的這個世界中的點相關聯。這種地理信息可能沒有明確的編碼，但圖形本身嵌入在平面中的事實決定了我們對任何分析的解釋。

Answer 3

除了msj的回答。

格拉夫= G(V, E)，其中V設置頂點的和和E設爲對頂點從V.這是圖的定義爲每Skiena。請注意，沒有提到這個圖形在視覺上是如何出現的（即沒有提及它的拓撲結構）。

實施例（注意，沒有定義，其中a，b位於說X，Y座標系）

V = { a, b, c, d, e, f }和E = { (a,b), (b,c), (a,e) }

要「繪製」需要爲其分配幾何位置例如圖在X，Y座標系中。

| 
|   b (2,3) 
| a(1,2) 
| 
| 
|____________________________ 
Fig 1 

圖1是簡單地嵌入在那裏我們繪製在E

之間的差異指定頂點對嵌入式和拓撲圖是如何的「拓撲」來定。在任何「嵌入」中，您都可以像上面解釋的那樣手動分配幾何位置，但在拓撲圖中，您可以根據圖的拓撲定義自己來定義「規則」。例如你指定一個G(V,E)並定義一個規則，比如說「訪問每個節點一次」定義了稱爲「完整圖」的拓撲。