math - 无向图抽象

Question

我有一个无向加权图，我需要正式描述它。似乎没有为无向图定义通过自动机或标记转换系统进行的抽象，仅涵盖有向图。图中的状态相互依赖，但方向本身并不相关。

你知道什么数学模型可以用来正式描述这样的图吗？

Answer 1

您可以将无向加权图视为有向加权图，其限制是对于任何节点 A 和 B，如果存在从 A 到 B 的边，则也存在从 B 到 A 的具有相同权重的边。所以任何有向图的模型也可以用于无向图。因此，如果您使用显示权重的矩阵，只需要求矩阵是对称的。如果您使用从有序对到实数的函数，请改用无序对（这里我的意思是大小为 2 的多重集）或大小为一或二的集合的函数。等等。

对于编程模型（毕竟这是一个编程站点），您可以使用权重对称矩阵。在某些语言（如 Python）中，您可以定义具有不同长度的列表列表，您可以使用三角矩阵而不是对称矩阵，仅显示从前面列出的节点到后面列出的节点的边。这可能比对所有矩阵更改实施对称限制更容易。

Answer 2

图是一种数学抽象。有向标记图没有被建模为自动机，而是反过来。

如果您正在“低级数学”中寻找“实现”，则有多种可能性：

作为有向图

每个无向图都可以看作是有向图，只要有一条从a到b的边，就有一条从b到a的边。在加权图的情况下，我们添加了反平行边具有相同权重的要求。

成套

自从 ZFC（可能在此之前）数学家就倾向于将事物建模为集合。然后，一个简单的无向加权图将是一个三元组(V, E, w)，其中V是您的顶点/节点的集合，E是V的幂集的子集，仅包含两个元素集（集合{a, b}表示a和b之间的边缘。）和权重函数w: E -> IR。