成功营销网站,58同城招聘网 找工作,软件开发文档,网站建设哪个公司好文章目录 图的基本概念欧拉图与哈密顿图树平面图代数系统群与环格与布尔代数 图的基本概念 图的阶#xff1a;图中的顶点数 #xff0c;n 个顶点被称为 n 阶图零图#xff1a;一条边都没有 平凡图#xff1a;一阶零图基图#xff1a;将有向图的各条有向边改成无向边所得到… 文章目录 图的基本概念欧拉图与哈密顿图树平面图代数系统群与环格与布尔代数 图的基本概念 图的阶图中的顶点数 n 个顶点被称为 n 阶图零图一条边都没有 平凡图一阶零图基图将有向图的各条有向边改成无向边所得到的无向图称为该有向图的基图关联次数可能取值为012 分别是边与顶点没有关联vi !vj , 环孤立点图中没有边关联的顶点区分邻域闭邻域等相关概念 也就是对于无向图来说邻域就是与v 相邻的顶点闭邻域就是邻域加上顶点本身关联集就是与顶点关联的边的合集 对于有向图来说后继元素就是看v 的出度的元素的合集先驱元素就是看 v 的入度的元素的合集邻域就是二者的并加上顶点本身就是闭邻域平行边对于无向图两个顶点之间的无向边多于1条平行边的条数被称为重数对于有向图两个顶点之间的有向边同起点同终点的边多于1条多重图与简单图含有平行边的图是多重图不含平行边以及环的图是简单图度数对于无向图就是顶点相邻的边的个数一个环算2度对于有向图分为出度d(v),入度d-(v) 出度加入度 是该顶点的度一个环有一个入度和一个出度认识最大度与最小度的符号度数为1的顶点是悬挂顶点与它相关联的边是悬挂边度为偶奇数的为偶奇度顶点握手定理无向图中所有的顶点的度数之和为边数的2倍有向图中所有的顶点的度数之和为边数的2倍所有顶点的入度等于出度可图化度数列之和为偶数 可简单图化至少每个顶点的度数小于 n-1 ,但是具体的情况还是要画图才知道图的同构阶数相同边数相同度数列相同也只是必要条件n阶无向完全图n(n-1)/2条边)n 阶有向完全图n(n-1) 条边 n 阶竞赛图n(n-1)/2条边)n 阶竞赛图的基图是无向完全图k-正则图无向图中每个顶点的度数为 k (n 阶 k - 正则图的边数 kn/2 ,当 k 为奇数n 一定为偶数了解子图生成子图以及导出的子图子图的顶点和边都可以在母图中任意找而生成子图的顶点为全部的顶点导出的子图的顶点可以随便找但是边的话要按照母图的来选取补图对于无向简单图来说补图就是无向完全图减去原来的图中相对应的边但是顶点数不变补图与自身同构的图称为互补图删除边删除顶点边的收缩加新边 通路与回路 在n 阶图中如果从顶点 u 到 v 存在通路则 u 到 v 一定存在长度小于等于 n- 1 的通路回路的话就是 n 的回路简单不一定初级但是初级一定简单顶点不同的图边一定不会重复图的连通于连通度点割集与割点边割集与桥割边分别在原来的图中减去点边图的连通度增加 点连通度点割集的最小的元素的个数--》就是改变原来的图从连通到非连通最少要减少的顶点数完全图的点连通度为n-1. k-连通图边连通度同理就是要将一个图从连通图变成非连通图所最少减少的边数 r 边 - 连通图对于任意的无向完全图 点连通度 边连通度 最小度可达弱连通图单向连通图强连通图 单向连通图的判定存在过每个顶点的通路强连通图的判定存在过每个顶点的回路二部图 n 阶零图n2) 是二部图二部图的判定无向图是二部图当且仅当 G 中没有奇数圈关联矩阵邻接矩阵可达矩阵 对于无向图的关联矩阵 1每列之和为2 2每行之和为对应的顶点的度数 3相同列的是平行边 4某一行和为0表示该点为孤立点 5全部数加起来是边数的两倍有向图的关联矩阵 1出度标1入度标-1 2每一列刚好一个1一个-1 3每一行中出度为1 的个数入度为-1 的个数 4平行边的列是相同的 51 的个数等于 -1 的个数邻接矩阵(有向图是有方向的 可以用邻接矩阵的幂次相加就可以得到从 vi 到 vj 的通路可知长度 有向图的可达矩阵自身可以可达自身 1对角线为1可达的就是1否则为0 欧拉图与哈密顿图 欧拉图与半欧拉图都是经过所有的边一次仅仅一次一个是回路一个是通路平凡图是欧拉图欧拉图的判定无向图G 是欧拉图当且仅当G 是连通图且没有奇数度顶点有向图是欧拉图当且仅当D 是强连通的且每个顶点的入度等于出度半欧拉图的判定无向图G 是连通的且恰有两个奇数度的顶点有向图D 是半欧拉图当且仅当 D 是单向连通的且恰有两个奇数度的顶点其中一个入度比出度大1另外一个出度比入度大1 其余顶点的入度等于出度G 是非平凡的欧拉图当且仅当 G 是连通的且为若干个边不重的圈的并圈和环并不影响欧拉性哈密顿图和半哈密顿图都是经过所有的顶点一次仅仅一次前者是回路后者是通路平凡图是哈密顿图哈密顿图的性质 p(G-V) |V| 就是删去某些顶点后G- V 的连通分支数小于删去的顶点数半哈密顿图的性质 p(G-V) |V| 1 就是删去某些顶点后G- V 的连通分支数小于删去的顶点数 1存在哈密顿通路在n 阶无向简单图中任意不相邻的顶点 u,v , d(u) d(V) n-1存在哈密顿回路在n 阶无向简单图中任意不相邻的顶点 u,v , d(u) d(V) n在n 阶无向简单图G中任意不相邻的顶点 u,v , d(u) d(V) nG 为哈密顿图当且仅当GU(u,v)为哈密顿图n 阶竞赛图都有哈密顿图 树 树无向树连通无回路的无向图 森林每个连通分支都是树的无向图 平凡树平凡图树叶悬挂顶点 分支点度数大于等于2的顶点n阶 m 条边的无向图(等价条件 1G 是树 2G中任意的两个顶点之间存在唯一的路径 3G 中没有回路且 m n-1 4G 是连通的且mn-1 5G 是连通的且任何的边都是桥 6G 中没有回路但是在任何不同的顶点之间加一条新边后可以得到唯一一条包含新边的圈n 阶非平凡的无向树中至少有两片树叶对于树的相关的证明一定要利用 度数与边的关系毕竟树是特殊的图生成树如果无向图G 的生成子图T是树则称T 是 G 的生成树。T 是G 的生成树G 在 T 中的边称为 T 的树枝不在的称为 弦T 的所有的弦的导出的子图称为 T 的余树 记作 T非无向图的生成树存在当且仅当G 是连通图n 阶m 条边无向连通图则mn-1基本回路与基本回路系统的的求法G是n 阶m 条边 1对于G 的生成树T , G 中T 的弦的个数为 m-n1,对于每个弦与T 中的树枝结合可以生成一个圈称为基本回路或者基本圈全部的圈的总集合被称为T 的基本回路系统m-n1 为G 的圈的秩 无向连通图的圈的秩与生成数的选取无关都是 m-n1,但是具体的基本回路系统可能不同任意一简单回路都可以表示为基本回路的环和割集生成树的割集只含某一树枝其余都是弦。不同的树枝对应的割集不同割集组成基本割集基本割集组成基本割集系统n-1 为 G 的割集的秩连通图的秩确定但是具体的基本割集系统不确定 求最小生成树 避圈法克鲁斯卡尔算法从圈出发依次找边的权值最小的边当该边的两个端点位于两个连通分支的时候就可以加入和已有的不构成圈否则就去下一条边根树一个顶点的入度为0其余顶点的入度为1的有向树 有向树有向图的基图是无向树入度为0的顶点是树根入度为1出度为0的顶点是树叶入度为1出度不为0 的顶点是内点内点和树根称为分支点层数从树根到任意顶点的路径的长度称为层数区别于数据结构 树高所有顶点的最大的层数 区分 r 叉树r 叉有序树 r 叉正则树 r 叉正则有序树r 叉完全正则树 r 叉完全正则有序树 上面的区分分别是是否有序 至多 r 个儿子 每个分支点 r 个儿子 每个分支点 r 个儿子加上树叶的层数等于树高最优二叉树赫夫曼算法前缀码任意两个符号都不互为前缀码由一棵正则二叉树可以产生唯一的一个2元前缀码 平面图 平面图将无向图G画在平面上除了顶点以外没有边相交 画出来的图称为G的平面嵌入非平面图无平面嵌入的图K1平凡图K2,K3,K4 ,K5 - e (随便减去一条边 都是平面图平面图的子图都是平面图非平面图的母图都是非平面图 含K3,3 以及 K5 作为子图的图都是非平面图Kn ,n5, Kr,s(r,s3) 都是非平面图设G 是平面图则在G 中加平行边和环之后还是平面图面平凡图划分的每一个区域称为G 的一个面其中有一个无限面外部面其余是有限面内部面 包围每个面的边的回路称为面的边界 边界的长度称为该面的次数 边界都是回路平面图所有的面的次数之和为边数的两倍通一条边被两个面共享极大平面图G 为简单平面图若在G 中任意两个不相邻的顶点之间加上一条边所得的图为非平面图K1平凡图K2,K3,K4 ,K5 - e (随便减去一条边都是极大平面图极大平面图是连通的当且仅当阶数大于等于3时没有割点和桥设G 是n(n3) 阶简单连通的平面图G 为极大平面图当且仅当G 的每个面的次数均为3极小非平面图若在非平面图中任意删除一条边所得的图是平面图K5 K33欧拉公式连通平面图G 的顶点数、边数、面数 分别为 n,m,r ,则有 n-mr 2欧拉公式的推广 1对于含有 k 个连通分支的平面图G ,有 n-mr k1设G 是连通的平面图且每一个面的次数最少是 L ,则 G 的边数m 和顶点数 n ,有 mL(n-2)/(L-2)当G 为 k 个连通分支的平面图的时候mL(n-k-1)/(L-2)设G 是 n 阶 m 条边的 极大平面图则 m 3n-6设G 是 n 阶 m 条边的 简单平面图则 m3n-6设G 是 简答平面图则G 的最小度 小于等于 5同胚如果两个图同构或者通过反复的插入删除2度顶点后同构则两个图同构平面图的判断 1图是平面图当且仅当 G 中不含与 K5 同胚的子图也不含与 K3,3 同胚的子图 2图是平面图当且仅当 G 中不含收缩于K5的子图,也不含能收缩于 K3,3的子图平面图的对偶 平面图的对偶图G* (1)G* 是平面图而且是平面嵌入 (2)G* 是连通图 (3)若e 为 G 中的环则G* 对应 e 为桥若 e 为桥则 G* 对应为 环 (4)大多数情况下G* 为多重图 (5)同一个平面的不同平面的嵌入的对偶图不一定同构相对应的数量关系 自对偶图G* 与 G 同构 轮图是自对偶图 代数系统 单位元和零元如果存在则是唯一的当代数系统的元素大于1时单位元与零元不相等对于可结合的二元运算可逆元素的逆元唯一同类型的代数系统运算个数相同对应运算的元数相同代数常数的个数相同 同种代数系统在同类型代数系统基础上运算的性质相同子代数证明元素是S 子集且满足运算封闭任何的代数系统都有子代数子代数与本身是同种的代数系统平凡子代数最小子代数代数常数与最大子代数自己积代数的形式a1,b1 ·a2,b2 a1oa2,b1*b2代数系统的同态与同构f:V1–V2 ,有f(xoy) f(x)*f(y) ,则称是从v1 到v2 的同态映射同态当 f 是单射时单同态满射满同态双射同构 群与环 半群代数系统S,o ,o 可结合可结合独异点在半群的基础上存在单位元可结合单位元群在独异点的基础上每个元素有逆元可结合单位元逆元偶阶群群中的元素的个数为偶数一定含有二阶元单位元的阶为1大于2 的阶的元素由于本身加上逆元个数的和为偶数对于由于二阶元的逆元为自己在群众也是占据一个位置刚好补上单位元的1 群其实是可以直接写出来 注意元素的幂运算0次幂为单位元正数幂直接算负数幂就用逆元的正数幂元素的阶使得a^k e 的最小的k 一个元素的阶与逆元的阶相等对于群的运算只用留意a b^-1 b^-1 a^-1群是满足消去律的消去律的前提就是满足结合律以及排除零元而群自身就满足结合律以及没有零元如何证明子群在H 非空的前提下 1满足封闭性满足逆元 2将封闭性与逆元结合ab^-1 属于H 3H 为非空的有限子集只用证明封闭即可子群的交仍然是子群子群的并不一定是子群元素a 的生成子群 a 陪集Ha 为H 在G 中的右陪集陪集的性质 1He H 2a 属于 Ha (至少有个单位元 3a 属于 Hb ab^-1 Ha Hb 证明陪集的相等 4H 的所有的右陪集集合构成G 的一个划分 5Ha 与 H 是等势的拉格朗日定理G 为有限群H 为 子群 G 的阶 子群的阶 * 陪集的个数 陪集之间是相互独立的且与子群等势广义并就是G) 重要推论 1n 阶群的元素的阶是n 的正因子即 a^n e 2阶为素数的群一定是循环群循环群简单来说就是由生成元生成的群 1无限循环群G只有两个生成元a 和 a^-1 2n 阶循环群G有从0到n-1 与n 互素的数的个数个生成元这个是G 的生成元的个数G 的生成元对于任何小于n 且与 n 互质的自然数 r,a^r 是G 的生成元且每一个正因子 d ,都有一个 d 阶子群a ^(n/d) 为相对应子群的生成元区别求生成元以及子群 结合子群的阶以及相对应的生成元来求即可环S,,* :S, 满足交换群交换律结合律单位元逆元 S, * 满足半群结合律单位元 * 对 满足分配律相关性质 1加法中的单位元为乘法中的零元 2a(b-c) ab -ac (分配律交换环乘法* 满足交换律含幺环乘法* 存在单位元无零因子环 ab 0 a0 或者 b 0 (a,b 至少其中一个为加法中的单位元整环满足交换环含幺环无零因子环域整环的基础上去除加法的单位元每个元素都有逆元模n 的整数环如果n 为素数那么为域整数环是整环但是不是域元素的逆不一定是整数 格与布尔代数 格偏序关系x,y 存在最小上界与最大下界如何证明一个代数系统是格证明封闭性证明^,V 成立对偶原理将 换成 ,^ 换成 v 那么称为相对应的对偶命题原命题与对偶命题的真值相同格的性质v,^ 是满足交换律结合律幂等律吸收律注意不满足分配律注意偏序与运算的关系以及相对应的保序关系子格S非空S 在 父格中关于运算^ 和v 封闭 对于下面左上角的题目对于{a,b,d,f} 来说b,d 的最大下界是c ,但是c 不在{a,b,d,f}中所以不是子格分配格满足分配律分配格的判定 1满足相对应的定义但是只用证明一个式子对偶 2判断不是分配格不含钻石格与五角格同构的子格 3小于5元的格都是分配格 4任何一条链都是分配格有补格补元对于a , b 与a 的最大下界是0最小上界是1补元不唯一有界格每个元素大于0小于1无限格也可能是有界格例如幂集格小于自己大于空集有界分配格如果元素存在补元则补元唯一存在有补分配格布尔代数 任何等势的布尔代数都同构于某一幂集格任何有限的布尔代数的基数为 2^n,布尔代数中的元素的补元是唯一的布尔代数与原子
