图论复习课ppt课件.ppt

《图论复习课ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、代数结构与图论复习课代数结构代数系统与运算半群、独异点代数系统的群与子群主要内容陪集与拉格朗日定理同态与同构环域二种特殊阿贝尔群的群循环群环、整环与域的关系:环交换环含幺环整环域无零因子环格与布尔代数偏序集格(任意两个元素有最小上界和最大下界)有界格(全上界和全下界)有限格(有限个元素)分配格a∧(b∨c)=(a∧b)∨(a∧c)有补格(补元)a∨(b∧c)=(a∨b)∧(a∨c)布尔格(有补分配格)格的基本性质:自反性:a≤a反对称性:a≤b,b≤aa=b传递性:a≤b,b≤ca≤c交换性:a∨b=b∨

2、a，a∧b=b∧a结合性:a∨(b∨c)=(a∨b)∨c，a∧(b∧c)=(a∧b)∧c幂等性:a∨a=a，a∧a=a吸收性:a∨(a∧b)=a，a∧(a∨b)=a保序性:b≤ca∨b≤a∨c，a∧b≤a∧c分配不等式:a∨(b∧c)≤(a∨b)∧(a∨c)(a∧b)∨(a∧c)≤a∧(b∨c)a≤a∨b，b≤a∨b，a∧b≤a，a∧b≤ba≤c，b≤ca∨b≤ca≤b，c≤da∨c≤b∨d，a∧c≤b∧da≤b↔a∧b=a↔a∨b=ba∨0=a，a∧1=a布尔代数a∨1=1，a∧0=0(

3、a')'=aa∨a'=1，a∧a'=0(a∨b)'=a'∧b'（a∧b)'=a'∨b'a∧b'=0↔a≤b↔a∨b'=1图论邻接点图的基本概念邻接边环（自回路）结点的度数（入度、出度）补图子图、生成子图路、回路连通图非连通图→连通分支无向图点割集→割点边割集→割边连通图强连通有向图单侧连通弱连通邻接矩阵图的矩阵表示可达性矩阵完全关联矩阵零图几种特殊的图完全图二部图欧拉图哈密顿图平面图树边界平面图面的次数极大平面图极小非平面图对偶图森林连通分支树无向树有向树树叶分枝点（内点）无向树生成树树枝弦余树带权树边权树权→最小

4、生成树根树树根有向树分枝点（内点）r叉树正则r叉树带权二叉树的权→最优树一．判断题1．设为整环，

5、R

6、=n，则是域。（）2．在有界分配格中，一个元素若有补元，则补元一定是唯一的。（）3．若一个有向图为强连通图，则它一定为欧拉图。（）4．一个循环群的生成元一定是唯一的。()二．单项选择题(在每小题的四个备选答案中选出一个正确的答案，并将其字母填在题后的括号内。)1．下列命题正确的是()。A.半群中任意一个元素只能有一个逆元B.独异点满足消去律C.群中有多个等幂元D.群运算表中任意两行均不相

7、同2．5阶群（）。A.既是阿贝尔群又是循环群B.是阿贝尔群但不是循环群C.既不是阿贝尔群又不是循环群D.是循环群但不是阿贝尔群3．设布尔代数为，则∣A∣可能的取值为（）。A.9B.12C.25D.164.图G是具有7个结点的无向完全图，那么G（）。A．是汉密尔顿图但不是平面图B．既是汉密尔顿图又是平面图C．是平面图但不是汉密尔顿图D．既不是汉密尔顿图也不是平面图三．给定权1，2，4，6，9，12，15，18构造一棵最优二叉树，求其对应的二元前缀码。四.证明：若n阶简单无向图G的任意两个结点的度数之

8、和大于等于n-1，则G是连通的。