第一章 图的基本概念

1.1 图和简单图

图的定义

★图

一个图 $G=(V,E)$, 其中:
(1) $V$ 是一个有限的非空集合, 称为顶点集合, 其元素称为顶点或点 (vertex). 用 $|V|$ 表示顶点数;
(2) $E$ 是由V中的点组成的无序对构成的”集合”, 称为边集, 其元素称为边 (edge), 且同一点对在 $E$ 中可以重复出现多次, 用 $|E|$ 表示边数.

注:
(1) Sylvester (1814-97) 于1878年在 ”Chemistry and Algebra” 一文中首次使用 ”Graph” 作为术语.
(2) 图可以用图形表示: $V$ 中的元素用平面上一个实心点或者小圆圈表示(位置无关的), $E$ 中的元素用一条连接 $V$ 中相应点对的任意的线(曲直, 长短等无关)表示.

对于图 $G$:
$m(G)$ 表示图的边数;
$n(G)$ 表示图的顶点数.

图的相关概念

有限图 (finite graph): 顶点集和边集都有限的图称为有限图;

平凡图 (trivial graph): 只有一个顶点的图称为平凡图;

零图 (null graph): 顶点集为空(边集随之为空)的图;

空图 (empty graph): 边集为空(顶点集非空)的图称为空图;

$n$ 阶 (order) 图 : 顶点数为 $n$ 的图称为 $n$ 阶图;

$(n,m)$ 图: 顶点数为 $n$, 边数为 $m$ 的图称为 $(n,m)$ 图;

边的重数 (multiplicity): 连接两个相同顶点的边的条数称为边的重数; 重数大于 1 的边称为 重边 (multiple/parallel edge);

自环 (loop): 端点重合为一点的边称为自环;

多重图 (multigraph): 包含重边 (但不包含自环) 的图;

★简单图 (simple graph): 无自环无重边的图称为简单图(或单图).

注: 简单图并不“简单”.

顶点与边的关系

顶点 $u$ 与 $v$ 相邻或邻接 (adjacent): 顶点 $u$ 与 $v$ 间有边相连接, 记为 $u\leftrightarrow v$; 其中 $u$ 与 $v$ 称为该边的两个端点 ; 简单图中, 包含一个点 $v$ 所有邻点的集合称作 $v$ 的邻域 (neighborhood), 记作 $N(v)$.

边 $e_1$ 与边 $e_2$ 邻接: $e_1$ 与 $e_2$ 有公共端点.

顶点 $u$ 与边 $e$ 相 关联 (incident): 顶点 $u$ 是边 $e$ 的端点.

图的同构

★图的同构 $\cong$

设两个简单图 $G_1=(V_1,E_1)$ 和 $G_2=(V_2,E_2)$, 若在其顶点集合间存在双射, 使得边之间存在如下关系: 设$u_1\leftrightarrow u_2$ , $v_1\leftrightarrow v_2$, $u_1,v_1\in V_1$ , $u_2,v_2\in V_2$; $u_1{v}_1\in E_1$, 当且仅当 $u_2{v}_2\in E_2$ (非简单图还要求 $u_1{v}_1$ 与 $u_2{v}_2$ 的重数相同). 称 $G_1$ 与 $G_2$ 同构 (isomorphism), 记为: $G_1\cong G_2$.

图同构的几个必要条件

由定义可以得到图同构的几个必要条件:

• (1)顶点数相同;
• (2)边数相同;
• (3)关联边数相同的顶点个数相同.

判定同构

注:
(1) 子图同构问题是 NP-完全的;
(2) 判定一般图的两个图是否同构普遍认为是困难的,是否存在 (或不存在) 多项式时间算法仍然是公开的(open problem). 多数学者认为它是 NP 问题中 NPI 的 (既非 P 又非 NP-完全的)可能候选对象.

对于规模不大的两个图, 判定其是否同构, 可以采用观察加推证的方法.

注: 化学家常用图同构方法来研究同一类分子的结构是否相同. 如烷烃的枚举.

注: 当图的阶数较大时, 枚举不再是好的方法.

例

证明下面两图不同构.

证明: $u_1$ 的两个邻接点与 $v_1$ 的两个邻接点状况不同. 所以, 两图不同构.

例

证明下面两图同构.

证明: 作映射 $f:v_i\mapsto u_i(i=1,2\dots .10)$.

容易证明, $v_i{v}_j\in E(G)$, 当且仅当 $f(v_i)f(v_j)=u_i{u}_j\in E(H)(1\le i\le 10,1\le j\le 10)$.

由定义知, 图 $G$ 与 $H$ 是同构的.

例

给出 $4$ 个顶点的非同构的所有简单图.

分析: 四个顶点的简单图边数最少为0, 最多为6, 所以可按边数进行枚举 (In fact, brute-force approach is sufficient for small n).

注:
(1) 非标号图(即顶点不固定)的不同构图的个数增长见: http://oeis.org/A000088.
(2) 标号的非同构图的个数增长见:http://oeis.org/A000273.

完全图、二部图与补图

完全图 $K_n$

每两个不同的顶点之间都有一条边相连的简单图称为完全图 (complete graph).

在同构意义下, $n$ 个顶点的完全图只有一个, 记为 $K_n$.

容易求出: $m(K_n)=\frac{1}{2}n(n-1)$.

★二部图 / 偶图

所谓具有二分类 $(X,Y)$ 的二部图或偶图(bipartite graph)是指一个图, 它的点集可以划分为两个非空子集 $X$ 和 $Y$, 使得每条边的一个端点在 $X$ 中, 另一个端点在 $Y$ 中.

完全二部图

完全二部图 (complete bipartite graph) 是指具有二分类 $(X,Y)$ 的简单二部图, 其中 $X$ 的每个顶点与 $Y$ 的每个顶点相连, 若 $|X|=m$ , $|Y|=n$, 则这样的完全二部图记为 $K_{m,n}$. 特别地, $K_{1,3}$也被称作爪 (claw), $K_{1,s}$ $(s\ge 1)$ 也被称作星 (star).

★补图

对于一个简单图 $G=(V,E)$, 令集合 $E_1=\{uv|u\ne v,u,v\in V\}$, 则称图 $H=(V,E_1\backslash E)$ 为 $G$ 的补图 (complement graph), 记为 $H=\overline{G}$.

补图是相对于完全图定义的.

注: 完全图 $G$ 与以 $V(G)$ 为顶点集的空图 (也叫独立集, independent set) 互为补图.

补图是图论中经常涉及的概念, 在图论研究中有重要的作用.

★自补图

如果图 $G$ 与其补图同构, 则称 $G$ 为自补图 (self-complementary graph).

★自补图的性质

