下载文档原格式
离散数学及应用课件离散数学是数学的一个重要分支，它研究的是数学离散对象，如集合、图、树、数等。
它涵盖了一系列丰富而又有深度的主题，包括集合论、图论、数论、逻辑学等。
这些主题不仅在数学领域有着广泛的应用，也在计算机科学、物理学、经济学等多个领域有所涉及。
一、离散数学的主要内容1、集合论：集合论是离散数学的基础，它研究的是集合及其性质和运算。
集合论中的基本概念包括元素、集合、子集、并集、交集、补集等。
2、图论：图论是离散数学中一门研究图形和网络结构的学科。
图论中的基本概念包括节点、边、路径、环、子图等。
图论在计算机科学、电子工程、交通运输等领域都有广泛的应用。
3、数论：数论是研究整数性质和运算的学科。
数论中的基本概念包括整数、素数、合数、约数、倍数等。
数论在密码学、计算机科学等领域有着重要的应用。
4、逻辑学：逻辑学是研究推理和证明的学科。
逻辑学中的基本概念包括命题、推理、证明、反证等。
逻辑学在人工智能、哲学、法学等领域有着广泛的应用。
二、离散数学的应用1、计算机科学：离散数学在计算机科学中的应用广泛而重要。
例如，图论被用于解决计算机科学中的一些基本问题，如排序问题、旅行商问题等。
离散数学还在计算机科学的其他领域有所应用，如算法设计、数据结构、数据库系统等。
2、物理学：离散数学在物理学中的应用也十分广泛。
例如，量子力学和统计力学的理论框架中都有离散数学的影子。
离散数学还在固体物理学、分子物理学等领域有所应用。
3、经济学：离散数学在经济学中的应用也日益增多。
例如，离散数学被用于研究金融市场中的复杂行为，以及分析经济数据的模式和趋势。
离散数学还在博弈论、决策理论等领域有所应用。
三、总结离散数学作为数学的一个重要分支，其理论和应用已经渗透到科学的各个领域。
学习和研究离散数学，不仅可以增强我们的数学素养，还可以提高我们的逻辑思维能力和解决问题的能力。
因此，我们应该重视离散数学的学习和应用。
离散数学是数学的一个重要分支，它研究的是离散量的结构及其相互关系。
第五章图论杨圣洪D形式定义：三元组(V(G),E(G),M(E,V))称为图。
其中V(G)为点的集合(非空集)，E(G)是边集，M(E,V)=边与点连接关系。
常简化为二元组 (V(G),E(G))称为图。
简记为G=(V,E)。
5.1图的概念与描述-邻接矩阵对于有向图，如果从结点vi到结点vj之间有一条边，则a(i,j)=1，否则为0。
由于结点vi到vj有一条边，反过来vj到vi之间不一定有一条，故不一定对称。
对于无向图，如果结点vi到Vj有一条边，则a(i,j)=1，否则为0。
由于Vi到Vj有一条边时，反过来Vj到Vi肯定也有一条边。
故它是对称的。
⎢⎢⎢⎢⎣⎡1110⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡111011010001101100011a b c de1e2e3e4e5e6V={a, b, c, d}E={e1,e2,e3,e4,e5,e6}|V|称为结点数，记为n 该值有限，有限图|E|称为边数，记为m.该值有限。
有限图无限图如果每条边都有方向的，则为有向图。
如果每条边都没有方向，则为无向图。
某些边有方向，某些边没有方向，混合图有向图无向图与D相邻,e1与A、D相关，D为A的后继。
点与边关联相邻，e1与a、b相关联。
自环/自旋。
某两个点之间，称为该点的度数：=4, 有向图某结点的边，也称为“负边”，负度某结点的边，也称为“正边”，正度各点度数和=边数的2倍∑deg(v)=2|E|=2m (为偶数)证明：先去掉所有的边，每个点、整个图的度数为0增加一条边e=(u,v)，使结点u与v的度数的各增加1 。
每增加一条边使整个图的度数增加2。
∑deg(v)=2|E| =2m(为偶数)握手定理边数=5，(2*5)，边数=66)图中度数为奇的结点有偶数个用Vo表示度数为奇(odd)的结点集合，Ve为偶(even)的结点的集合,则有：∑e deg(v)+ ∑o deg(v)= ∑deg(v)=2m。
因Ve中每点度数均为偶数⇒∑e deg(v)为偶数，不妨记为2k⇒∑o deg(v)=2m-2k=2(m-k) ，由于Vo中每个结点的度数为奇数，不妨依次记为2n1-1,2n2-1,…,2n t-1，t为个数⇒其和为2(n1+n2+…n t)-1-1-…-1=2n'-t ⇒2n‘-t=2(m-k) 个数t=2(m-k)-2n'=2(m-k-n'):A(5) B(3)共2个:B(3),D(3)共2个n个结点完全图Kn的边数=n(n-1)/2 Kn:n个结点的完全图⇒该图的任何两个结点之间都有边相连⇒每个点都与其它n-1个点之间有边相连⇒每个点度数为(n-1)，n个点的度数和n(n-1),而整图的度数和为n(n-1)=边数2倍=2m⇒n(n-1)=2m，故边数m=n(n-1)/2由组合学可知m=C(n,2)⇒证明了c(n,2)=n(n-1)/2说明：简单图中点的度≤(n-1)，边数≤n(n-1)/2非空简单图一定存在度相同的结点证明:图G的结点数记为n。
