第1讲图论概述精选文档.ppt
《第1讲图论概述精选文档.ppt》由会员分享,可在线阅读,更多相关《第1讲图论概述精选文档.ppt(23页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第1讲图论概述本讲稿第一页,共二十三页教师联系方式教师联系方式冯结冯结 电话电话 :1898076527018980765270,8543600785436007(H H)电子邮箱电子邮箱:本讲稿第二页,共二十三页本课程学习要求本课程学习要求 1.1.必备三物:必备三物:教材,作业本教材,作业本教材,作业本教材,作业本,课堂笔记课堂笔记课堂笔记课堂笔记.2.2.成绩评定:成绩评定:平时成绩占平时成绩占20%20%期中测验占期中测验占20%20%期末考试占期末考试占60%60%本讲稿第三页,共二十三页引例:七桥问题引例:七桥问题一笔画问题:一笔画问题:要求笔不离纸,边不重复要求笔不离纸,边不重复
2、哥尼斯堡七桥问题哥尼斯堡七桥问题本讲稿第四页,共二十三页一个图是由两个集合组成:一个图是由两个集合组成:顶点集顶点集V V(非空有限集)(非空有限集)边集边集E E(有限集(有限集E E)每条边对应由两个顶点组成的顶点对。若顶点对是无序的,则称每条边对应由两个顶点组成的顶点对。若顶点对是无序的,则称为为无向图无向图;若顶点对是有序的,则称为;若顶点对是有序的,则称为有向图有向图。若图用若图用G G 表示,则它的点集和边集就分别记为表示,则它的点集和边集就分别记为V(G)V(G),E(G),E(G),该图可以该图可以记为记为G=(V(G)G=(V(G),E(G)E(G)。在不致引起混淆的情况下可
3、简记为。在不致引起混淆的情况下可简记为G=(VG=(V,E)E)。什么是图?什么是图?本讲稿第五页,共二十三页常用常用u,v,w,或或v1,v2,v3,来标记图的顶点,用来标记图的顶点,用a,b,c,或或e1,e2,e3,标记图的边。每条边用一条连接该边端点的线表示。画图形时,标记图的边。每条边用一条连接该边端点的线表示。画图形时,表示顶点的点的位置和表示边的线的相对位置是无关紧要的,因为表示顶点的点的位置和表示边的线的相对位置是无关紧要的,因为一个图的图形仅需画出它的顶点与边之间的关系,所以一个一个图的图形仅需画出它的顶点与边之间的关系,所以一个图的图图的图形表示不是唯一的形表示不是唯一的。
4、例例1:V=v1,v2,v3,v4,v5,v6 和和E=e1,e2,e3,e4,e5,其中其中e1=v1v2,e2=v1v4,e3=v5v6,e4=v1v2,e5=v5v5,则,则G=(V,E)的图形表示为:的图形表示为:图1本讲稿第六页,共二十三页若一条边的端点为同一顶点,则称此边为若一条边的端点为同一顶点,则称此边为环环。(如图。(如图1 中的中的e5)若若E 中两条或两条以上不同边具有相同端点,则称这些边为中两条或两条以上不同边具有相同端点,则称这些边为 重复边重复边(e1 和和e4)无环无重边的图称为无环无重边的图称为简单图简单图,只有一个顶点的图称为平凡图,其余为非,只有一个顶点的图
5、称为平凡图,其余为非平凡图。无边的图称为平凡图。无边的图称为空图空图。一条边的端点称为与此边一条边的端点称为与此边关联关联的顶点,反之亦然,与同一条边关联的顶点,反之亦然,与同一条边关联的而个顶点称为的而个顶点称为相邻相邻的,与同一顶点关联的两条边也称为相邻的的,与同一顶点关联的两条边也称为相邻的在图在图l 中,中,e1 与与v1,v2 关联,关联,v1 与与v4 相邻,相邻,e1 与与e2 相邻。相邻。本讲稿第七页,共二十三页 与顶点与顶点vi 关联的边的数目称为关联的边的数目称为vi 的的度(或次)度(或次),记为,记为d(vi),度为,度为0 的顶点称为的顶点称为孤立点孤立点,度为,度为
6、1的点称为的点称为悬挂点悬挂点,与悬挂点相联的边称为,与悬挂点相联的边称为悬挂边悬挂边。与。与vi 关联的环计算时作为关联的环计算时作为2 条边,图条边,图G 的顶点数和边数分别的顶点数和边数分别用用(G)和和(G)表示表示,当讨论的图只有一个时,常省去括号中表示图的当讨论的图只有一个时,常省去括号中表示图的符号,而只用符号,而只用V,E,等记法。等记法。在图在图1 中,中,=6,=5,d(v1)=3,d(v2)=2,d(v3)=0,d(v4)=1,d(v5)=3,d(v6)=1,v3 为为3 孤立点,孤立点,v4,v6为悬挂点,为悬挂点,e2,e4为悬挂边为悬挂边本讲稿第八页,共二十三页图的
7、本质?图的本质?图最为本质的内容是一个图最为本质的内容是一个二元关系二元关系.相关基本概念:相关基本概念:有序对,有序积有序对,有序积AB(笛卡尔积),(笛卡尔积),无序对,无序积无序对,无序积A&B,A到到B的二元关系,的二元关系,A和和B的二元关系的二元关系图,是某顶点集合图,是某顶点集合V和和V 上的一个二元关系。上的一个二元关系。只要一个系统若具有二元关系便可以考虑采用图来建立模型解只要一个系统若具有二元关系便可以考虑采用图来建立模型解决实际问题。决实际问题。本讲稿第九页,共二十三页几个有趣问题几个有趣问题1.1.一次集会上面许多朋友相互握手,那么握手次数一次集会上面许多朋友相互握手,
8、那么握手次数为奇数的人的数目一定是偶数。为奇数的人的数目一定是偶数。2.2.有有2 2人以上的人群中,总有两人在该人群内恰人以上的人群中,总有两人在该人群内恰好有相同的朋友数。好有相同的朋友数。3.3.证明:任意证明:任意6 6个人中,至少有个人中,至少有3 3人相互认识或人相互认识或者至少有者至少有3 3人相互全都不认识。人相互全都不认识。本讲稿第十页,共二十三页定理定理 设设G=(V,E)是一个图,则是一个图,则度为奇数的点称为度为奇数的点称为奇点奇点,度为偶数的点称为,度为偶数的点称为偶点偶点。推论:推论:在任何图中,在任何图中,奇点的个数必为偶数奇点的个数必为偶数。证明:设证明:设V1
9、 和和V2 分别是偶点集和奇点集,由定理分别是偶点集和奇点集,由定理 可得下式:可得下式:由于由于2是偶数,是偶数,也是偶数,所以也是偶数,所以 必然是偶数。必然是偶数。由于由于 中每一项都是奇数,所以它的项数必须是偶数,中每一项都是奇数,所以它的项数必须是偶数,即奇点数必为偶数。即奇点数必为偶数。本讲稿第十一页,共二十三页节目排序问题节目排序问题要求要求(1)每个演员不连续参加)每个演员不连续参加2个节目的演出;个节目的演出;(2)A和和H必须安排在首尾两个节目。必须安排在首尾两个节目。演员节目12345678910A B CDEFGH 本讲稿第十二页,共二十三页图的作用图的作用图是解决问题
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 讲图论 概述 精选 文档
限制150内