定理: 若 $n$ 阶图 $G$ 是自补图 ( $G\cong \overline{G}$ ), 则有: $n=0,1(\mathrm{m}\mathrm{o}\mathrm{d}4)$

证明: $n$ 阶图 $G$ 是自补图, 则有:

$$m(G)+m(\overline{G})=m(K_n)=\frac{1}{2}n(n-1)$$

所以:

$$m(G)=\frac{1}{4}n(n-1)$$

由于 $n$ 是正整数, 所以: $n=0,1(\mathrm{m}\mathrm{o}\mathrm{d}4)$

自补图是很有意义的图类. 它在对角型 Ramsey 数、图的香农容量的研究、强完美图方面的研究等都有重要作用.

例

在 $10$ 个顶点以下的简单图中, 哪些阶数的图可能为自补图? 画出 $8$ 阶的 $4$ 个自补图(共10个).

https://mathworld.wolfram.com/Self-ComplementaryGraph.html

解: $1,4,5,8,9$ 阶的图可能为自补图.

顶点的度与图的度序列

顶点的度 $d(v)$

$G$ 的顶点 $v$ 的度 $d(v)$ 是指 $G$ 中与 $v$ 关联的边的数目, 每个环计算两次.

分别用 $\delta (G)$ 和 $\Delta (G)$ 表示图 $G$ 的最小与最大度.

奇数度的点称为奇度点, 偶数度的顶点称偶度点.

$k$-正则图

设$G=(V,E)$, 如果对所有 $v\in V$ , 有 $d(v)=k$, 称图 $G$ 为 $k$-正则图 ($k$-regular). 3 正则图也称为 3 次图 (cubic).

★图论第一定理 / 握手定理

图 $G=(V,E)$ 中所有顶点的度的和等于边数 $m$ 的 $2$ 倍, 即:

$$\sum _{v\in V(G)}d(v)=2m$$

证明: 由顶点度的定义知: 图中每条边给图的总度数贡献 $2$ 度, 所以, 总度数等于边数 $2$ 倍.

注: 该定理称为图论第一定理, 1736 年由欧拉提出的. 欧拉一生发表论文 886 篇, 著作 90 部. 该定理还有一个名字: “握手定理”.

★推论1

在任何图中, 奇度点的个数为偶数.

证明: 设 $V_1$, $V_2$ 分别是 $G$ 中奇点集和偶点集. 则由握手定理有:

$$\sum _{v\in V_1}d(v)+\sum _{v\in V_2}d(v)=\sum _{v\in V}d(v)$$

是偶数, 由于 ${\sum }_{v\in V_2}d(v)$ 是偶数, 所以 ${\sum }_{v\in V_1}d(v)$ 是偶数, 于是 $|V_1|$ 是偶数.

★推论2

正则图的阶数和度数不同时为奇数.

证明: 设 $G$ 是 $k$-正则图, 若 $k$ 为奇数, 则由推论 1 知正则图 $G$ 的点数必为偶数.

例

$\Delta$ 与 $\delta$ 是简单图 $G$ 的最大度与最小度, 求证:

$$\delta \le \frac{2m}{n}\le \Delta$$

证明: 由握手定理有:

$$n\delta \le \sum _{v\in V(G)}d(v)=2m\le n\Delta$$

所以有:

$$\delta \le \frac{2m}{n}\le \Delta$$

★图的度序列及其性质

一个图 $G$ 的各个点的度 $d_1,d_2,\dots ,d_n$ 构成的非负整数组 ($d_1,d_2,\dots ,d_n$) 称为 $G$ 的度序列 (degree sequence).

任意一个图 $G$ 对应唯一一个度序列, 图的度序列是刻画图的特征的重要“拓扑不变量”, 反应了图的整体性质.

图的度序列有下面的性质:

• 图的度序列与顶点的顺序无关.
• 同构的所有图具有相同的度序列(反之不成立).

★定理

非负整数组 ($d_1,d_2,\dots ,d_n$) 是图的度序列的充分必要条件是: ${\sum }_{i=1}^n{d}_i$ 为偶数.

证明:

必要性由握手定理立即得到.

如果 ${\sum }_{i=1}^n{d}_i$ 为偶数, 则数组中为奇数的数字个数必为偶数. 按照如下方式作图 $G$:

• 若 $d_i$ 为偶数, 则在与之对应的点作 $\frac{d_i}{2}$ 个环;
• 对于剩下的偶数个奇数 $d_i$ , 两两配对后分别在每配对点间先连一条边, 然后在每个顶点画 $\frac{d_i-1}{2}$ 个环.

该图的度序列就是已知数组.

★图的图序列

一个非负数组如果是某简单图的度序列, 我们称它为可图序列 (graphic sequence), 简称图序列.

关于图序列, 主要研究 3 个问题:

• (1) 存在问题: 什么样的整数组是图序列？
• (2) 计数问题: 一个图序列对应多少不同构的图？
• (3) 构造问题: 如何画出图序列对应的所有不同构图？

研究现状: (1)彻底解决了, (2)解决得不完整, (3)没有解决.

★定理 (Havel 1955, Hakimi 1962)

非负整数组

$$\pi =(d_1,d_2,\dots ,d_n),d_1\ge d_2\ge \dots \ge d_n,\sum _{i=1}^n{d}_i=2m$$

是图序列的充分必要条件是:

$${\pi }_1=(d_2-1,d_3-1,\dots ,d_{d_1+1}-1,d_{d_1+2},\dots ,d_n)$$

是图序列.

注: ${\pi }_1$ 是从 $\pi$ 中删去 $d_1$ ,然后对后面连续的 $d_1$ 个点的度均减 $1$ 后得到.

定理

一个简单图 $G$ 的 $n$ 个点的度不能互不相同.

证明: 因为图 $G$ 为简单图, 所以: $\Delta (G)\le n-1$.

情形1: 若 $G$ 没有孤立点, 则

$$1\le d(v)\le n-1,\forall v\in V(G)$$

由鸽笼原理: 必有两顶点度数相同;

情形2: 若 $G$ 只有一个孤立点, 设 $G_1$ 表示 $G$ 去掉孤立点后的部分, 则:

$$1\le d(v)\le n-2,\forall v\in V(G_1)$$

由鸽笼原理: 在 $G_1$ 里必有两顶点度数相同;

情形3: 若 $G$ 只有两个以上的孤立点, 则定理显然成立.

频序列

设 $n$ 阶图 $G$ 的各点的度取 $s$ 个不同的非负整数 $d_1,d_2,\dots ,d_s$. 又设度为 $d_i$ 的点有 $b_i$ 个 $(i=1,2,\dots ,s)$, 则

$$\sum _{i=1}^s{b}_i=n$$

