邻接矩阵

一个邻接矩阵是表示有限结构的紧致方法吗图．如果一个图表有 $n$顶点，它的邻接矩阵是 $n \ n$矩阵，其中每一项表示从一个顶点到另一个顶点的边数。

利用图的邻接矩阵可以高效、优雅地实现图论中的一些性质和计算。此外，邻接矩阵的某些性质问题对应于相关图的一些有趣问题。

给定一个图 $G$与 $n$顶点，邻接矩阵是一个 $n \ n$矩阵 $= \ {pmatrix}开始现代{11}&现代{12}& \ cdots &现代{1 n} \ \现代{21}&现代{22}& \ cdots &现代{2 n} \ \ \ vdots & \ vdots & \ ddots & \ vdots \ \现代{n1} &现代{n2} & \ cdots &现代{nn} \ {pmatrix},$的价值 $现代{ij}$等于顶点的边数 $我$的顶点 $j。$如果图形是无向,然后 $现代{ij} =现代{他}$对所有 $i, j。$即邻接矩阵为对称的．

当图简单时，邻接矩阵的项都是 $0$或 $1$(边上没有权值，或者有多条边)对角线项都是 $0$(没有循环)。更复杂的图会产生更多种类的矩阵。

创建一个邻接矩阵为以下加权，无向图:

---

这些边上的权值计入邻接矩阵的条目，如下所示: $= \ {pmatrix}开始0 &3&0&0&0&12&0 \ \ 3 &0&5&0&0&0&4 \ \ 0 &5&0&6&0&0&3 &0&6&0&1&0&0 \ \ \ \ 0 0 12 &0&0&0&10&0&2 &0&0&1&0&10&7 \ \ \ \ 0 &4&3&0&7&2&0 \ {pmatrix}结束。\ _ \广场$

这个例子提出了一些后续问题，将在后面的部分中解决:

• 注意，如果标记不同的顶点，邻接矩阵将会改变。
• 它会怎样变化，新的邻接矩阵和旧的邻接矩阵有什么关系?
• 这种关系能用矩阵语言表达吗?

邻接矩阵是一个数字数组，表示关于图的所有信息。图的一些性质对应于它邻接矩阵的一些有趣的性质，反之亦然。下面是一个简单的例子:

权力:从邻接矩阵的运算中获得图的信息最著名的方法之一是通过它的幂函数。如下面的例子所示，邻接矩阵的幂项给出了图中路径的信息。

让 $一个$是一个具有的简单图的邻接矩阵 $6$顶点。假设进入 $^ 2$在 $3 ^ \文本{rd}$行和 $4 ^ \文本{th}$列是 $5.$这对图表意味着什么?

---

假设 $=(现代{ij})。$然后 $3、4$条目的 $^ 2$是

$现代{31}现代{14}+现代{32}现代{24}+现代{33}现代{34}+现代{34}现代{44}+现代{35}现代{54}+现代{36}现代{64}。$

考虑 $现代{31}现代{14}。$它计算从顶点3到顶点1的路径数，乘以顶点1到顶点4的路径数。这就是从顶点3到顶点4经过顶点1的两步路径的数量。其他条款 $现代{3 k}现代{k4}$计算从顶点3到顶点4经过顶点的两步路径的数量 $k。$所以总和计算了从顶点3到顶点4的所有两步路径。结论是有 $5$从顶点3到顶点4的两步路径。 $_ \广场$

因此, $我,我$条目的 $^ 2$计算两步走的距离 $我$来 $j。$概括如下:

让 $一个$是一个图的邻接矩阵。的 $我,我$条目的 $^ n$计数 $n$-步从顶点走 $我$到顶点 $j。$

$（$证明是一个简单的归纳法 $n,$这个论证本质上和上面给出的是一样的 $^ 2)。$

光谱:的研究特征值图的邻接矩阵的谱图理论．下面是图属性与邻接矩阵特征向量对应的一个简单例子:

无向图是 $k$常规的如果学位每个顶点的 $k。$关于a的邻接矩阵的特征值和特征向量我们能说些什么 $k$正则图吗?

---

让 $一个$是a的邻接矩阵 $k$正则图。让 $v \男朋友$是中的全1列向量 ${} \ mathbb R ^ n。$然后 $我^ \文本{th}$条目的 ${\ bf v}$等于元素的和 $我^ \文本{th}$行 $一个。$这是从顶点发出的边的数量 $我,$这正是 $k。$所以 $A \begin{pmatrix} 1\\1\\\ \vdots\\1 \end{pmatrix} = \begin{pmatrix} k\\k\\\vdots\ k\ end{pmatrix} 1\\1\\\vdots\\1 \end{pmatrix}，$即。 $v \男朋友$特征向量是 $一个$与特征值 $k。$ $_ \广场$

同构:如果一个图可以通过重标记顶点从另一个图得到，则称两个图是同构的。注意同构图不需要有相同的邻接矩阵，因为邻接矩阵依赖于顶点的标记。但同构图的邻接矩阵是密切相关的。

让 $G$而且 $H$图在 $n$顶点邻接矩阵 $一个$而且 $B。$然后 $G$而且 $H$是否同构当且仅当存在置换矩阵 $P$这样 $B = PAP ^{1}。$

回想一下，置换矩阵是一个方阵它的所有项都是 $0$或 $1，$使每一行和每列只包含一个 $1.$

• 图论

• 图- - - - - -中间