第五部分图论

为了用矩阵表示图，必须制定顶点或边的顺序，使其称为标定图。解释：没有二义性。

本节讨论：

        关联矩阵（无向图和有向图）

        邻接矩阵（Adjacent matrix有向图）

        可达矩阵（Accessibility matrix有向图）

14.4.1关联矩阵（无向图和有向图）

无向图关联矩阵：描述的是点和边的关联次数关系，即 $v_{i}$ 与 $e_{j}$ 的关联次数。

$M(G)=\begin{bmatrix} 2& 1& 1& 1& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 1 \end{bmatrix}$ [ToDo: 插图14.15]

M(G)有以下性质：

$\sum_{j=1}^{n}mij=2 (j=1,2,3,...,m)$ ,即每列元素之和均为2。因为每条边必有两个端点(即使是环，也是始末两个点)。
第 $i$ 行元素之和为 $v_{i}$ 的度数。
符合握手定理，即各顶点度数之和等于边数的2倍。即所有项之和等于2m。
第 $j$ 列与第 $k$ 列相同当且仅当边 $e_{j}$ 与 $e_{k}$ 是平行边。
$\sum_{j=1}^{n}mij=0$ 当且仅当 $v_{i}$ 是孤立点(即某一行全是零，也就没有边相邻的点)。

有向图关联矩阵：描述的是点和边的始末关联关系（即始点、终点、不关联）。

$m_{ij}=\left\{\begin{matrix} 1,& v_{i} 是e_{j}的始点\\ 0,& v_{i}与e_{j}不关联\\ -1,& v_{i}是e_{j}的终点\\ \end{matrix}\right.$

$M(G)=\begin{bmatrix} -1& 1& 0& 0& 0\\ 1& -1& 1& 0& 0\\ 0& 0& 0& 1& 1\\ 0& 0& -1& -1& -1 \end{bmatrix}$

M(D)有以下性质：

每一列恰好有一个+1和一个-1，因为一个有向边必然有一个始点和一个终点。
+1的个数等于-1的个数等于边数m，根据握手定理可知。
行的+1个数等于 $d^{+}( v_{i})$ ,-1的个数等于 $d^{-}( v_{i})$ 。
若存在平行边，那么平行边所对应的列相同。注：有向图的平行边始末点相同。

14.4.2有向图的邻接矩阵（Adjacent matrix有向图）

有向图邻接矩阵：描述的是点与点之间的边关系（两点之间有几条特定长度的边）。

$A=(a_{ij}^{(1)})_{n\times n}=\begin{bmatrix} 0 & 2 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 \end{bmatrix}$ 点与点之间边长为1的边的个数关系。

A有以下性质：

$v_{i}$ 行边数之和等于 $d^{+}(v_{i})$ ，一行之和表示某个点的出度数。
$v_{i}$ 列边数之和等于 $d^{-}(v_{i})$ ，一列之和表示某个点的入度数。
$\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}^{(1)}=\sum_{i=1}^{n}d^{+}(v_{i})=m$ 同1
$\sum_{j=1}^{n}\sum_{i=1}^{n}a_{j}^{(1)}=\sum_{j=1}^{n}d^{-}(v_{j})=m$ 同2
3和4符合有向图的握手定理。
$\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}^{(l)}$ 为D中长度为l的通路(含回路)总数。注：A中默认l=1
$\sum_{i=1}^{n}a_{ii}^{(l)}$ 为D中长度为l的回路总数。
6和7说的是A中的对角线值。

因为邻接矩阵的计算设计边长 $l$ ,所以邻接矩阵就涉及 $l=1,2,3,4,n$ 的 $A^{n}$ 计算。

方法1：参考图进行计算得出，该方法比较挫，要识别图中的环。容易眼花出错。

方法2：根据矩阵乘法进行计算(参考线性代数矩阵乘积)

         $A^{1} = \begin{pmatrix} 0 & 2 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 \end{pmatrix}$

         $A^{2} = \begin{pmatrix} 0 & 2 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 2 & 1 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 \end{pmatrix}=\begin{pmatrix} 0 & 0 & 2 & 1\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 2 \end{pmatrix}$

   $A^{2}$ 中的 $V_{ij}$ = $A^{1}$ 的行乘以 $A^{1}$ 求和，即行1X列1+行2X列2+行2X列2+行2X列2之和。

         $A^{3}=A^{2}\times A^{1} \\ A^{4}=A^{3}\times A^{1}$