故非整数组 $(b_1,b_2,\dots ,b_s)$ 是 $n$ 的一个划分, 称为 $G$ 的频序列.

定理

一个 $n$ 阶图 $G$ 和它的补图有相同的频序列.

1.2 子图与图的运算

★子图

简单地说, 图 $G$ 的任意一部分 (包括本身) 都称为是图 $G$ 的一个子图.

定义: 如果 $V(H)\subseteq V(G),E(H)\subseteq E(G)$ 且 $H$ 中边的重数不超过 $G$ 中对应边的条数, 则称 $H$ 为 $G$ 的子图 (subgraph), 记为 $H\subseteq G$.

当 $H\subseteq G,H\ne G$ 时, 称 $H$ 是 $G$ 的真子图 (proper subgraph), 记为 $H\subset G$.

顶点导出子图

定义: 如果 $V^{\prime }\subseteq V(G)$ , 则以 $V^{\prime }$ 为顶点集,以两个端点均在 $V^{\prime }$ 中的边集组成的子图, 称为图 $G$ 的点导出子图 (induced subgraph). 记为: $G[V^{\prime }]$.

注: 事实上, $G[V^{\prime }]=G-\overline{V^{\prime }}$ .

边导出子图

定义: 如果 $E^{\prime }\subseteq E(G)$ , 则以 $E^{\prime }$ 为边集, 以 $E^{\prime }$ 中边的所有端点为顶点集组成的图, 称为图 $G$ 的边导出子图 (edge-induced subgraph). 记为: $G[E^{\prime }]$.

图的生成子图

定义: 如果图 $G$ 的一个子图包含 $G$ 的所有顶点, 称该子图为 $G$ 的一个生成子图 (spanning subgraph).

定理: 简单图 $G=(n,m)$ 的所有生成子图个数为 $2^m$.

图运算

在图论中, 将两个或更多的图按照某种方式合并, 或者对一个图作某种形式的操作, 可以得到很有意义的新图. 将图合并或对一个图进行操作, 称为图运算.

图的删点、删边运算 (deletion) $-$

设 $V^{\prime }\subseteq V(G)$, 在 $G$ 中删去 $V^{\prime }$ 中的顶点和 $G$ 中与之关联的所有边的操作, 称为删点运算. 记为 $G-V^{\prime }$.

特别地, 如果只删去一个点 $v$ , 则记为 $G-v$.

判词: 点之不存, 边将焉附!

设 $E^{\prime }\subseteq E(G)$, 在 $G$ 中删去 $E^{\prime }$ 中的所有边的操作, 称为删边运算. 记为 $G-E^{\prime }$.

特别地, 如果只删去一条边 $e$, 则记为 $G-e$.

判词: 点若磐石, 不为边动!

注: 删点、删边后得到的图均是原图的子图.

图的并 (union) $\cup$ / 不交并 $+$

设 $G_1$, $G_2$是 $G$ 的两个子图, $G_1$ 与 $G_2$ 并是指以 $V(G_1)\cup V(G_2)$ 为顶点集, 以 $E(G_1)\cup E(G_2)$ 为边集组成的子图. 记为: $G_1\cup G_2$.

特别地, 如果 $G_1$, $G_2$ 不相交 (没有公共顶点), 称它们的并为不交并, 可以记为: $G_1+G_2$.

图的交 (disjoint) $\cap$

设 $G_1$, $G_2$是 $G$ 的两个子图, $G_1$ 与 $G_2$ 交是指由 $V(G_1)\cap V(G_2)$ 为顶点集, 以 $E(G_1)\cap E(G_2)$ 为边集组成的子图. 记为: $G_1\cap G_2$.

图的差 (difference) $-$

设 $G_1$, $G_2$ 是两个图, $G_1$ 与 $G_2$ 的差是指从 $G_1$ 中删去 $G_2$ 中的边得到的新图. 记为 $G_1-G_2$.

图的对称差 (symmetric difference) / 异或(XOR) $△$

设 $G_1$, $G_2$ 是两个图, $G_1$ 与 $G_2$ 的对称差定义为:

$$G_1△G_2=(G_1\cup G_2)-(G_1\cap G_2)$$

注: 仅包含那些恰好在 $G_1$ 或 $G_2$ 出现一次的边, 而不包含在 $G_1$ 和 $G_2$ 中都出现的边.

★图的联 (join) $\vee$

设 $G_1$, $G_2$ 是两个不相交的图, 作 $G_1+G_2$, 并且将 $G_1$ 中每个顶点和 $G_2$ 中的每个顶点连接, 这样得到的新图称为 $G_1$ 与 $G_2$ 的联图. 记为: $G_1\vee G_2$

★Cartesian 积图 (Cartesian product) $\square$

设 $G_1=(V_1,E_1),G_2=(V_2,E_2),$ 是两个图. 对点集 $V=V_1\times V_2$ 的任意两个点 $u=(u_1,u_2)$ 与 $v=(v_1,v_2)$, 若:
(1) $u_1=v_1$ 和 $u_2\leftrightarrow v_2$, 或者
(2) $u_2=v_2$ 和 $u_1\leftrightarrow v_1$ 时,
$u$ 与 $v$ 相连. 如此得到的图称为 $G_1$ 与 $G_2$ 的积图. 记为 $G_1\square G_2$.

教材中 adj 是 adjacent 的缩写, 表示相邻.

记号 $\square$ 是由捷克数学家 Jaroslav Nešetřil 给出.

注:

• (1) Cartesian 积是构造新图的一种重要方法. 且 Cartesian 积对图的一些性质保持很好. 如 $G_1\square G_2$ 和$G_2\square G_1$ 同构 ($\square$ 可交换顺序); 若 $G_1,G_2$ 正则 (二部, 点传递, 欧拉, 哈密尔顿, $k$-连通等), 则 $G_1\square G_2$ 亦然).
• (2) Cartesian 积的符号 $\square$ 隐含将 $G_1$ 复制 $|G_2|$ 次后将对应顶点水平或者竖直相连. 例如 $K_2\square K_2=C_4$.
• (3) 互连网络中需要一些对称性好的图(路由算法易设计), 往往用 Cartesian 积构造.

★图的合成 (composition) / 字典积 (lexicographic product) $G_1[G_2]$

设 $G_1=(V_1,E_1),G_2=(V_2,E_2),$ 是两个图. 对点集 $V=V_1\times V_2$ 的任意两个点 $u=(u_1,u_2)$ 与 $v=(v_1,v_2)$, 当
(1): $u_1\leftrightarrow v_1$, 或
(2): $u_1=v_1$ 和 $u_2\leftrightarrow v_2$ 时,
连接 $u$ 与 $v$. 如此得到的图称为 $G_1$ 与 $G_2$ 的合成图. 记为 $G_1[G_2]$.

