algorithm - graph - Graph 中的 Embedded 和 Topological 之间有什么区别？

Question

在Algorithm Design Manual ，第178页描述了Graph的一些属性，其中之一是embedded和Topological:

Embedded vs. Topological

A graph is embedded if the vertices and edges are assigned geometric positions. Thus, any drawing of a graph is an embedding, which may or may not have algorithmic significance.

Occasionally, the structure of a graph is completely defined by the geometry of its embedding. For example, if we are given a collection of points in the plane, and seek the minimum cost tour visiting all of them (i.e., the traveling salesman problem), the underlying topology is the complete graph connecting each pair of vertices. The weights are typically defined by the Euclidean distance between each pair of points.

Grids of points are another example of topology from geometry. Many problems on an n × m grid involve walking between neighboring points, so the edges are implicitly defined from the geometry.

我不太明白:

1. 首先，embedded 在这里到底是什么意思？只要顶点有自己的几何位置，我就可以称这个图为嵌入的吗？
2. 任何图的绘制都是嵌入是什么意思？这是否意味着我在第 1 点中所说的？
3. 拓扑 是什么意思？我认为此描述中没有对此进行解释。
4. 这个描述中的例子真的让我很困惑。有人可以用最简单的词让我理解这两个图形术语吗？
5. 理解这两个术语真的很重要吗？

谢谢

Answer 1

1. 提醒您，图只是一组顶点和定义在顶点上的一组边，因此顶点没有自己的几何位置。绘制图称为嵌入，绘制的图称为嵌入。
2. 这意味着绘制图形的任何方式都称为该图形的嵌入。
3. 拓扑图是顶点和边分别为点和弧的图。