标签：关系 图论 end 浅谈 align 矩阵 times

浅谈关系矩阵

什么是关系矩阵

关系矩阵就是用矩阵来表示关系，关系矩阵中的数值皆为**0**或**1**（也就是**bool**型）。

• 举个例子：

\[\begin{vmatrix} 1& 0& 1\\ 0& 0& 1\\ 1& 0& 0 \end{vmatrix} \]

• 这个关系矩阵就表示了3个抽象物体的关系：

\[\begin{vmatrix} 1->1有& 1->2没& 1->3有\\ 2->1没& 2->2没& 2->3有\\ 3->1有& 3->2没& 3->3没\\ \end{vmatrix} \]

• 注意：关系是有向的，也就是说1->2有关系不一定2->1也有关系。

关系矩阵和图论中的邻接矩阵本质上是一样的，所以我们也可以用图论的方式来理解关系矩阵。

关系矩阵的表示

对于元素集合 \(A={a_1,a_2,a_3,...,a_n}\) ,关系\(R\subseteq A\times A\)。

\(R\) 用关系矩阵表示为 \(M(R)=(r_{i,j})_{n\times n}\)

关系矩阵的性质

自身性质

1. 自反性

   关系矩阵主对角线上所有元素的值都为1。在图论中则表示每个点都存在自环。

2. 反自反性

   关系矩阵主对角线上所有元素的值都为0。在图论中则表示每个点都不存在自环。

3. 对称性

   对于 \(\forall {i,j}(i\ne j)\)，关系矩阵D中的元素 \(d_{i,j}\) 与 \(d_{j,i}\) 相等。在图论中则表示为每一条边都为双向边或自环。

4. 反对称性

   对于 \(\forall {i,j}(i\ne j)\)，关系矩阵D中的元素 \(d_{i,j}\) 与 \(d_{j,i}\) 不相等或全为0。在图论中则表示为任意两点之间仅有一条单向边或无边，允许存在自环。

5. 非对称性

   对于 \(\forall {i,j}(i\ne j)\)，关系矩阵D中的元素 \(d_{i,j}\) 与 \(d_{j,i}\) 不相等或全为0，且 \(d_{i,i}\) 等于0。在图论中则表示为任意两点之间仅有一条单向边或无边，无自环。

运算性质

1. 逆运算相关性质

   \(M(R^{-1})=(M(R))^T\)

   关系的逆的关系矩阵等于关系矩阵的逆

2. 合成运算相关性质

   \(M(R_1 \circ R_2)=M(R_2)\bullet M(R_1)\)

   其中 \(\bullet\) 是矩阵的逻辑乘法，运算法则与矩阵乘法类似，逻辑乘法使用 \(\wedge\) 运算，逻辑加法使用 $\vee $ 运算

食用方法及技巧

图论

逻辑矩阵在图论中的应用十分广泛，例如邻接矩阵就是一种逻辑矩阵的拓展，由于应用的实在是太广了，所以就先鸽了这部分。

反演

反演本身就是求两个函数之间的关系，很适合用关系矩阵来推导。

小试牛刀：

我们最常见到的反演关系就是前缀和与差分了，我们尝试用关系矩阵证明一下，设 \(F_n\) 为前缀和，\(G_n\) 为差分，则有：

\[\begin{align*} F_n&=\sum_{i=0}^{n}G_i\\ G_n&=F_n-F_{n-1} \end{align*} \]

我们设 \(A\) 为关系矩阵，用于描述求和关系：

\[\begin{align*} F_{n}&=\sum_{i=0}^{n}G_i\\ &=\sum_{i=0}^{\infty}A_{n,i}G_i\\ \\ F&=G\times A\\ G&=A^T\times F \end{align*} \]

设 \(B\) 为差分关系矩阵：

\[\begin{align*} G_n&=\sum_{i=0}^{\infty}B_{n,i}F_i\\ &=F_n-F_{n-1}\\ G&=F\times B\\ F&=B^T\times G \end{align*} \]

• 上面写的可能有些冗长，目的是为了帮助像我一样的蒟蒻理解，大佬误喷。

那么有

\[\begin{align*} A_{n,i}&=i\le n\\ B_{n,i}&= \end{align*} \]

标签：关系,图论,end,浅谈,align,矩阵,times
From： https://www.cnblogs.com/mjsdnz/p/17566526.html