注:

• (1) 合成图 $G_1[G_2]$ 也可以定义为将 $G_1$ 的每个顶点用 $G_2$ 的一个拷贝代替, $G_1$ 中的两个点相邻, 那么这两个对应的 $G_2$ 之间增加联运算的所有可能边.
• (2) 区分导出子图 ($G[V^{\prime }]$), 边导出子图 ($G[E^{\prime }]$), 合成图 ($G_1[G_2]$) 记号的区别.

图的张量积 (tensor product) $\times$

设 $G_1=(V_1,E_1),G_2=(V_2,E_2),$ 是两个图. 对点集 $V=V_1\times V_2$ 的任意两个点 $u=(u_1,u_2)$ 与 $v=(v_1,v_2)$, 当 ($u_1\leftrightarrow v_1$) 和 ($u_2\leftrightarrow v_2$) 时, 把 $u$ 与 $v$ 相连. 如此得到的新图称为 $G_1$ 与 $G_2$ 的张量积图. 记为 $G_1\times G_2$.

一般地, $\chi (G_1\times G_2)\le \min \{\chi (G_1),\chi (G_2)\}$ 成立. 1966年 S.T. Hedetniemi 猜想对于简单图等号都成立. Yaroslav Shitov 于2019.5月给出了反例 (论文仅3页), 该结果已被 Annals of Mathematics 正式接收发表, 创造了Annals 接收发表最快的新纪录 (21天). https://arxiv.org/abs/1905.02167

超立方体

图的积运算是网络构造的常用方法. 并行计算机中的网络拓扑常采用所谓的“超立方体”结构. 采用该结构可使网络具有较好的可靠性、较小的通信延迟和很好的可扩展性以及便于并行编程等优点.

★积图构造

“超立方体” (hypercube, 或 $n$-cube) 可以用如下积图来递归构造.

(1) $1$ 方体: $Q_1=K_2$

(2) $n$ 方体: $Q_n=K_2\square Q_{n-1}$

二进制码构造

“超立方体” 常采用下面简单的递归构造方法:

$n$ 方体 $Q_n$ 的顶点可用一个长度为 $n$ 的二进制码来表示. $Q_n$ 的顶点数目正好等于 $2^n$ 个.

由 $n-1$ 方体 $Q_{n-1}$ 构造 $Q_n$ 的方法是: 将 $Q_{n-1}$ 拷贝一个. 将原 $Q_{n-1}$ 每个顶点的码前再添加一个零, 将拷贝得来的 $n-1$ 方体每个顶点的码前面再添加一个 $1$. 然后在两个 $n-1$ 方体之间连线: 当且仅当两个顶点码只有一位对应位数字不同时, 该两点连线. 如此得到的图即为 $n$ 方体.

由两个 $Q_2$ 构造 $Q_3$ :

关于 $n$ 方体 $Q_n$ 的性质研究, 可以查阅到很多文献. 经典文章是: Saad Y, M H. Schultz, Topological properties of hypercubes, IEEE Trans. Comput. 1988 37(7) 867--872

超立方体的性质

$|V(Q_n)|=2^n$

$|E(Q_n)|=n\times 2^{n-1}$

$Q_n$ 是二部图 (点色数为 $2$, 边色数是 $n$)

$Q_n$ 是 $n$ 正则图 (正则二部图存在完美匹配) (见 5.2)

1.3 路与图的连通性

对图的路与连通性进行研究, 在计算机网络研究中有十分重要的意义. 因为网络的抽象就是一个图. 研究网络信息传递, 信息寻径是主要问题之一, 这恰对应于图中路的研究; 在网络研究中, 可靠性也是主要问题之一, 它与图的连通性问题相对应.

★路与连通性的相关概念

途径 (walk)

$G$ 的一条途径 (walk) 是一个有限非空序列 $w=v_0{e}_1{v}_1{e}_2{v}_2\dots e_k{v}_k$, 它的项交替地为顶点和边, 使得 $1\le i\le k$, $e_i$ 的端点是 $v_{i-1}$ 和 $v_i$.

途径中边数称为途径的长度 (length);

$v_0$, $v_k$ 分别称为途径的起点 (initial vertex) 与终点 (terminal vertex), 其余顶点称为途径的内部点 (internal vertex).

迹 (trail)

边不重复的途径称为图的一条迹.

路 (path)

顶点不重复的途径称为图的一条路. $n$ 个点的路一般用 $P_n$ 表示.

注:

(1) 起点与终点重合的途径、迹、路分别称为图的闭 (closed) 途径、闭迹与圈. 闭途径也称为回路.

长度为 $k$ 的圈称为 $k$ 圈 ($k$-cycle), $k$ 为奇数时称为奇圈 (odd cycle), $k$ 为偶数时称为偶圈 (even cycle). $n$ 阶圈一般用 $C_n$ 表示.

(2) 自环一般认为是 $1$ 长圈, 两条重边围成 $2$ 长圈;

(3) 所有的奇圈都不是二部图, 所有的偶圈均是二部图.

图中两点的距离 (distance)

点 $u$ 与 $v$ 的距离: $u$ 与 $v$ 间最短路的长度称为 $u$ 与 $v$ 间距离, 记为 $d(u,v)$. 如果 $u$ 与 $v$ 间不存在路, 定义 $d(u,v)=\infty$.

图中两顶点的连通性

图 $G$ 中点 $u$ 与 $v$ 连通的 (connected), 如果 $u$ 与 $v$ 间存在路. 否则称 $u$ 与 $v$ 是不连通的 (disconnected). 点对的连通关系是等价关系 (满足自反性, 对称性, 传递性).

注: 规定一个顶点和它自身连通.

连通图

若图 $G$ 中任意两点是连通的, 称 $G$ 是连通图 (connected graph), 否则, 称 $G$ 为非连通图 (disconnected graph).

连通分支 $\omega (G)$

图 $G$ 中每一个极大连通子图, 称为 $G$ 的连通分支 (component) (连通关系的等价类). $G$ 的连通分支的个数, 称为 $G$ 的分支数, 记为 $\omega (G)$.

注: 连通图 $G$ 的连通分支数 $\omega (G)=1$.

例

在 $n$ 阶连通图中至少有 $n-1$ 条边.

证明: $n$ 阶空图的分支数为 $n$. 每增加一条边, 分支数至多减少 $1$. 故至少要增加 $n-1$ 条边, 才能使分支数减少为 $1$, 即使其连通. 故在 $n$ 阶连通图中至少有 $n-1$ 条边.

例

若 $\delta \ge 2$ , 则 $G$ 中必然含有圈.

