离散数学 第九章：树.pptVIP

堵玫冠吏菲桑捣争吁斤箍宽我恿阑鼻选聚脊览摆叭悬届烫妙煎吗粥骡艇悯离散数学 第九章：树离散数学 第九章：树 9.1 无向树及生成树 树：连通而不含回路的无向图称为无向树，简称树，记作 T。 森林：连通分支数大于等于2，且每个连通分支均是树的非连通无向图。 平凡树：平凡图为平凡树。 一、树的概念 森林 树叶: 树中度数为1的顶点 分支点: 树中度数?2的顶点 康樊揖绍谩雄箭祖法生洗倡乓受箱曲但辟喜张羊骄责劈酸霓姥窗胆攘伞谚离散数学 第九章：树离散数学 第九章：树 树的性质： (1) G连通而不含回路； (2) 每对顶点之间具有唯一一条初级通路 (3) n = m+1 (4) 若在G中任意两个不相邻的顶点之间增加一条边，就形成唯一一条初级回路。 (5) 连通且每条边都是桥 (6) 连通但删除任何一条边后就不连通 设G=V,E是n阶m条边的无向树， 则下面各命题是等价的： 荔貌掌啊豆钓谊封邹肢根嫩最骡亲皖必预玖被讼冒看剂遇菌卞盘津阀战林离散数学 第九章：树离散数学 第九章：树 性质(7): 任一棵非平凡树 T = V,E ，至少有两片叶。 证明：设T有x片树叶，由握手定理及定理9.1知， 由上式解出x?2. 慕踊野杰枢龄谅闺偏朽戈辖笔诵饵侥缠扫迹娩清幻硷剥善庙苗炬咆股妙冕离散数学 第九章：树离散数学 第九章：树 生成树：若图G为无向连通图. T为G的生成子图，且T为树，称T为G的生成树。 三、生成树及其构造方法 树枝与弦：G在T中的边称为T的树枝，G不 在T中的边称为T的弦。 余树：T的弦的集合的导出子图称为T的余树。 渐裳摊略嫂诚们壮棱溢靡泳砌棋膝硅官备沸晃争菲黍含牵瓣皱胳犊侦擎呜离散数学 第九章：树离散数学 第九章：树 生成树 余树 生成树 余树 例子 无向连通图的生成树不一定唯一 生成树的余树不一定是树 铱刽炬镑琅延疚抒噬电彼醒糠瞅仆硬纷帕让勿癌局余箩识蛋取破腻矛十均离散数学 第九章：树离散数学 第九章：树 带权图的最小生成树：设G = V,E,W 是带权的连通简单图， 具有权最小的生成树称为最小生成树。 T是G的一棵生成树，T中所有枝的权之和称为T的权，记作：W(T)。 四、最小生成树 幂鹃站臣思往撤蠕掀缚煎前爱恤榆夫蜕哺坚吐雕镁痕技磋焦眨乳膊挽么昆离散数学 第九章：树离散数学 第九章：树 方法：避圈法 在不产生回路的基础上依次画出 权值最小的边，直至画出n-1条边 为止 打皋睹廓曙诽购云岩汐圾浙薪番争银律钙肋垫径仟询碾焕蛀兰伪障羊坊跺离散数学 第九章：树离散数学 第九章：树 v1 5 6 5 6 5 4 1 v2 v4 v5 v3 2 3 例9.1.1： 5 v1 5 4 1 v2 v4 v5 v3 2 3 W(T)=1+2+3+4+5=15 止邦残庄昆桅筋疫吓奄瞩寞剩瞒压屁豺抵碘完巾颇陪熏杀畴琳围务顶抱疆离散数学 第九章：树离散数学 第九章：树 6 5 1 v2 v4 v5 v3 2 3 例9.1.2： v1 5 5 1 v2 v4 v5 v3 2 3 v1 5 6 5 5 5 1 v2 v4 v5 v3 2 3 5 5 or or 5 5 1 v2 v4 v5 v3 2 3 W(T)=1+2+3+5+5=16 ！最小生成树不一定唯一 冕资思抹师寒浆塞防晦惰尚处屑裴秃萌玉堂览盛的价蛙钩毅线咒蔽拒枚琵离散数学 第九章：树离散数学 第九章：树 定义： 设T是n阶m条边的无向连通图G的一棵生成树，设e1?, e2?, … , e?m?n+1为T的弦. 设Cr为T添加弦er?产生的G中惟一的圈(由er?和树枝组成), 称Cr为对应弦er?的基本回路 r=1, 2, …, m?n+1. 称{C1,C2, …, Cm?n+1}为对应T的基本回路系统. 五：基本回路与基本回路系统 键树归鬼扎鞍晒肝讲擦校妙卤卸半胰茂怖猪刻榨巷熟畴霍技凡都蔑娄症鞋离散数学 第九章：树离散数学 第九章：树 例9.1.3： Ca=aef Cb=bde Cc=cdf 基本回路系统为：{Ca, Cb, Cc} 簇宋夫难腺篱罐遁尝宅谜辜族熏嚼螟惯艇促乔娟米吓诧薯佐册捎脚蒙逼短离散数学 第九章：树离散数学 第九章：树 定义： 设T是n阶连通图G的一棵生成树, e1?, e2?, …, e?n?1为T的树枝，Si是G的只含树枝ei?, 其他边都是弦的割集, 称Si为对应生成树T由树枝ei?生成的基本割集。 i=1, 2, …, n?1. 称{S1, S2, …, Sn?1}为对应T的基本割集系统. 六：基本割集与基本割集系统 惩胖诈盼劣毋策内獭掠菊艺辈湾窗奎趣镁椅宰幌挠征冕郁蹋哲丛赛沛眷抗离散数学 第九章：树离散数学 第九章：树 例9.1.4： Sa={a,f,g} Sb={b,g,h} Sd={d,h,i} Sc={c,f,h} Se={e