离散数学-基本割集的找法

前言:因为做离散数学的时候发现一些重要的基础知识总是忘记,觉得写下来应该可以记得更牢固一些,所以记录平时的知识,随学随更。

基本割集:由树的一条树枝和若干连支构成的割集。

寻找基本割集的步骤
1.移去所有连支,余下一棵树。

2.移除tk,则余下子图被分成N1,N2两部分。

3.tk和连接N1,N2的连支l1,l2,...,ln构成基本割集。

4.割集的方向,以tk所指的方向为正方向。

例题:寻找支路3的基本割集,树枝为2,3,5.

1.移去所有连支,余下一棵树。

2.移去支路3,树被分成两个孤立部分N1,N2。

3.则支路3和连接N1,N2的连支1,4,6构成基本割集。

原网址:https://wenku.baidu.com/view/dd66d23783c4bb4cf7ecd1c9.html

原文地址:https://www.cnblogs.com/whitor/p/Discrete_mathematics.html