图论中的关联矩阵

如果一个矩阵显示一个图，从而帮助我们从它绘制出图，那么它被称为关联矩阵。我们可以用符号 [AC] 来表示关联矩阵。这个矩阵有一些行和列。矩阵 [AC] 的行用于表示图的顶点数量，矩阵 [AC] 的列用于表示图的边数量。

关联矩阵是图分析中一种重要的工具。它主要用于各种应用，如网络流分析、电路分析和连通性分析。

如果一个关联矩阵有 n 行，那么图中必须有 n 个顶点。同样地，如果一个关联矩阵有 n 列，那么图中必须有 n 条边。

在上面的图中，我们有一个有向图，包含 4 个顶点和 4 条边。因此，该图的关联矩阵将有 4 行 4 列。关联 矩阵 遵循 基尔霍夫定律，该定律规定关联矩阵中只能填充 +1、-1 或 0。根据 KCL，在一个 有向图 中，我们可以按以下方式填充关联矩阵的条目

关联矩阵的构建

绘制关联矩阵有一些步骤，如下所示

• 如果给定图中的节点包含出分支，则在关联矩阵中写入 +1。
• 如果给定图中的节点包含入分支，则在关联矩阵中写入 -1。
• 图中除了这两个分支之外的所有其他分支都将在关联矩阵中写入 0。

如何创建关联矩阵

为了理解它，我们将考虑一个图表，并尝试理解如何构建关联矩阵。

在上面的图中，我们有 3 个顶点和 4 条边。因此，关联矩阵将有 3 行 4 列。矩阵的行表示顶点，矩阵的列表示边。在矩阵中，我们在矩阵的两侧添加所有顶点和所有边。在关联矩阵的行中，我们添加顶点名称，在关联矩阵的列中，我们添加边名称。

在下面的矩阵中，我们从一个空矩阵开始，只添加顶点和边名称，如下所示

现在我们可以填充上面的关联矩阵，查看顶点和边的名称，并尝试确定它们对应的关系。假设该图的顶点通过一条边连接。在这种情况下，我们计算连接到该顶点的边所连接的总腿数，完成计数后，我们将此数字作为矩阵元素。

有两种方法可以填充矩阵，即按列或按行。在我们的示例中，我们将使用按行方法。现在，我们考虑图中的每个顶点，并检查用于连接到该顶点的边。

在上面的图中，首先，我们考虑顶点 a。共有 2 条边 e1 和 e2 用于连接到顶点 a。因此，我们将 e1 和 e2 的位置填充数字 1。现在，我们使用这些数字并尝试按以下方式填充矩阵

同样，顶点 b 通过总共 2 条边 e1 和 e3 连接，因此我们将 e1 和 e3 的位置填充数字 1。现在，我们使用这些数字并尝试按以下方式填充矩阵

现在，顶点 c 通过总共 3 条边 e2、e3 和 e4 连接，因此我们将 e2、e3 和 e4 的位置填充数字 1。现在，我们使用这些数字并尝试按以下方式填充矩阵

现在，我们已经考虑了所有顶点，并且没有剩余顶点。矩阵中所有剩余的未填充单元格都将填充为 0。上述图的完整矩阵可以显示如下

现在，我们尝试绘制另一个图的关联矩阵，如下图所示

上述图的关联矩阵可以按以下方式绘制

关联矩阵中的自环和多重边

在关联矩阵的情况下，可以显示自环和多重边。多重边可以通过关联矩阵中具有相同条目的列来表示。在多重边的情况下，这些边通过相同的顶点对关联。图的自环可以通过条目为 1 的列来表示。我们可以通过一个例子来理解自环和多重边，如下所述

这个图包含 5 个顶点和 8 条边，因此关联矩阵将有 5 行 8 列。该图的关联矩阵可以按以下方式写入

一些重要术语

在学习关联矩阵概念时，有一些重要术语很有用。

关联矩阵： 我们可以将关联矩阵描述为用于显示图的矩阵。关联矩阵的行表示图的顶点或节点，关联矩阵的列表示图的边或分支。

矩阵条目： 如果图中存在入边，则在关联矩阵中记为 -1。如果图中存在出边，则在关联矩阵中记为 +1。所有其他分支或边都将记为 0。

构建步骤： 如果我们要构建关联矩阵，则对于出边分配 +1，对于入边分配 -1，对于其他边分配 0。

简化关联矩阵： 我们可以通过从关联矩阵中删除任何一行来生成简化关联矩阵。

正确性检查： 我们可以通过检查每列的总和是否为 0 来检查绘制的矩阵是否正确。

关联矩阵的示例

关联矩阵中有很多示例，其中一些示例如下所示

示例 1

此示例包含一个图，我们需要找到它的关联矩阵。

这个图包含 4 个顶点和 6 条边，因此关联矩阵将有 4 行 6 列。该图的关联矩阵可以按以下方式写入

示例 2

此示例包含一个图，我们需要找到它的关联矩阵。

这个图包含 6 个顶点和 8 条边。因此，该图的关联矩阵将有 6 行 8 列。该图的关联矩阵可以按以下方式写入

示例 3

此示例包含一个图，我们需要找到它的关联矩阵。

示例 4

此示例包含一个图，我们需要找到它的关联矩阵。

这个图包含 4 个顶点和 5 条边。因此，该图的关联矩阵将有 4 行 5 列。该图的关联矩阵可以按以下方式写入

示例 5

