a
b
e
Q1 a
b e
Q2
a
b
e
d
c
d
c
d
c
f
f
f
a
b Q3 a
b
e
e
d
c
f
d
c
Q4
f
结论:汇集于 同一结点的支 路都是G的一个 割集。
特点:①全移,G一分为二 ②少移一条,G连通。
3
例:判断下图中各支路集合是否是图G的割集?
Q5
a
b
e
d
c
f
(b, d, e, f )是
Q6
a
b
e
d
c
f
(a, b, c, d ) 也是
Q7
a
b
e
d
c
f
(a, e, f ) 也是
特点:①全移,G一分为二 ②少移一条,G连通。
4
例:判断下图中各支路集合是否是图G的割集?
Q8 a d
b e
c
f
Q9 a d
b e
c
f
少移去e,G仍为两部分, 全移,G被分为三部分,
(a, d, e, f )不是G的割集。 (a, b, c, d ,e )不是G的割集
100
010
BT il=
0 1
0 1
1 0
1 0 1
il1
i1
il1 il2 il3
il2
il3 il1+il2
il1il3
i3 i4 i2 i5
i5 , i6 ]T ②
① i3 3 Ⅱ i2
2
4 i6Ⅲ
i4