离散数学

您所在的位置:网站首页 生成树的基本割集 离散数学

离散数学

2024-07-11 05:57| 来源: 网络整理| 查看: 265

一.环路空间

1.定义(有些定义不理解没事的,看例题里的应用就好)

环路:G中圈(圈:起点和终点相同的路径)或若干个边不重圈的并

(简单一句话:图G里面所有大圈圈和小圈圈集合起来)

规定:Ø是环路

补充:圈&简单回路==>环路,反之不一定成立~

C环:G中所有环路的集合

Ω:G各边的导出子图的集合

(导出子图:

2.定理(通俗解释在下方,有的符号真的不太好打/(ㄒoㄒ)/~~)

(1)G,生成树T,基本环路系统C基,C基中每个Ci(r个)对应的弦ei

==>e1,e2,...er均在。。。中

(环合运算不懂的不要急,下面有例题)

(2)G的两个回路环和以后==>得到的是G的环路

(3)推论:G的两个环路环和以后==>得到的是G的环路

~~~(2)&(3)记忆方式:两个回路或者环路,进行环合,得到环路

(4)G的任一回路T的基本回路/若干个基本回路的环和

(5)推论1:G的任一环路T的基本回路/若干个基本回路的环和

~~~(4)&(5)记忆方式:任一回路或者环路,都是T的基本回路/他们的环和

         推论2:m-n+1e1,e2,...er均在。。。中

(2)G的两个断集进行对称差以后==>得到的是G的断集

(3)G的任一回路T的基本割集/若干个基本割集的对称差

(4)S断是Ω的n-1维的子空间

4.举例



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3