此示例包含一个图，我们需要找到它的关联矩阵。

这个图包含 4 个顶点和 3 条边。因此，该图的关联矩阵将有 4 行 3 列。该图的关联矩阵可以按以下方式写入

简化关联矩阵

如果通过从关联矩阵中删除任何一行来获得矩阵，则该矩阵称为简化关联矩阵。换句话说，我们通过从 [A_C] 中删除任何一行来获得新生成的矩阵或简化关联矩阵。我们可以用符号 [A] 来表示简化关联矩阵。在简化关联矩阵中，总共有 (n-1) 行和 b 列，其中 n 用于表示图的顶点数量，b 用于表示图的边数量。简化关联矩阵用于简化矩阵，这可以进一步用于降低计算的复杂性，尤其是在网络分析的情况下。

如果我们要获得简化关联矩阵，我们首先必须绘制关联矩阵。之后，我们可以从关联矩阵中删除任何一行，从而获得简化关联矩阵。我们可以通过一个例子来理解简化关联矩阵。

在此示例中，我们有一个关联矩阵，我们需要找到简化关联矩阵。

我们可以按以下方式绘制该图的关联矩阵

[A_C]

现在，我们从上面的关联矩阵中删除节点 3。从 [A_C] 中删除节点 3 后的简化关联矩阵可以按以下方式绘制

[A]

简化关联矩阵的应用

简化关联矩阵有很多应用。在这里，我们将介绍一些用于电气工程、网络分析或 图论 领域的内容。

这些应用如下所示

电路分析： 我们可以在电路领域使用简化关联矩阵，这样可以轻松简化网络分析。它用于降低电路的复杂性，可用于查找网络中的电流流动和电压电位。

生成树计算： 我们可以在生成树领域使用简化关联矩阵。它可用于查找给定图中 生成树 的数量。简化关联矩阵在 ST 中还有其他用途，即优化问题和网络设计。

连通性： 我们可以在网络连通性情况下使用简化关联矩阵。它可用于查找网络的连接强度，并且它还查找网络是否包含任何断开的部分。

流网络分析： 我们可以在建模网络流的情况下使用简化关联矩阵。它可用于分析网络中的信息流。

完整关联矩阵的属性

完整关联矩阵有很多属性，其中一些属性如下所示

连通性： 借助关联矩阵，可以轻松判断给定图是连通的还是非连通的。如果矩阵中包含所有必要的边，则该图是连通的。

稀疏性： 关联矩阵通常是稀疏的。这是因为关联矩阵的大多数条目都是零。零条目用于表示顶点和边之间没有连接。

大小和结构： 如果一个图包含 n 个顶点和 m 条边，则关联矩阵将是一个 n*m 矩阵。

有向图中的对称性： 如果存在有向图，则矩阵的条目表示边的方向。由于这个原因，只要图是无向的，矩阵就不对称。

当我们从关联矩阵中删除一行和一列以形成简化关联矩阵时，所有上述属性都得以保留。但是，在简化关联矩阵的情况下，矩阵变得更易于管理。

简化关联矩阵的示例

简化关联矩阵包含很多示例，其中一些示例如下所示

示例 1

此示例包含一个图，我们需要找到该图的简化关联矩阵。

解决方案： 我们可以按以下方式绘制该图的关联矩阵

[A_C]

现在，我们从上面的关联矩阵中删除节点 1。从 [A_C] 中删除节点 1 后的简化关联矩阵可以按以下方式绘制

示例 2

此示例包含一个图，我们需要找到该图的简化关联矩阵。

解决方案： 我们可以按以下方式绘制该图的关联矩阵

[A_C]

现在，我们从上面的关联矩阵中删除节点 v5。从 [A_C] 中删除节点 v5 后的简化关联矩阵可以按以下方式绘制

[A]

示例 3

此示例包含一个图，我们需要找到该图的简化关联矩阵。

解决方案： 我们可以按以下方式绘制该图的关联矩阵

[A_C]

现在，我们从上面的关联矩阵中删除节点 v2。从 [A_C] 中删除节点 v2 后的简化关联矩阵可以按以下方式绘制

[A]

示例 4

此示例包含一个图，我们需要找到该图的简化关联矩阵。

解决方案： 我们可以按以下方式绘制该图的关联矩阵

[A_C]

现在，我们从上面的关联矩阵中删除节点 C。从 [A_C] 中删除节点 C 后的简化关联矩阵可以按以下方式绘制

[A]

要点

在学习关联矩阵的概念时，有一些要点可以帮助您轻松理解这个概念。

这些要点如下所述

• 如果我们想检查绘制的矩阵是否正确，那么我们需要检查列的总和。
• 在进行列求和时，如果结果为 0，则表示创建的关联矩阵是正确的。如果求和时得到除 0 以外的任何其他矩阵，则关联矩阵不正确。
• 关联矩阵的列和只能针对有向图进行检查。
• 我们可以通过计算一行中除了 0 之外的所有条目的数量来计算任何顶点的分支数量。我们也可以将顶点的分支数量称为该顶点的度。
• 如果我们有一个完整的关联矩阵，那么它的秩总是 (n-1)，其中 n 可以用来表示图的顶点数量。
• 如果我们有一个关联矩阵，该矩阵的阶数总是 (n*b)，其中 b 可以用来表示图的分支数量。
• 可以通过简化关联矩阵绘制完整的关联矩阵。为此，我们只需添加 -1、0 或 +1，使得每列的总和为 0。