围绕割点的重要概念之一：不可分割 A graph of order at least 3 is nonseparable iff every two vertices lie on a common cycle ■充分条件 口显然，删除任意一点，均不能使得任意两点不连通 。必要条件：反证法 口找到不成回路的最短uw路径P Why? 口d(u,v)=1,易证 口d(u,v)≥2，令k-是P中v的直接前驱节点 ■u,vk-1有回路C ■删去vk-1,u和v仍然相连：Q Uk=U 令x是C和Q的第一个交点 构造P',Q,可以形成ux+Q'+P'的uw回路围绕割点的重要概念之一：不可分割 A graph of order at least 3 is nonseparable iff every two vertices lie on a common cycle ◼ 充分条件 ❑ 显然，删除任意一点，均不能使得任意两点不连通 ◼ 必要条件：反证法 ❑ 找到不成回路的最短𝑢𝑣路径𝑃 ❑ 𝑑 𝑢, 𝑣 = 1，易证 ❑ 𝑑 𝑢, 𝑣 ≥ 2,令𝑣𝑘−1是𝑃中𝑣的直接前驱节点 ◼ 𝑢, 𝑣𝑘−1有回路𝐶 ◼ 删去𝑣𝑘−1，𝑢和𝑣仍然相连: 𝑄 ◼ 令𝑥是𝐶和𝑄的第一个交点 ◼ 构造𝑃′ , 𝑄′ ,可以形成𝑢𝑥 + 𝑄′ + 𝑃′的𝑢𝑣回路 Why？