块 ■完全图是块吗？ ■树是块吗？ ■欧拉图和哈密尔顿图是块吗？ ■若图的块只含一个顶点 则这种顶点有什么特征？ V6 e7 V7 ■若图的块只含一条边 则这种边有什么特征？(f) e e ■两个块至多含多少个公共顶点 e6. eA 这种顶点有什么特征？ ■ 两个块至多含多少条公共边？ e2 es ■ 块为边集定义了一种等价关系。 V3 ·划分是什么？ 2023/3/20 16
n 完全图是块吗？ n 树是块吗？ n 欧拉图和哈密尔顿图是块吗？ n 若图的块只含一个顶点， 则这种顶点有什么特征？ n 若图的块只含一条边， 则这种边有什么特征？（iff） n 两个块至多含多少个公共顶点？ 这种顶点有什么特征？ n 两个块至多含多少条公共边？ n 块为边集定义了一种等价关系。 l 划分是什么？ 2023/3/20 16 块 v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6 v7 v6 e7
块 ■对于阶至少为3的连通图G,以下是块的等价定义 1.G没有割点。 2.对于任意两个顶点u,v∈V,G含两条无公共内顶点的-v路。 3.对于任意两个顶点u,v∈V,G含圈经过和v。 4.对于任意一个顶点vEV和任意一条边eEE,G含圈经过v和e。 5.对于任意两条边e,feE,G含圈经过e和f。 6.对于任意两个顶点u,v∈V和任意一条边e∈E,G含w-v路经过e。 7.对于任意三个顶点，y,wEV,G含w-v路经过w。 8.对于任意三个顶点u,,w∈V,G含v路不经过w。 2023/3/20 17
n 对于阶至少为3的连通图G，以下是块的等价定义 1. G没有割点。 2. 对于任意两个顶点u, v ∈ V ，G含两条无公共内顶点的u-v路。 3. 对于任意两个顶点u, v ∈ V，G含圈经过u和v。 4. 对于任意一个顶点v ∈ V 和任意一条边e ∈ E，G含圈经过v和e 。 5. 对于任意两条边e, f ∈ E，G含圈经过e和f。 6. 对于任意两个顶点u, v ∈ V 和任意一条边e ∈ E ，G含u-v路经过e 。 7. 对于任意三个顶点u, v, w ∈ V ，G含u-v路经过w。 8. 对于任意三个顶点u, v, w ∈ V ，G含u-v路不经过w 。 2023/3/20 17 块
块 ■对于阶至少为3的连通图G 1.G没有割点。 →2.对于任意两个顶点，v∈V,G含两条无公共内顶点的路。 2023/3/20
n 对于阶至少为3的连通图G 1. G没有割点。 2. 对于任意两个顶点u, v ∈ V ，G含两条无公共内顶点的u-v路。 2023/3/20 18 块
块 ■对于阶至少为3的连通图G 1.G没有割点。 ◆2. 对于任意两个顶点u,v∈V',G含两条无公共内顶点的-v路。 ■删去v的邻点w,仍存在其它的-v路，与经过w的-v路组成圈。 这样证明存在什么问题？ u 2023/3/20 19
n 对于阶至少为3的连通图G 1. G没有割点。 2. 对于任意两个顶点u, v ∈ V ，G含两条无公共内顶点的u-v路。 n 删去v的邻点w，仍存在其它的u-v路，与经过w的u-v路组成圈。 这样证明存在什么问题？ 2023/3/20 19 块 u w v
块 ■对于阶至少为3的连通图G 1.G没有割点。 →2.对于任意两个顶点，v∈V,G含两条无公共内顶点的路。 ■删去v的邻点w,仍存在其它的-v路，与经过w的-v路组成圈。 这样证明存在什么问题？ 2023/3/20 20
n 对于阶至少为3的连通图G 1. G没有割点。 2. 对于任意两个顶点u, v ∈ V ，G含两条无公共内顶点的u-v路。 n 删去v的邻点w，仍存在其它的u-v路，与经过w的u-v路组成圈。 这样证明存在什么问题？ 2023/3/20 20 块 u w v