谁有离散数学的概念总结呀???高分急求!!!
发布网友
发布时间:2022-07-23 04:09
我来回答
共2个回答
热心网友
时间:2023-11-22 21:40
图论基本概念
重要定义:
有向图:每条边都是有向边的图。
无向图:每条边都是无向边的图。
混合图:既有有向边又有无向边的图。
自回路:一条边的两端重合。
重数:两顶点间若有几条边,称这些边为平行边,两顶点a,b间平行边的条数成为(a,b)的重数。
多重图:含有平行边的图。
简单图:不含平行边和自回路的图。
注意!一条无向边可以用一对方向相反的有向边代替,因此一个无向图可以用这种方法转化为一个有向图。
定向图:如果对无向图G的每条无向边指定一个方向由此得到的有向图D。称为的G定向图.
底图:如果把一个有向图的每一条有向边的方向都去掉,得无向图G称为的D底图。
逆图:把一个有向图D的每条边都反向由此得到的图称为D的逆图。
赋权图:每条边都赋上了值。
出度:与顶点相连的边数称为该定点的度数,以该定点为始边的边数为出度。 入度:以该定点为终边的边数为入度。
特殊!度数为零的定点称为孤立点。度数为一的点为悬挂点。
无向完全图:在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。Kn
完全有向图:在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。
竟赛图:阶图中如果其底图是无向完全图,则程此有向完全图是竟塞图。
注意!n阶有向完全图的边数为n的平方;无向完全图的边数为n(n-1)/2。
下面介召图两种操作:①删边:删去图中的某一条边但仍保留边的端点。
②删点:删去图中某一点以及与这点相连的所有边。
子图:删去一条边或一点剩下的图。
生成子图:只删边不删点。
主子图:图中删去一点所得的子图称的主子图。
补图:设为阶间单无向图,在中添加一些边后,可使成为阶完全图;由这些添加边和的个顶点构成的图称为的补图。
重要定理:
定理5.1.1 设图G是具有n个顶点m条边的有向图,其中点集V={v,v,….,v}
deg+(vi)=deg-(vi)=m
定理5.1.2 设图G是具有n个顶点m条边的无向图,其中点集V={v,v,v,……,v}
deg(vi)=2m
推论 在无向图中,度数为积数的顶点个数为偶数。
通路和富权图的最短通路
1通路和回路
基本概念:
通路的长度:通路中边的条数。
回路:如果通路中始点与终点相同。
简单通路:如果通路中各边都不相同。
基本通路:如果通路中各顶点都不相同。显然(基本通路一定是简单通路,但简单通路不一定是基本通路)
可达:在图G中如果存在一条v到d通路则称从v到d是可达。
连通:在无向图中如果任意两点是可达的,否则是不连通的。
强连通:在有向图中如果任意两点是互可达的。
单向连通:在有向图中如果存在任意两点的通路。
弱连通:在有向图中如果其底图是连通的。
权:在图的点或边上表明某种信息的数。
赋权图:含有权的图。
赋权图的最短通路问题的算法:先求出到某一点的最短通路,然后利用这个结果再去确定到另一点的最短通路,如此继续下去,直到找到到的最短通路为止。
指标:设V是图的点集,T是V的子集,且T含有z但不含a,则称T为目标集。在目标集T中任取一个点t,由a到t但不通过目标集T中其它点所有通路中,个边权和的最小者称为点t关与T的指标记作DT(t)。
图和矩阵
住意两个的区别:A·A 中元素的意义:当且仅当a 和a 都是1时,a a =1而a 和a 都为1意味着图G中有边(v ,v )和(v ,v )。于是可得如下结论:从顶点v 和v 引出的边,如果共同终止于一些顶点,则这些终止顶点的数目就是b 的值;特别对于b ,其值就是v 的出度。
A ·A中元素的意义:当且仅当a 和a 都为1时,a a =1,这意味着图中有边(v ,v )和(v ,v )。于是的得如下结论:从某些点引出的边,如果同时终止于v 和v ,则这样的顶点数就是的值。特别对于b ,其值就是的v 入度。
幂A 中元素的意义:当m=1时,a 中的元素=1,说明存在一条边(v ,v ),或者说从v 到v 存在一条长度为一的通路。
A 中元素a 表示从v 到v 的长度为m的所有通路的数目。
欧拉图
主要定义:
如果图中存在一条通过图中个边一次且仅一次的回路,则称此回路为欧拉回路,具有欧拉回路的图称为欧拉图。
如果图中存在一条通过图中各边一次且仅一次的通路,则称此回路为欧拉通路,具有欧拉通路的图称为半欧拉图。
主要定理:一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数。
一个无向连通图是半欧拉图的充要条件是图中至多有两个奇数度点。
设图G是有向连通图,图G是欧拉图的充要条件是图中每个顶点的入度和出度相等。
设图G是有向连通图,图G是半欧拉图的充要条件是至多有两个顶点,其中一个顶点入度比它的出度大1,另一个顶点入度比它的出度少1;而其他顶点的入度和出度相等。
哈密顿图
主要定义:如果图G中存在一条通过图G中各个顶点一次且仅一次的回路,则称此回路为图的哈密顿回路;具有哈密顿回路的图称为哈密顿图。
如果图G中存在一条通过图G中各个顶点一次且仅一次的回路,则称此回路为图的哈密顿回路;具有哈密顿回路的图称为哈密顿图。
主要定理:设图G是哈密顿图,如果从G中删去个p顶点得到图G’,则图G’的连通分支数小于等于p。
设图G是具有n个顶点的无向简单图,如果G中任意两个不同顶点的度数之和大于等于n-1,则具有哈密顿通路,即G是半哈密顿图。
设图G是具有n个顶点的无向简单图,如果G中任意两个不同顶点的度数之和大于等于n,则G具有哈密顿回路,即G是哈密顿图。
参考资料:http://www.renwei.com/yzren/showthread.php?t=29079
热心网友
时间:2023-11-22 21:40
http://wenku.baidu.com/view/4ae2b3d528ea81c758f57863.html
百度文库,不错的,呵呵,推荐
谁有离散数学的概念总结呀???高分急求!!!
16. 无向完全图:在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。17. Kn完全有向图:在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。18. 竟赛图:阶图中如果其底图是无向完全图,则程此有向完全图是竟塞图。19. n阶有向完全图的边数为n的平方...
谁有离散数学的概念总结呀???高分急求!!!
无向完全图:在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。Kn 完全有向图:在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。竟赛图:阶图中如果其底图是无向完全图,则程此有向完全图是竟塞图。注意!n阶有向完全图的边数为n的平方;无向完全图的...
离散数学的概念是什么?
离散数学定义: t(R) = R u R^2 u R^3 u... 其中R^(n+1) = R^n 复合 R 矩阵表示: M(R) = M + M^2 + M^3 +...+M^n(其中加为逻辑加) 所以我们只要按照这个公式每次更新M,最后的Mn就是传递闭包。大数据技术专业学的有:程序设计实践、离散数学、数据结构、数学分析。1、程...
什么是离散数学,其学习要点有哪些?
离散数学2:基本概念 公式层次:单个的命题变项A是0层公式。如果A是n层公式,B是m层公式,那么_A是n+1层公式;C=A∧B,C=A∨B,C=A→B,C=A↔B的层次是:max(n,m)+1。比如(_(p→_q)∧((r∨s)↔_q)的层次计算就是:01001 211 32 4 4层公式 设p1,p2,p3?pn是公...
离散数学的基本概念有哪些?
离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科,是现代数学的一个重要分支。离散的含义是指不同的连接在一起的元素,主要是研究基于离散量的结构和相互间的关系,其对象一般是有限个或可数个元素。随着信息时代的到来,工业革命时代以微积分为代表的连续数学占主流的地位已经发生...
怎样去学习离散数学? 有点迷茫
之处,离散数学,计算机科学,当然作为课程与其他课程的沟通,也有其自身的特点,现在的特点进行了简要分析,我们把它作为考试内容。1,定义和定理。离散数学是在上面定义的学科大量的逻辑推理。因此,对概念的理解,是我们学习这门学科的核心。基于这些概念,尤其应注意概念之间的联系,以及这些链接的实体的...
在日常生活中,离散数学的概念如何应用?
艺术创作:离散数学的对称性和分形几何在艺术创作中有广泛应用。例如,通过对称性的破缺和恢复,可以创造出美丽的图案;通过分形几何,可以创造出复杂的形状。总的来说,离散数学的概念和应用渗透到日常生活的各个方面,无论是科学技术,还是文化艺术,都离不开离散数学的理论和方法。
学习离散数学的技巧有什么?
1.理解基本概念:离散数学的基础是集合论,因此要花时间去理解和掌握集合论的基本概念,如集合、元素、子集等。2.多做练习题:离散数学是一门实践性很强的学科,通过做练习题可以加深对知识点的理解和记忆。可以从简单的题目开始做起,逐渐提高难度。3.学会证明:离散数学中有很多定理和性质需要证明,...
离散数学相关的知识有什么?
离散数学是研究离散对象的数学分支,主要包括以下几个方面的知识:1.集合论:研究集合及其运算、关系、函数等基本概念。集合论是离散数学的基础,为其他领域提供了理论基础。2.逻辑与证明论:研究命题逻辑、谓词逻辑、模态逻辑等逻辑系统,以及证明方法、定理和推理规则。逻辑与证明论在计算机科学、人工智能等...
如何理解离散数学的几个基本概念的含义?
y是约束变量 (5)F(x)中的x是约束变量,G(x,y,z)中的y是约束变量,x,z是自由变量,H(x,y,z)中的z是约束变量,x,y是自由变量。离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科,是现代数学的一个重要分支。离散的含义是指不同的连接在一起的元素。