问答题
设T为任意的无向树,问T的点连通度κ和边连通度λ分别为几?
【正确答案】
当T为平凡树时,κ=λ=0;当T为非凡平树时,κ=λ=1.
当T为平凡树时,T为完全图K
1
,而完全图K
n
的点连通κ与边连通λ都等于n-1,所以,κ=λ=0.
当T为非平凡树时,又分两种情况讨论.
①T是2阶树,此时T为K
2
,所以κ=λ=1.
②当T的阶数n≥3时,T一定有非树叶顶点,非树叶顶点都是割点,所以κ=1,又T的每条边都是桥,所以λ=1.
【答案解析】
提交答案
关闭