《第1讲图论概述优秀课件.ppt》由会员分享，可在线阅读，更多相关《第1讲图论概述优秀课件.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1讲图论概述第1 页，本讲稿共23 页教师联系方式 冯结 电话:18980765270，85436007（H）电子邮箱：第2 页，本讲稿共23 页本课程学习要求 1.必备三物：教材，作业本 教材，作业本,课堂笔记课堂笔记.2.成绩评定：平时成绩占20%期中测验占20%期末考试占60%第3 页，本讲稿共23 页引例：七桥问题 一笔画问题：要求笔不离纸，边不重复 哥尼斯堡七桥问题第4 页，本讲稿共23 页一个图是由两个集合组成：顶点集V（非空有限集）边集E（有限集E）每条边对应由两个顶点组成的顶点对。若顶点对是无序的，则称为无向图；若顶点对是有序的，则称为有向图。若图用G 表示，则它的点集和边集
2、就分别记为V(G)，E(G),该图可以记为G=(V(G)，E(G)。在不致引起混淆的情况下可简记为G=(V，E)。什么是图？第5 页，本讲稿共23 页常用u,v,w,或v1,v2,v3,来标记图的顶点，用a,b,c,或e1,e2,e3,标记图的边。每条边用一条连接该边端点的线表示。画图形时，表示顶点的点的位置和表示边的线的相对位置是无关紧要的，因为一个图的图形仅需画出它的顶点与边之间的关系，所以一个图的图形表示不是唯一的。例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=(
3、V,E)的图形表示为：图1第6 页，本讲稿共23 页若一条边的端点为同一顶点，则称此边为环。（如图1 中的e5）若E 中两条或两条以上不同边具有相同端点，则称这些边为 重复边（e1 和e4）无环无重边的图称为简单图，只有一个顶点的图称为平凡图，其余为非平凡图。无边的图称为空图。一条边的端点称为与此边关联的顶点，反之亦然，与同一条边关联的而个顶点称为相邻的，与同一顶点关联的两条边也称为相邻的在图l 中，e1 与v1，v2 关联，v1 与v4 相邻，e1 与e2 相邻。第7 页，本讲稿共23 页 与顶点vi 关联的边的数目称为vi 的度（或次），记为d(vi)，度为0 的顶点称为孤立点，度为1的点
4、称为悬挂点，与悬挂点相联的边称为悬挂边。与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为悬挂边第8 页，本讲稿共23 页图的本质？图最为本质的内容是一个二元关系.相关基本概念：有序对，有序积AB（笛卡尔积），无序对，无序积A&B，A到B的二元关系，A和B的二元关系 图，是某顶点集合V和V 上的一个二元关系。只要一个系统若具
5、有二元关系便可以考虑采用图来建立模型解决实际问题。第9 页，本讲稿共23 页几个有趣问题 1.一次集会上面许多朋友相互握手，那么握手次数为奇数的人的数目一定是偶数。2.有2人以上的人群中，总有两人在该人群内恰好有相同的朋友数。3.证明：任意6个人中，至少有3人相互认识或者至少有3人相互全都不认识。第10 页，本讲稿共23 页定理 设G=(V，E)是一个图，则度为奇数的点称为奇点，度为偶数的点称为偶点。推论：在任何图中，奇点的个数必为偶数。证明：设V1 和V2 分别是偶点集和奇点集，由定理 可得下式：由于2是偶数，也是偶数，所以 必然是偶数。由于 中每一项都是奇数，所以它的项数必须是偶数，即奇点
6、数必为偶数。第11 页，本讲稿共23 页节目排序问题 要求（1）每个演员不连续参加2个节目的演出；（2）A和H必须安排在首尾两个节目。演员节目1 2 3 4 5 6 7 8 9 10A B C D E F G H 第12 页，本讲稿共23 页图的作用 图是解决问题的一种工具，是一种重要的数学模型。图往往能够使问题得到简化，便于处理。图具有直观性和艺术性。图论与数学（拓扑学，代数学，组合数学）关系密切，如今，它的许多方法在物理学，化学，通讯科学，计算机技术，运筹学，经济学，生物遗传学，心理学，社会学，人类学，语言学等诸多学科的某些领域都有应用。第13 页，本讲稿共23 页图的分类 有向图，无向图
7、 平凡图，非平凡图，空图 连通图，不连通图 平面图，非平面图 赋权图，无权图第14 页，本讲稿共23 页一些特殊类型的图 完全图：任意一对不同顶都有一条边相连的简单图。n个顶点的完全图记为Kn二部图（偶图）：图G=(V，E)的顶点集V如能分为两个非空子集X和Y，使得E中每条边都是一个端点在X中另一个端点在Y中，则称G为二部图。若G是简单二部图，且X中每一顶点与Y中每一顶点相连，|X|=m,|Y|=n（符号|A|表示集合A中元素的个数），则称G为完全二部图（完全偶图），记为Km,n。v2v3v4v5v2v3v4v5 v1v1完全图K5(完全)二部图K2,3第15 页，本讲稿共23 页 k-部图：
8、图G=(V,E)的顶点集V如能分为k个非空子集V1,V2,Vk使得E中每一条边都有一个端点在某一Vi中，另一端 点在某一Vj中，ij,则称G为k-部图。r-正则图：称图G是r-正则的，如果对所有vV都有d(v)=r。第16 页，本讲稿共23 页图的若干重要定义 途径：G的一条途径是一个有限非空的顶点和边的交错序列W=v0e1v1e2v2ekvk，使得对任何i,ei 的端点是vi-1和vi，并称W 是从v0 到 vk的一条途径，或一条(v0,vk)途径。v0 和vk 分别称为W 的起点和终点，通称为端点，其余的顶点为它的内点，整数k 称为W 的长。注意：在一条途径中，顶点和边可以重复出现。若W
9、的起点与终点是相同的，则称W 为闭途径，否则为开途径。在表示途径时亦可用边的序列e1e2ek 表示，特别在简单图中，由于不存在重边与环，途径可由顶点序列v1v2vk 表示而不至引起混乱。第17 页，本讲稿共23 页v1e1v2e2v3e6v6e5v2e1v1 是闭途径 v1e1v2e2v3e6v6e8v5e7v4 是开途径链：一条途径若其所有边互不相同 则称为链路：一条链若其所有顶点互不相同，则称为路，记为P。一条路所含边的数目称为此路的长，。圈：起点终点相同的链，称为圈，记为C。一个圈所含边的数目称为此圈的长。回路：起点终点相同的路，称为回路。v1e1v2e2 v3 为一条路v1e1v2e9v5e7v4e3v1 为一个圈 连通图：若图G 中任意两点间都存在一条路,则称G 为连通的。第18 页，本讲稿共23 页