证明: 只就连通图证明即可！

设 $P=v_1{v}_2\dots v_{k-1}{v}_k$ 是 $G$ 中的一条最长路. 由于 $\delta \ge 2$ , 所以 $v_k$ 必然有相异于 $v_{k-1}$ 的邻接顶点. 又 $W$ 是 $G$ 中最长路, 所以, 这样的邻接点必然是 $v_1,v_2,\dots ,v_{k-2}$ 中之一. 设该点为 $v_m$ , 则 $v_m{v}_{m+1}\dots v_k{v}_m$ 为 $G$ 中圈.

练习: 若 $G$ 是简单图且 $\delta \ge k$ , 则 $G$ 中存在 $k$ 长路. (与练习题13类比)

图的直径

连通图 $G$ 的直径 (diameter) 定义为:

$$d(G)=\max \{d(u,v)|u,v\in V(G)\}$$

如果 $G$ 不连通, 图 $G$ 的直径定义为: $d(G)=\infty$.

连通图的性质

定理1

若图 $G$ 不连通, 则其补图连通.

证明: $\forall u,v\in V(\bar{G})$,
如果 $u$, $v$ 属于 $G$ 的同一分支, 设 $w$ 是与 $u,v$ 处于不同分支中的点, 则在 $G$ 的补图中, $u$ 与 $w$, $v$ 与 $w$ 分别相邻, 于是, $u$ 与 $v$ 在 $G$ 的补图中是连通的.
若 $u$ 与 $v$ 在 $G$ 的不同分支中, 则在 $G$ 的补图中必然相邻, 因此, 补图也连通.

定理2

若 $G$ 是简单图且 $\delta (G)\ge (n-1)/2$, 则 $G$ 是连通的.

证明: 选择 $G$ 的任意两点 $u$ 和 $v$. 若 $u$ 和 $v$ 相邻, 则结论成立. 故假设 $u$ 和 $v$ 不相邻. 事实上, 仅需证明 $u$ 和 $v$ 有一个公共邻点.

因 $G$ 是简单图, 故$|N(u)|\ge \delta (G)\ge (n-1)/2$, $|N(v)|\ge \delta (G)\ge (n-1)/2$.

则有$|N(u)|+|N(v)|\ge n-1$. 这说明 $u$ 和 $v$ 至少有 $1$ 个邻点.

注: (1) 上面结论还可以用反证法证明 (留作练习).

​ (2) 定理的界 $(n-1)/2$ 是紧的(sharp). 考虑 $K_{\lfloor n/2\rfloor }+K_{\lceil n/2\rceil }$.

★二部 (偶) 图的判定定理

定理: (König, 1936) 一个图是二部图当且仅当它不包含奇圈.

图 $G$ 是偶图当且仅当 $G$ 中没有奇回路.

证明:

必要性: 设 $G$ 是具有二分类 $(X,Y)$ 的二部图, 并且 $C=v_0{v}_1\dots v_k{v}_0$ 是 $G$ 的一个圈. 不失一般性, 可假定 $v_0\in X$. 一般地, $v_{2i}\in X$, $v_{2i+1}\in Y$. 又因为 $v_0\in X$, 所以 $v_k\in Y$. 由此 $C$ 是偶圈.

充分性: 在 $G$ 中任意选取点 $u$, 定义 $V$ 的分类如下:

• $X=\{x|d(u,x)是偶数,x\in V(G)\}$ (到 $u$ 距离为偶数的点)
• $Y=\{y|d(u,y)是奇数,y\in V(G)\}$ (到 $u$ 距离为奇数的点)

下面证明: 对 $X$ 中任意两点 $v$ 与 $w$ 都不相邻！($v,w\in Y$ 的情形自己证明)

设 $v$ 与 $w$ 是 $X$ 中任意两个顶点. $P$ 是一条最短 $(u,v)$ 路, 而 $Q$ 是一条最短的 $(u,w)$ 路.

又设 $u_1$ 是 $P$ 和 $Q$ 的最后一个交点. 由于 $P,Q$ 是最短路, 所以, $P,Q$ 中 $u$ 到 $u_1$ 段长度相同, 因此奇偶性相同. 又 $P,Q$ 的长均是偶数, 所以, $P,Q$ 中 $u_{1}v$ 段和 $u_{1}w$ 段奇偶性相同.

如果 $v$ 与 $w$ 邻接, 则可得到奇圈, 矛盾.

注:
要判断一个图是二部图, 找到二部划分;
要判断一个图不是二部图, 仅需找到一个奇圈.

1.4 最短路及其算法

赋权图

赋权图的定义

在图 $G$ 的每条边上标上一个实数 $w(e)$ 后, 称 $G$ 为边赋权图. 被标上的实数称为边的权值(weight).

若 $H$ 是赋权图 $G$ 的一个子图, 称 $W(H)={\sum }_{e\in E(H)}w(e)$ 为子图 $H$ 的权值.

注: 权值的意义是广泛的. 可以表示距离, 可以表示交通运费, 可以表示网络流量, 在朋友关系图甚至可以表示友谊深度(抽象的距离).

赋权图中的最短路

设 $G$ 为边赋权图. $u$ 与 $v$ 是 $G$ 中两点, 在连接 $u$ 与 $v$ 的所有路中, 路中各边权值之和最小的路, 称为 $u$ 与 $v$ 间的最短路 (shortest path).

算法

解决某类问题的一组有穷规则, 称为算法 (algorithm).

好算法

算法总运算量 (算术运算、比较运算等) 是问题规模的多项式函数时, Edmonds 称该算法为好算法 (如图上某算法的运算次数可由 $V$ 和 $E$ 的一个多项式表示, 如 $5|V{|}^3|E|$).若一个算法计算需要指数次(如 $5^{|V|}$), 则对规模大的图而言, 将是十分无效的.

算法分析

注: 对算法进行分析, 主要对时间 (或空间) 复杂度进行分析. 分析运算量和问题规模之间的关系.

动态规划 (Dynamic Programming)

为求出 f(n), 只需要知道几个更小的 f(i). 将求解 f(i) 称作求解 f(n) 的“子问题”. 将一个问题拆成几个子问题, 分别求解这些子问题, 即可推断出大问题的解, 这就是动态规划 (DP).

无后效性: 一旦求出某个 f(i), 如何凑出 f(i) 就再也用不着了;

最优子结构: 大问题的最优解可以由子问题的最优解推出, 这个性质叫做“最优子结构性质”.

★最短路算法

1956 年, 荷兰计算机学家 Edsger W. Dijkstra (1930.5-2002.8, 1972 年获图灵奖) 得到了在赋权图中求由点 $u_0$ 到 $G$ 中所有顶点的最短路的好算法, 称为顶点标号法, 3 年后 (1959 年) 发表在期刊 Numerische Mathematik 上.

