离散数学第7章ppt课件.ppt

ID:59495082

大小:3.42 MB

页数:135页

时间:2020-09-13

离散数学第7章ppt课件.ppt_第1页
离散数学第7章ppt课件.ppt_第2页
离散数学第7章ppt课件.ppt_第3页
离散数学第7章ppt课件.ppt_第4页
离散数学第7章ppt课件.ppt_第5页
资源描述:

《离散数学第7章ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第四篇图论图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究,如1736年欧拉(L.Euler)所解决的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题:例如 迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意,从而在这些问题研究的基础上,又提出了著名的四色猜想和环游世界各国的问题。例:用定理解决哥尼斯堡桥的问题第四篇图论图论不断发展,它在解决运筹学,网络理论,信息论,控制论,博奕论以及计算机科学等各个领域的问题时,显示出越来越大的效果。对于这样一门应用广泛的学科,其包含的内

2、容是丰富的,本篇我们只准备介绍基本的概念和定理,为今后有关学科及课程的学习和研究提供方便。WWW电力网因特网复杂网络的事例——技术网络复杂网络的事例——社会网络朋友关系网演员网科学家合著网科学引文网复杂网络的事例——交通运输网络城市公共交通网道路交通网航空网复杂网络的事例——生物网络神经网络生态网络蛋白质相互作用网络基因网络新陈代谢网络SantaFe研究所的科学家合作网复杂网络的事例——科学家合作网经济物理学科学家合作网复杂网络的事例——科学家合作网复杂网络的事例——中药方剂网示意图点(药材),边(药材之间相互作用),局域世界(方剂)

3、§1图的基本概念定义:图(graph)G由一个三元组表示,其中:非空集合V(G)={v1,v2,…,vr}称为图G的结点集,其成员vi(i=1,2,…,r)称为结点或顶点(nodesorvertices);集合E(G)={e1,e2,…,es}称为图G的边集,其成员ej(j=1,2,…s)称为边(edges)。函数G:E(G)→(V(G),V(G)),称为边与顶点的关联映射(associatvemapping)§1图的基本概念例:G=其中V(G)={a,b,c,d},E(G)=

4、{e1,e2,e3,e4,e5,e6},G(e1)=(a,b),G(e2)=(a,c),G(e3)=(b,d),G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d)abcde1e2e3e4e5e6§1图的基本概念讨论定义:(1)V(G)={V1,V2,…,Vn}为有限非空集合,Vi称为结点,简称V是点集。(2)E(G)={e1,…,em}为有限的边集合,ei称边,每个ei都有V中的结点对与之相对应,称E为边集。即每条边是连结V中的某两个点的。§1图的基本概念(3)若G中每一条边e与有序偶对

5、无序偶对(vi,vj)相关联,则可说边e连接结点vi和vj(4)可用e=或e=(vi,vj),以结点来表示图的边,这样可把图简化成:G=<V,E>。例:有图如下,试写成定义表达式G=〈V,E〉,其中V={v1,v2,v3,v4,v5}E={x1,x2,x3,x4,x5,x6}§1图的基本概念例:对有向图可表示为:G=〈V、E〉,其中V={a、b、c、d}E={,,,,,}§1图的基本概念下面定义一些专门名词:(1)有向边:若边ej与结点序偶关联,那

6、么称该边为有向边。(2)无向边:若边ej与结点无序偶(vj,vk)关联,那么称该边为无向边。§1图的基本概念(3)邻接结点:由一条边(有向或无向)连接起来的结点偶对。(4)(n,e)图:具有n个结点(顶点),e条边的图。§1图的基本概念(5)有向图:在G中每一条边均为有向边。(6)无向图:每条边均为无向边的图。(7)混合图:有些边是无向边,有些边是有向边的图称为混合图。§1图的基本概念V1’v1v4v5v1v2v3v4V2’V3’V4’(a)无向图(b)有向图(c)混合图(孤立点)v2v3环§1图的基本概念(8)点和边的关联:如ei=

7、(u,v)或ei=称u,v与ei关联。(9)点与点的相邻:关联于同一条边的结点称为邻接点。(10)边与边的邻接:关联于同一结点的边称为邻接边。§1图的基本概念(11)孤立结点:不与任何结点相邻接的结点称为孤立结点。(12)零图:仅有孤立结点的图。(13)平凡图:仅有一个孤立结点的图。(14)自回路(环):关联于同一结点的边称为自回路,或称为环。§1图的基本概念(15)平行边:在有向图中,始点和终点均相同的边称为平行边,无向图中若两点间有多条边,称这些边为平行边,两点间平行边的条数称为边的重数。定义:在图G=,vV

8、,与结点v关联的边数称为该点的度数,记为deg(v)。孤立结点的度数为0。图G最大度记为(G)=max{deg(v)

9、vV(G)},最小度数记为(G)=min{deg(v)

10、vV(G)}§1图的基本概念定义:在有

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
正文描述:

