证明:若[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是连通图，则有可能删除顶点使[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]变成不连通的当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]不是完全图。

公告：维护QQ群：833371870，欢迎加入！
公告：维护QQ群：833371870，欢迎加入！
公告：维护QQ群：833371870，欢迎加入！

2022-06-19

证明:若[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是连通图，则有可能删除顶点使[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]变成不连通的当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]不是完全图。

答案：

解：如果[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是完全图，则每步移除一个点，剩下的图仍然是完全图，因此绝不会出现非连通图。相反，如果边[tex=1.071x0.786]C9VbywV/RPuZbJOw0bvX8g==[/tex]不在[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]图中了，那么移除所有除了[tex=0.643x0.786]cnVwa8IjZzNSEmAUXJ8VCQ==[/tex]和[tex=0.5x0.786]GWrvJtODhYOBa2bpkSPSFQ==[/tex]的点将会得到非连通图。

举一反三

内容

0
假设图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]采用邻接表存储,编写一个实现连通图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的深度优先遍历(从顶点[tex=0.5x0.786]GWrvJtODhYOBa2bpkSPSFQ==[/tex]出发)的非递归算法.
1
当且仅当[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的一条边[tex=0.5x0.786]WKYr2kz69xrVCyPvbyVG1w==[/tex]不包含在[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的闭迹中时，[tex=0.5x0.786]WKYr2kz69xrVCyPvbyVG1w==[/tex]才是[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]的割边。
2
图[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个顶点，[tex=2.357x1.143]dkoxwOpyXKTw0HsOj3nnBg==[/tex]条边，证明[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]中至少有一个顶点度数大于等于[tex=0.5x1.0]/BQKP5E8YnupUQ2sDg7w1Q==[/tex]。
3
证明：若[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]和[tex=0.857x1.0]h610M+sGyf59WggKwaDo1Q==[/tex]是同构的有向图，则[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]和[tex=0.857x1.0]h610M+sGyf59WggKwaDo1Q==[/tex]的逆图也是同构的。
4
证明:若群[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]只有有限多个子群,则[tex=0.786x1.0]JTRtgqQ00R3dUQzwS4iwbg==[/tex]是有限群.