15

在Algorithm Design Manual中，第 178 页描述了 Graph 的一些属性，其中之一是嵌入和拓扑：

嵌入式与拓扑

如果顶点和边被分配了几何位置，则嵌入图。因此，任何图形的绘制都是一种嵌入，它可能具有也可能不具有算法意义。

有时，图的结构完全由其嵌入的几何形状定义。例如，如果给定平面上的一组点，并寻求访问所有这些点的最小成本旅行（即旅行商问题），则底层拓扑是连接每对顶点的完整图。权重通常由每对点之间的欧几里得距离定义。

点网格是几何拓扑的另一个示例。n × m 网格上的许多问题都涉及在相邻点之间行走，因此边缘是从几何图形中隐式定义的。

我完全不明白：

  1. 首先，embedded这里到底是什么意思？只要顶点有自己的几何位置，那我可以称之为嵌入图吗？
  2. 是什么any drawing of a graph is an embedding意思？这是否意味着我在第 1 点所说的？
  3. 是什么Topological意思？我认为这个描述中没有解释。
  4. 这个描述中的例子真的让我很困惑。有人可以用最简单的词让我理解这两个图表术语吗？
  5. 理解这两个术语真的很重要吗？

谢谢

4

3 回答 3

5
  1. 我提醒你，一个图只是一组顶点和一组定义在它们上面的边，所以顶点没有自己的几何位置。图的绘制称为嵌入，绘制的图称为嵌入。
  2. 这意味着任何绘制图形的方式都称为该图形的嵌入。
  3. 拓扑图是一个图，其顶点和边分别是点和弧。
于 2012-04-04T12:22:24.450 回答
1

除了 msj 的回答。

Graph = 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)并定义一个规则，例如“仅访问每个节点一次”定义了称为“完整图”的拓扑。

于 2016-10-07T05:21:56.883 回答
0

Skiena 使用地理友谊图作为嵌入式图的示例，因为每个顶点都与朋友居住的这个世界中的一个地理点相关联。

摘自本书 - 我的朋友住在我附近吗？– 社交网络并没有脱离地理。您的许多朋友之所以成为您的朋友，仅仅是因为他们碰巧住在您附近（例如，邻居）或曾经住在您附近（例如，大学室友）。

因此，对社交网络的全面理解需要一个嵌入式图，其中每个顶点都与他们所居住的这个世界中的点相关联。这种地理信息可能没有被明确编码，但图形固有地嵌入平面这一事实塑造了我们对任何分析的解释。

于 2016-09-25T00:45:21.320 回答