假设 $S$ 是 $V$ 的真子集且 $u_0\in S$ 并记 $\overline{S}=V\backslash S$. 若 $P=u_0\cdots u\overline{v}$ 是从 $u_0$ 到 $\overline{S}$ 的最短路, 则显然 $u\in S$ 且 $P$ 的 $u_0$ 至 $u$ 节必然是最短的 $u_0$ 至 $u$ 节路 (最优子结构).

Dijkstra 算法的思想

从 $S_0=\{u_0\}$ 开始逐步构造一个由 $V$ 的子集组成的递增序列 $S_0,S_1,\dots S_{v-1}$, 使得在第 $i$ 步结束时, 由 $u_0$ 到 $S_i$ 的最短路均已知.

首先确定距 $u_0$ 最近的一个顶点. 为此只要选取顶点 $u_1\in \overline{S_0}$, 使得 $d(u_0,u_1)=d(u_0,\overline{S_0})$ 即可. 事实上,

$$d(u_0,\overline{S_0})=\underset{u\in S_0,\overline{v}\in \overline{S_0}}{\min }\{d(u_0,u)+w(u\overline{v})\}=\underset{\overline{v}\in \overline{S_0}}{\min }\{w(u_0\overline{v})\}\text{\hspace{1em}(1)}$$

现置 $S_1=\{u_0,u_1\}$ 并用 $P_1$ 记路 $u_0{u}_1$, 显然这是最短的 $u_0$ 到 $u_1$ 的路.

一般地, 若集 $S_k=\{u_0,u_1,\dots ,u_k\}$ 以及相应的最短路 $P_1,P_2,\dots ,P_k$ 已经确定, 则可以计算得到 $d(u_0,\overline{S_k})$, 并选取顶点 $u_{k+1}\in \overline{S_k}$ 使得 $d(u_0,u_{k+1})=d(u_0,\overline{S_k})$. 可以得到对某个 $j\le k$, $d(u_0,u_{k+1})=\min \{d(u_0,u_j)+w(u_j{u}_{k+1})\}$ 成立.

若在每一步通过搜索计算 (1) 式的最小值时, 则有许多不必要的比较. 为避免重复并保留从每一步到下一步的计算信息, 采用如下的标号方法.

开始时 $l(u_0)=0$, 而对其它顶点则有 $l(u_0)=\infty$. 在实际运行中, 这些标号不断被修改: 在第 $i$ 步结束时 $l(u)=d(u_0,u)$ 对 $u\in S_i$ 成立, 并且 $l(v)={\min }_{u\in S_{i-1}}\{d(u_0,u)+w(uv)\}$ 对 $v\in \overline{S_i}$ 成立.

★Dijkstra 算法

设 $l(v)$ 表示 $v$ 到 $u_0$ 的最短距离.

1. 置 $l(u_0)=0$; 对 $v\ne u_0$, $l(v)=\infty$, $S_0=u_0$ 且 $i=0$.
2. 对每个 $v\in \overline{S_i}$, 用 $\min \{l(v),l(u_i)+w(u_{i}v)\}$ 代替 $l(v)$. 计算 $\underset{v\in \overline{S_i}}{\min }\{l(v)\}$, 并把达到最小值的点记为 $u_{i+1}$. 记 $S_{i+1}=S_i\cup u_{i+1}$.
3. 若 $i=n-1$, 则停止. 若 $i<n-1$, 则用 $i+1$ 代替 $i$, 并转入第 2 步.

当算法结束时, 从 $u_0$ 到 $v$ 的距离由标号 $l(v)$ 的终值给出. 算法个仅给出了 $u_0$ 到所有其它顶点的距离, 而且只要沿着先后顶点的轨迹引伸, 就能给出对应的最短路.

时间复杂度分析: 全部迭代共需 $n(n-1)/2$ 次加法和 $n(n-1)$ 次比较, 所以算法是 $n^2$ 次的.

例

如图所示, 求点 $a$ 到点 $b$ 的距离.

解:

1. $l(a)=0,S_0=\{a\},i=0$;

2. $l(v_1)=l(a)+w(a{v}_1)=2$;
   $l(v_2)=l(a)+w(a{v}_2)=8$;
   $l(v_3)=l(a)+w(a{v}_3)=1$ ;
   $\min l(v_i)=l(v_3)=1$, 令 $S_1=\{a,v_3\},i=1$.

3. $l(v_6)=l(v_3)+w(v_3{v}_6)=10$;
   $\min l(v_i)=l(v_1)=2$, 令 $S_2=\{a,v_1,v_3\},i=2$.

4. $l(v_4)=l(v_1)+w(v_1{v}_4)=3$;
   $\min l(v_i)=l(v_4)=3$, 令 $S_3=\{a,v_1,v_3,v_4\},i=3$.

5. $l(v_2)=l(v_4)+w(v_4{v}_2)=7$;
   $l(v_5)=l(v_4)+w(v_4{v}_5)=6$;
   $l(b)=l(v_4)+w(v_{4}b)=12$;
   $\min l(v_i)=l(v_5)=6$, 令 $S_4=\{a,v_1,v_3,v_4,v_5\},i=4$.

6. $l(v_6)=l(v_5)+w(v_5{v}_6)=10$;
   $l(b)=l(v_5)+w(v_{5}b)=12$;
   $\min l(v_i)=l(v_2)=7$, 令 $S_5=\{a,v_1,v_2,v_3,v_4,v_5\},i=5$.

7. $l(v_6)=l(v_2)+w(v_2{v}_6)=9$;
   $\min l(v_i)=l(v_6)=9$, 令 $S_6=\{a,v_1,v_2,v_3,v_4,v_5,v_6\},i=6$.

8. $l(b)=l(v_6)+w(v_{6}b)=11$;
   $l(b)=12$, 令 $S_7=\{a,v_1,v_2,v_3,v_4,v_5,v_6,b\},i=7$.

最短路算法的在计算机科学中的应用

1. 导航软件 (GIS) 中路径规划中的最短路计算.
2. 停车诱导系统中的最短路计算.
3. 开放最短路优先协议 (OSPF). OSPF 是由 IETF (Internet Engineering Task Force) 的 IGP (Interior Gateway Protocol) 工作组为 IP 网络设计的路由协议, 此工作组于 1988 年设计了基于最短路优先 (SPF) 算法的 IGP 用于Internet. 它是基于 SPF 算法进行的, 也就是 Dijkstra 算法.

Remark: 最短路算法不仅可以计算实际的距离问题, 还可以计算抽象距离(如状态转移的次数).

