程序如何辅助数学证明

问题介绍

一.子图和(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 或其他标志（如表示不可达）

123