图空间与赋权图

贡献者：零穹

预备知识　图，向量空间

　　图空间是指定义在图的点集和边集上的函数全体，它们刚好满足向量空间的定义。定义在点集上的函数全体叫做点空间，而定义在边集上的函数全体叫做边空间。赋权图则是在点或边空间中选择一个函数和图组成的二元组，所选的函数叫做权函数，权函数的值叫做对应点或边的权。

1. 图空间

定义 1　点空间，边空间

　　设 $D$ 是一个图，其点集和边集为 $V (D) = {v_{1}, \dots, v_{n}}, E (D) = {a_{1}, \dots, e_{m}}$ 。则定义在 $V (D)$ 上，值域为 $R$ 的函数全体称为 $G$ 的点空间（vertex space），记作 $V (G)$ 。而定义在 $E (D)$ 上，值域为 $R$ 的函数全体称为 $G$ 的边空间（edge space），记作 $E (G)$ 。

习题 1　

　　 $V (G), E (G)$ 上的加法和数乘定义如下：设

\begin{matrix} (1) & f, g \in V (G), x \in V (D) 或 f, g \in E (G), x \in E (D), λ \in R, \end{matrix}

那么

\begin{matrix} (2) & \begin{aligned} (f + g) (x) := f (x) + g (x), \\ (λ f) (x) := λ f (x) . \end{aligned} \end{matrix}

试证明：点空间

V (G)

和边空间

E (G)

满足向量空间的定义。

　　注意到 $\forall f \in V (G)$ 可由在 $V (G)$ 上 $n$ 个点处的取值 $f (v_{1}), \dots f_{(} v_{n})$ 唯一确定，且 $f (v_{i}) = f (v_{i}) \cdot 1$ ，于是若令 $α_{i} (v_{j}) = δ_{i j}, i, j = 1, \dots, n$ ，其中 $δ_{i j}$ 试 Dirac $δ$ 函数。那么

\begin{matrix} (3) & f (v_{j}) = \sum_{i = 1}^{n} f (v_{i}) α_{i} (v_{j}) = (\sum_{i = 1}^{n} f_{i} α_{i}) (v_{j}), \end{matrix}

其中

f_{i} := f (v_{i})

。于是

\begin{matrix} (4) & f = \sum_{i = 1}^{n} f_{i} α_{i} . \end{matrix}

由于

f

的任意性，这表明

{α_{i} | i = 1, \dots, n}

是

V (G)

的一组基。因此，

(f_{1}, \dots, f_{n})

就是

f

在该基下的坐标。

　　同样的，若令 $β_{i} (e_{j}) = δ_{i j}, i, j = 1 \dots, m$ ，则 $\forall g \in E (G)$ ， $g = \sum_{i = 1}^{m} f_{i} β_{i}$ 。即 ${β_{i} | i = 1, \dots, n}$ 是 $E (G)$ 的一组基。而 $(g_{1}, \dots, g_{m})$ 就是 $g$ 在该基下的坐标。

2. 赋权图

定义 2　边赋权图

　　设 $G$ 是图， $ω \in E (G)$ 。则称二元组 $(G, ω)$ 为边赋权图（edge weighted graph）， $ω$ 称为边权函数（edge weighted function）， $ω (a)$ 称为边 $a$ 的权（weigth）。

定义 3　点赋权图

　　设 $G$ 是图， $ω \in V (G)$ 。则称二元组 $(G, ω)$ 为点赋权图（vertex weighted graph）， $ω$ 称为点权函数（vertex weighted function）， $ω (a)$ 称为点 $a$ 的权（weigth）。

定义 4　混合赋权图

　　设 $G$ 是图， $ω_{1} \in V (G), ω_{2} \in E (G)$ 。则称三元组 $(G, ω_{1}, ω_{2})$ 为混合赋权图（mixed weighted graph）， $ω_{1}, ω_{2}$ 分别称为点权和边权函数。

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

图空间与赋权图

1. 图空间

定义 1 点空间，边空间

习题 1

2. 赋权图

定义 2 边赋权图

定义 3 点赋权图

定义 4 混合赋权图

定义 1　点空间，边空间

习题 1　

定义 2　边赋权图

定义 3　点赋权图

定义 4　混合赋权图