1.5 图的代数表示及其特征

用邻接矩阵或关联矩阵表示图, 称为图的代数表示 (第三种表示方法).

用矩阵表示图有两个优点:
(1) 能够把图输入到计算机中;
(2) 可以用线性代数的方法研究图论.

★图的邻接矩阵 $A$ (adjacency matrix)

邻接矩阵的定义

设 $G$ 为 $n$ 阶图, $V=v_1,v_2,\dots ,v_n$, 邻接矩阵 $A(G)=(a_{ij})$, 其中:

$$a_{ij}=\{\begin{array}{l}l,v_i与v_j间边数(一个自环计2)\\ 0,v_i和v_j不邻接\end{array}$$

(与顶点顺序无关)

$$A(G)=\left(\begin{array}{cccc}0& 2& 0& 1\\ 2& 0& 1& 1\\ 0& 1& 0& 1\\ 1& 1& 1& 4\end{array}\right)$$

邻接矩阵的性质

(1) 非负性与对称性

由邻接矩阵定义知 $a_{ij}$ 是非负整数, 即邻接矩阵是非负整数矩阵;

在图中点 $v_i$ 与 $v_j$ 邻接, 有 $v_j$ 与 $v_i$ 邻接, 即 $a_{ij}=a_{ji}$. 所以, 邻接矩阵是对称矩阵.

(2) 同一图的不同形式的邻接矩阵是相似矩阵.

这是因为, 同图的两种不同形式矩阵可以通过交换行和相应的列变成一致.

(3) 如果 $G$ 为简单图, 则 $A(G)$ 为布尔矩阵; 行和(列和)等于对应顶点的度数; 矩阵元素总和为图的总度数, 也就是 $G$ 的边数的 $2$ 倍.

(4) $G$ 连通的充分必要条件是: $A(G)$ 不能与如下矩阵相似.

$$\left(\begin{array}{cc}{A}_{11}& 0\\ 0& A_{22}\end{array}\right)$$

证明:

1 必要性 (连通 => 不能与这种矩阵相似 即 与这种矩阵相似 => 不连通)
若不然: 设 $A_{11}$ 对应的顶点是 $v_1,v_2,\dots ,v_k$ , $A_{22}$ 对应的顶点为 $v_{k+1},v_{k+2},\dots ,v_n$, 显然, $v_i$ $(1\le i\le k)$ 与 $v_j$ $(k+1\le i\le n)$ 不邻接, 即 $G$ 是非连通图. 矛盾！

2 充分性 (不能与这种矩阵相似 => 连通 即 不连通 => 与这种矩阵相似)
若不然: 设 $G_1$ 与 $G_2$ 是 $G$ 的两个不连通的部分, 并且设 $V(G_1)=v_1,v_2,\dots ,v_k$, $V(G_2)=v_{k+1},v_{k+2},\dots ,v_n$, 如果在写 $G$ 的邻接矩阵时, 先排 $V(G_1)$ 中点, 再排 $V(G_2)$ 中点, 则 $G$ 的邻接矩阵形式必为:

$$\left(\begin{array}{cc}{A}_{11}& 0\\ 0& A_{22}\end{array}\right)$$

(5) 定理: 设 $A^k(G)=(a_{ij}^{(k)})$, 则 $a_{ij}^{(k)}$ 表示顶点 $v_i$ 到顶点 $v_j$ 的长度为 $k$ 的途径条数.

证明: 对 $k$ 作数学归纳法证明. 当 $k=1$ 时, 由邻接矩阵的定义, 结论成立; 假设当 $k-1$ 时结论均成立. 当为 $k$ 时:

一方面: 先计算 $A^k$;

$$A^k=A^{k-1}A=(a_{i1}^{(k-1)}{a}_{j1}+a_{i2}^{(k-1)}{a}_{j2}+\cdots +a_{in}^{(k-1)}{a}_{jn}{)}_{n\times n}$$

另一方面: 考虑 $v_i$ 到 $v_j$ 的长度为 $k$ 的途径: 设 $v_m$ 是 $v_i$ 到 $v_j$ 的途径上点, 且该点和 $v_j$ 邻接. 则 $v_i$ 到 $v_j$ 的经过 $v_m$ 且长度为 $k$ 的途径数目应该为:

$$a_{im}^{(k-1)}{a}_{mj}$$

所以, $v_i$ 到 $v_j$ 的长度为 $k$ 的途径数目为:

$$a_{i1}^{(k-1)}{a}_{j1}+a_{i2}^{(k-1)}{a}_{j2}+\cdots +a_{in}^{(k-1)}{a}_{jn}$$

即为 $a_{ij}^{(k)}$.

推论: 对于简单图有:

(1) $A^2$的元素 $a_{ii}^{(2)}$ 是 $v_i$ 的度, $A^3$ 的元素 $a_{ii}^{(3)}$ 是含 $v_i$ 的三角形个数的 $2$ 倍;

(2) 若 $G$ 是连通的, 对于 $i\ne j$ , $v_i$ 和 $v_j$ 间距离 $d$ 是使 $A^d$ 中 $a_{ij}^{(d)}\ne 0$ 的最小整数.

★图的关联矩阵 $M$ (incidence matrix)

关联矩阵的定义

若 $G$ 是 $(n,m)$ 图, 则图 $G$ 的关联矩阵为:

$$M(G)=(a_{ij}{)}_{n\times m}$$

其中: $a_{ij}$ 为 $v_i$ 与 $e_j$ 关联的次数: $0$, $1$, 或 $2$ (环).

$$M(G)=\left(\begin{array}{ccccccc}1& 1& 0& 0& 1& 0& 1\\ 1& 1& 1& 0& 0& 0& 0\\ 0& 0& 1& 1& 0& 0& 1\\ 0& 0& 0& 1& 1& 2& 0\end{array}\right)$$

关联矩阵的性质

(与顶点, 边顺序无关)

(1) 关联矩阵的元素为 $0$, $1$ 或 $2$ (非简单图);
(2) 关联矩阵的每列和为 $2$; 每行的和为对应顶点度数 (据此可以证明握手定理) ;

注:
(1) 邻接矩阵, 关联矩阵是计算机表示图的两种方式(还有邻接表等), 包含的信息有所不同;
(2) 非稀疏图一般不用关联矩阵(边数多占用存储空间大).

简单图的关联矩阵与邻接矩阵的关系

(i) $M{M}^{\top }=A+D$, 其中 $D$ 是度矩阵 (即对角线元素代表是对应顶点的度, 其它元素均为零), $A$ 代表邻接矩阵.

(ii) $M^{\top }M=2I+A(L(G))$, 其中 $I$ 是单位矩阵, $A(L(G))$ 代表 $G$ 的线图 $L(G)$ 的邻接矩阵 (线图的概念见第四章 $E$ 图与 $H$ 图的关系).

★图的 Laplacian 矩阵

图的 Laplacian 矩阵 $L=D-A$, 其中 $D$ 是度矩阵 (即对角线元素代表对应顶点的度, 其它元素均为零), $A$ 代表图的邻接矩阵. Laplacian 矩阵在机器学习, 复杂网络, 控制理论等领域中都有重要应用.

相关结论:

1. $L$ 的特征值 $0$ 的重数与图的连通分支数相等;
2. $L$ 的第二小特征值大于 $0$ 当且仅当图连通.
3. 可参见 https://arxiv.org/pdf/1111.2897.pdf.

图的谱

图的谱理论 (Spectral Graph Theory) 应用非常广泛:

1. Expanders(扩展器, or Enlargers): 通信网络, 纠错码, 内存空间(计算模块的第二大特征值).
2. 传感器网络(Laplacian矩阵的第二小和最大特征值之比, 比越大其决策融合算法收敛越快 ).
3. 复杂网络(度和特征值分布)和互联网(正则化Laplacian谱).
4. 数据挖掘(将数据表示成图, 计算Laplacian谱聚类).
5. 计算机视觉和模式识别(用边赋权图表示图片, 点表示像素, 边表示像素之间相似程度): 用Fiedler向量(Laplacian第二小特征值)分割图像前景和背景.
6. 网络搜索(PageRank算法, AAT的最大特征值).
7. 控制理论/负载均衡和互连网络: Laplacian谱.
8. 化学 (特征值对应分子稳定性).
9. 理论物理和量子力学中(最小化Hamiltonian系统能量).

图的特征多项式 (characteristic polynomial)

图的邻接矩阵 $A(G)$ 的特征多项式

$$f(G,\lambda )=|\lambda E-A|={\lambda }^n+a_1{\lambda }^{n-1}+a_2{\lambda }^{n-2}+\cdots +a_{n-1}\lambda +a_n$$

称为图 $G$ 的特征多项式.

例

简单图 $G$ 的特征多项式为

$$f(G,\lambda )=|\lambda E-A|={\lambda }^n+a_1{\lambda }^{n-1}+a_2{\lambda }^{n-2}+\cdots +a_{n-1}\lambda +a_n$$

求证:
(1) $a_1=0$;
(2) $–a_2=m(G)$;
(3) $–a_3$ 是 $G$ 中三角形数目的 $2$ 倍;

证明: 由 Laplace 定理 (1812年由Cauchy首先证明): 对每个 $1\le i\le n$, $(-1{)}^i{a}_i$ 是 $A(G)$ 的所有 $i$ 阶主子式之和.

(1) 因 $A(G)$ 的主对角元全为零, 故所有 $1$ 阶主子式全为零, 即: $a_1=0$;

(2) 对于简单图 $G$, $A(G)$ 中非零的 $2$ 阶主子式必为如下形式:

$$\left|\begin{array}{cc}0& 1\\ 1& 0\end{array}\right|=-1$$

这样的一个 $2$ 阶主子式对应 $G$ 中的一条边, 反之亦然, 所以, 有:

$$\begin{gathered} (-1{)}^2{a}_2=-m(G) \\ -a_2=m(G) \end{gathered}$$

(3) 对于简单图 $G$, $A(G)$ 中非零的 $3$ 阶主子式有如下 $3$ 种本质上不同的形式:

$$\left|\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 0\end{array}\right|,\left|\begin{array}{ccc}0& 1& 1\\ 1& 0& 0\\ 1& 0& 0\end{array}\right|,\left|\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right|$$

这三种情形中仅最后一种的值非零 (值为 $2$). 这种主子式对应图中 $3$ 条互相相邻的边 (形成一个三角形 $K_3$). 所以结论成立.

★图的邻接谱 $Spec(G)$

1950s, 德国化学家本生发现(焰色反应): 每种元素在火焰下都有它自己特有的颜色, 如钠的颜色是黄色, 钙的颜色是砖红色, 锂的颜色是深红色, 钾的颜色是紫色.

本生将结论告诉好友基尔霍夫后, 他们用三棱镜制作了一个简陋光谱仪, 发现所有元素的发射光谱都是分立的线条, 并不连续, 就像条形码一样, 而且每种元素的条形码都不一样.

这不就是元素的身份证吗? 他们把已知的元素光谱线都记录了下来,以后只要把一个东西往火里一烧, 分析他的光谱, 然后对照已经记录的元素光谱, 发现其中有钠元素, 有氯元素, 就知道烧的是氯化钠.

这解释了夫琅和费线(太阳可见光谱中的暗线, 1814年)中的暗线都对应了特定元素的吸收线, 从而确实了太阳的组成(1849年).

图的邻接矩阵 $A(G)$ 的特征多项式的特征值 (eigenvalue) 及其重数 (multiplicity), 称为 $G$ 的邻接谱 (adjacency spectrum), 记为 $Spec(G)$.

$K_n$ 的谱

$K_n$ 的邻接矩阵为

$$A(K_n)=\left(\begin{array}{cccccc}0& 1& 1& \cdots & 1& 1\\ 1& 0& 1& \cdots & 1& 1\\ 1& 1& 0& \cdots & 1& 1\\ ⋮& ⋮& ⋮& & ⋮& ⋮\\ 1& 1& 1& \cdots & 0& 1\\ 1& 1& 1& \cdots & 1& 0\end{array}\right)$$

于是

$$\begin{array}{rl}|\lambda E-A(K_n)|& =\left|\begin{array}{cccccc}\lambda & -1& -1& \cdots & -1& -1\\ -1& \lambda & -1& \cdots & -1& -1\\ & & \cdots & & & \\ -1& -1& -1& \cdots & -1& \lambda \end{array}\right|\\ & =\left|\begin{array}{cccccc}\lambda -n+1& -1& -1& \cdots & -1& -1\\ \lambda -n+1& \lambda & -1& \cdots & -1& -1\\ & & \cdots & & & \\ \lambda -n+1& -1& -1& \cdots & -1& \lambda \end{array}\right|\\ & =(\lambda -n+1)\left|\begin{array}{cccccc}1& -1& -1& \cdots & -1& -1\\ 1& \lambda & -1& \cdots & -1& -1\\ & & \cdots & & & \\ 1& -1& -1& \cdots & -1& \lambda \end{array}\right|\\ & =(\lambda -n+1)(\lambda +1{)}^{n-1}\end{array}$$

$K_n$ 的谱为

$$Spec(G)=\left(\begin{array}{cc}-1& n-1\\ n-1& 1\end{array}\right)$$