14.4.3有向图的可达矩阵（Accessibility matrix有向图）

有向图可达矩阵,描述的是点与点之间联通关系，联不联通（两点之间在特定长度是否联通）。

$p_{ij}=\begin{Bmatrix} 1,&v_{i}可达v_{j}\\ 0,&否则 \end{Bmatrix}$

可达矩阵约定每个顶点到自身都是可达的。

$P_{1}=\begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{pmatrix}$ $P_{2}=\begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{pmatrix}$

特点对角线都为1，可以根据邻接矩阵推算出来。

14.5图的运算

书本中定义：通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。

通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。

具有欧拉回路的图称为为欧拉图。

具有欧拉通路而无欧拉回路的图称为为半欧拉图。

我的理解：走不重复的路，经过所有的顶点形成通路或回路。欧拉图谈的是边的关系。

平凡图是欧拉图。只有一个顶点，没有边的图。

第15章欧拉图与哈密顿图

15.1欧拉图

欧拉图以边为中心讨论图

定义：

平凡图是哈密顿图也是欧拉图。

15.2哈密顿图

哈密顿图以点为中心讨论图

定义：经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。

经过图中所有顶点一次且仅一次的回路称为哈密顿回路。

具有哈密顿回路的图称为哈密顿图。

具有哈密顿通路但不具有哈密顿回路的图称为班哈密顿图。

平凡图是哈密顿图也是欧拉图。

补充说明：

带1度顶点的图无哈密顿回路；
若图中有2度顶点，则关联这个顶点的两条边属于任意一条哈密顿回路；
当构造哈密顿回路且该回路经过某一顶点时除了回路所用的两条边，不用再考虑这个顶点关联的其它边；
哈密顿回路不能包含更小的回路；
若图中某些必须出现在哈密顿回路中的边已构成回路，而图中尚有不在该回路中的点，则此图不是哈密顿图。

哈密顿图于半哈密图的判定：

结论1：不满足 $p\left ( G - V_{1} \right ) \leqslant \left | V_{1} \right |$ 则不是哈密顿图

推论1：满足 $p\left ( G - V_{1} \right ) \leqslant \left | V_{1} \right |+1$ 则是半哈密顿图

推论2：（1）若G是哈密顿图，则 $\left | V_{1} \right | = \left | V_{2} \right |$

（2）若G是半哈密顿图，则 $\left | V_{2} \right | = \left | V_{1} \right |+1$

（3）若 $\left | V_{2} \right | \geqslant = \left | V_{1} \right |+2$ ，则G不是哈密顿图，也不是半哈密顿图

定理：G是n阶无向简单图，若对于G中任意不相邻的顶点 $v_{i}$ , $v_{j}$ 均有

$d(v_{i})+d(v_{j})\geqslant n -1$

则G中存在哈密顿通路。

推论：设G为n（ $n\geqslant 3$ ）阶无向简单图，若对于G中任意两个不相邻的顶点 $v_{i}$ , $v_{j}$ 均有

$d(v_{i})+d(v_{j})\geqslant n$

则G中存在哈密顿回路，从而G为哈密顿图。

15.3最短路问题、中国邮递员问题与货郎担问题

乐奇 Rokid 开放社区

更多推荐

AI 日报（2026年9月24日）

2026年9月24日，AI技术与应用呈现多元化演进态势。硬件与端侧方面，Meta在Connect大会发布首款轻量化VR眼镜与无摄像头智能眼镜，全面接入Muse智能体；谷歌上线Gemini 3.8 Flash TTS可定制语音模型，并在DeepMind推动私密计算与服务端内存融合。行业与前沿科研领域，Anthropic湿实验实验室利用Claude发现CRISPR样新型酶系统，并推出一站式Claude

乐奇 Rokid 开放社区

面向逻辑思维的程序设计方法——人形机器人最佳训练场景

乐奇 Rokid 开放社区

AI行业日报｜2026-09-25：5个热点事件

本期行业动态聚焦于端侧算力重构、自主智能体工作流、开发工具经济模型、网络隔离架构设计与公共部门合规审查。以下结合一线技术场景进行结构化梳理，供 AI 研究员与软件工程团队参考。 PrismML 正将其轻量级语言模型适配至搭载高通处理器的智能眼镜终端 1 。该平台的核心战略指向开源权重模型的本地化运行，旨在最大化挖掘穿戴设备现有算力的利用效率 1 。对于嵌入式与边缘计算开发者而言，此类微型模型向低功