设y=+1表示X是连通图
设y=-1表示X是非连通图。
用 反证法 证明 识别连通图问题是非线性可分的：
假设：
这个问题是线性可分的，那么一定存在（ω，b）：
当y=+1时，ωTx+b≥0；
当y=-1是，ωTx+b＜0
图1连通：y=+1
2（1）1+2+3+5+6+b≥0
5（2）1+2+3+4+7+b≥0
口-（3）1+2+3+4+5+b＜0
-口（4）1+2+3+6+7+b＜0
公式1+2，有2[1+2+3+b]+4+5+6+7≥0
公式3+4，有2[1+2+3+b]+4+5+6+7<0
那么两个新公式相同，不可能同时＞0，＜0.
所以识别连通图的问题是非线性可分的。
思考：请证明【一笔画问题】是【非线性可分】问题。即区分两类二值图像，一种可以用一笔画出，另一种不能一笔画出。要证明这个问题的非线性可分问题。
结论
“能否一笔画完”的判定 不是线性可分的。
下面给出一种 构造-反证：把经典的 XOR（奇偶）问题 嵌入到“一笔画”判定里；因为 XOR 本身在任何原始特征空间都不可线性分离，一旦它是“一笔画”问题的子问题，就说明整题也必然非线性可分。
1 预备：一笔画⇔顶点奇偶性
对无向图 G=(V,E) 来说
G 可一笔画 ⟺ ∣{v∈V∣deg(v) 为奇}∣ =0 或 2.
于是只要我们能构造一个极小图，使
- 偶数条边 ⇒ 奇点数为 0 或 2 (阳性)
- 奇数条边 ⇒ 奇点数 > 2 (阴性)
就形成了 “边数奇偶＝类别标签” 的 奇偶判定。
2 构造一个 3 条边的“星形”子问题
A
|
x1
|
O —— x2 —— B
|
x3
|
C
- 顶点：中心 O和三个端点 A,B,C。
- 可选边（特征） x1=OA, x2=OB, x3=OC ∈{0,1}.
数据集 D（8 个可能图，用 (x1,x2,x3) 表示）
| 边的组合 | 奇点个数 | 是否一笔画 | 类别 |
|---|---|---|---|
| (0,0,0) | 0 | ✅ | +1 |
| (1,0,0) | 2 | ✅ | +1 |
| (0,1,0) | 2 | ✅ | +1 |
| (0,0,1) | 2 | ✅ | +1 |
| (1,1,0) | 2 | ✅ | +1 |
| (1,0,1) | 2 | ✅ | +1 |
| (0,1,1) | 2 | ✅ | +1 |
| (1,1,1) | 4 | ❌ | –1 |
观察可知：
类别 = {
- +1,若 x1+x2+x3 为偶数,
- −1,若 x1+x2+x3 为奇数
这正是三维 偶／奇 (Parity) 函数——它是经典的 XOR 在 3 维的推广。
3 XOR / 奇偶函数为什么线性不可分？
给出一种简洁的几何论证（Minsky & Papert 1969 同款）：
- 正样本集合
P={(0,0,0),(1,1,0),(1,0,1),(0,1,1)} 的 凸包
含有点 (1/2,1/2,1/2)。 - 负样本集合
N={(1,0,0),(0,1,0),(0,0,1),(1,1,1)} 的凸包
同样 含有该点(1/2,1/2,1/2)。
若两类能被一条超平面分开，则其凸包必须互不相交；
但这里两凸包 相交，故不存在任何线性分割面。
因此 Parity / XOR 非线性可分。
4 归结到一笔画问题
- 我们已经把“一笔画”中的一个小子集 D映射成 Parity；
- 若整体问题可被一个超平面分割，则 D 也必能被同一超平面分割——与上一节矛盾。
所以：区分“一笔画图”和“非一笔画图”的整体二分类任务 不存在 任何基于原始 0/1 像素（边存在与否）的线性判别函数；即它是 非线性可分问题。
5 结论与启示
- 证明思路：把已知的 XOR 难题嵌入目标任务
→ 找到凸包相交
→ 否定线性可分性。 - 工程意义
- 想要自动判别一笔画图片，必须借助 核技巧 / 深度模型 / 非线性特征；
- 单层感知器或任何纯线性模型都无法完成该区分。