《离散数学第7章ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第四篇图论图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究,如1736年欧拉(L.Euler)所解决的哥尼斯堡七桥问题。以及在民间广为流传的一些游戏问题:例如 迷宫问题、棋盘上马的行走路线问题等等。这些古老的问题当时吸引了许多学者的注意,从而在这些问题研究的基础上,又提出了著名的四色猜想和环游世界各国的问题。例:用定理解决哥尼斯堡桥的问题第四篇图论图论不断发展,它在解决运筹学,网络理论,信息论,控制论,博奕论以及计算机科学等各个领域的问题时,显示出越来越大的效果。对于这样一门应用广泛的学科,其包含的内

2、容是丰富的,本篇我们只准备介绍基本的概念和定理,为今后有关学科及课程的学习和研究提供方便。WWW电力网因特网复杂网络的事例——技术网络复杂网络的事例——社会网络朋友关系网演员网科学家合著网科学引文网复杂网络的事例——交通运输网络城市公共交通网道路交通网航空网复杂网络的事例——生物网络神经网络生态网络蛋白质相互作用网络基因网络新陈代谢网络SantaFe研究所的科学家合作网复杂网络的事例——科学家合作网经济物理学科学家合作网复杂网络的事例——科学家合作网复杂网络的事例——中药方剂网示意图点(药材),边(药材之间相互作用),局域世界(方剂)

3、§1图的基本概念定义:图(graph)G由一个三元组表示,其中:非空集合V(G)={v1,v2,…,vr}称为图G的结点集,其成员vi(i=1,2,…,r)称为结点或顶点(nodesorvertices);集合E(G)={e1,e2,…,es}称为图G的边集,其成员ej(j=1,2,…s)称为边(edges)。函数G:E(G)→(V(G),V(G)),称为边与顶点的关联映射(associatvemapping)§1图的基本概念例:G=其中V(G)={a,b,c,d},E(G)=

4、{e1,e2,e3,e4,e5,e6},G(e1)=(a,b),G(e2)=(a,c),G(e3)=(b,d),G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d)abcde1e2e3e4e5e6§1图的基本概念讨论定义:(1)V(G)={V1,V2,…,Vn}为有限非空集合,Vi称为结点,简称V是点集。(2)E(G)={e1,…,em}为有限的边集合,ei称边,每个ei都有V中的结点对与之相对应,称E为边集。即每条边是连结V中的某两个点的。§1图的基本概念(3)若G中每一条边e与有序偶对

5、无序偶对(vi,vj)相关联,则可说边e连接结点vi和vj(4)可用e=或e=(vi,vj),以结点来表示图的边,这样可把图简化成:G=<V,E>。例:有图如下,试写成定义表达式G=〈V,E〉,其中V={v1,v2,v3,v4,v5}E={x1,x2,x3,x4,x5,x6}§1图的基本概念例:对有向图可表示为:G=〈V、E〉,其中V={a、b、c、d}E={,,,,,}§1图的基本概念下面定义一些专门名词:(1)有向边:若边ej与结点序偶关联,那

6、么称该边为有向边。(2)无向边:若边ej与结点无序偶(vj,vk)关联,那么称该边为无向边。§1图的基本概念(3)邻接结点:由一条边(有向或无向)连接起来的结点偶对。(4)(n,e)图:具有n个结点(顶点),e条边的图。§1图的基本概念(5)有向图:在G中每一条边均为有向边。(6)无向图:每条边均为无向边的图。(7)混合图:有些边是无向边,有些边是有向边的图称为混合图。§1图的基本概念V1’v1v4v5v1v2v3v4V2’V3’V4’(a)无向图(b)有向图(c)混合图(孤立点)v2v3环§1图的基本概念(8)点和边的关联:如ei=

7、(u,v)或ei=称u,v与ei关联。(9)点与点的相邻:关联于同一条边的结点称为邻接点。(10)边与边的邻接:关联于同一结点的边称为邻接边。§1图的基本概念(11)孤立结点:不与任何结点相邻接的结点称为孤立结点。(12)零图:仅有孤立结点的图。(13)平凡图:仅有一个孤立结点的图。(14)自回路(环):关联于同一结点的边称为自回路,或称为环。§1图的基本概念(15)平行边:在有向图中,始点和终点均相同的边称为平行边,无向图中若两点间有多条边,称这些边为平行边,两点间平行边的条数称为边的重数。定义:在图G=,vV

8、,与结点v关联的边数称为该点的度数,记为deg(v)。孤立结点的度数为0。图G最大度记为(G)=max{deg(v)

9、vV(G)},最小度数记为(G)=min{deg(v)

10、vV(G)}§1图的基本概念定义:在有

显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
关闭