图-嵌入和拓扑在图中的区别是什么？

Question

在算法设计手册中，第178页描述了图的一些属性，其中一个属性是嵌入和拓扑的：

嵌入式与拓扑 如果顶点和边被分配给几何位置，则嵌入一个图。因此，图的任何绘图都是嵌入图，它可能具有算法意义，也可能没有算法意义。 有时，图的结构完全由嵌入的几何形状来定义。例如，如果给我们一个平面上的点集合，并寻求访问所有这些点的最小代价旅行(即旅行推销员问题)，则底层拓扑就是连接每一对顶点的完整图。权值通常由每对点之间的欧几里德距离定义。 点网格是几何拓扑的另一个例子。N×m网格上的许多问题都涉及到相邻点之间的行走，因此从几何上隐式地定义了边。

我完全不明白：

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

谢谢

Answer 1

1. 我提醒你，图只是一组顶点和一组定义在它们上的边，所以顶点没有自己的几何位置。图的绘图称为嵌入，绘制的图称为嵌入。
2. 这意味着任何绘制图的方法都被称为该图的嵌入。
3. 拓扑图是顶点和边分别为点和弧的图。

Answer 2

除了msj的回答。

图= G(V, E)，其中V是顶点集，E是V中的一对顶点。这是图的定义。请注意，如何没有提到该图形的视觉显示(即，没有提到它的拓扑)。

示例(请注意，它没有定义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)并定义了一个规则，比如“访问每个节点一次”，定义了称为“完全图”的拓扑结构。

Answer 3

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

这本书的摘录-我的朋友住在我附近吗？-社交网络并没有脱离地理。你的许多朋友是你的朋友，只是因为他们碰巧住在你附近(例如，邻居)或过去住在你附近(例如，大学室友)。

因此，对社会网络的全面理解需要一个嵌入的图表，其中每个顶点都与他们所居住的世界中的点相关联。这种地理信息可能不会被显式编码，但是图形内在地嵌入在平面上这一事实决定了我们对任何分析的解释。