证明 :κ ≤ κ′ ≤ δ 图论 |
您所在的位置:网站首页 › 点连通度与边连通度 › 证明 :κ ≤ κ′ ≤ δ 图论 |
证明:点连通度小于等于边连通度小于等于最小度 κ:连通度,图G所具有的k顶点割中最小的k κ′ :边连通度,图G中所有k边割中最小的k δ :最小度 证: 先证κ′ ≤ δ 若G是平凡的,则κ′ = 0 ≤ δ。否则,与度为δ的点相连的所有边就构成了G的一个边割,由此可得:κ′ ≤ δ
再证κ ≤ κ′ 当κ′=0时,G是平凡图或不连通的,κ ≤ κ′显然成立。否则,一定存在边数k=κ′的边割,所以至多删除该边割中的κ′个点使得G不连通,由此得:κ ≤ κ′ 综上所述:κ ≤ κ′ ≤ δ证明完毕 书中原证明:
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |