随想｜程序如何辅助数学证明

问题介绍

一.子图和(subgraph)和诱导子图(induced subgraph)

设和是两个图，其中表示顶点集合，表示边集合。

---

1. 子图（Subgraph）的定义

图是图的一个子图，当且仅当满足：

• ；
• ，且每条边必须满足。

即子图是从图中选取部分顶点和部分边构成的图。

---

2. 诱导子图（Induced Subgraph）的定义

若给定图和顶点子集，则由所诱导的子图定义为：

• ；
• 。

即包含中以为端点的所有边。

这样的被称为在上的诱导子图，或简称为诱导子图。

如果图不包含某个图作为诱导子图，则称是 -free 的。

---

3. 举例（Example）

• 图 1 是图 2 的一个诱导子图：它由图 2 中某些顶点及其所有相关联边组成。
• 图 3 是图 2 的一个子图，但不是诱导子图，因为顶点和在图 2 中是相邻的，而图 3 中省略了这条边。

1.png

2.png

3.png

二. 爪型图(claw)

爪形图 是一个含有四个顶点的无向图，记作，它是一个星形图，包含：

• 一个中心顶点，
• 三个与中心顶点相连的叶子顶点，
• 且三个叶子顶点之间没有边相连。

即邻接关系为：

但与（其中）之间无边。

三.邻接矩阵

设图是一个有个顶点的图（无向图或有向图），记顶点集合为。则邻接矩阵是一个的矩阵，其中：

• 对于无向图：

注： 若图是带权图，则邻接矩阵中可以将 1 替换为相应的权值，无边则仍为 0 或其他标志（如表示不可达）

四. 用程序辅助检查有限情形

我为这个问题写了一个 MATLAB 程序：Max-vertices-in-rank-r-claw-free-graph。程序用邻接矩阵表示图，从给定图出发计算满足条件的加点结果，并筛掉含复制点的重复情形，帮助找出星补最多还能添多少个点。

它在证明中的作用，是把有限范围内繁琐、容易漏掉的图情况交给程序系统检查：结果可以用来核对手工推导、寻找极值构型或反例。程序验证的是设定范围内的枚举结果；要把结论推广为一般定理，还需要数学证明说明枚举覆盖了所有情形，并论证程序所检查的条件与定理条件一致。