第1讲图论概述精选文档.ppt

第1讲图论概述本讲稿第一页，共二十三页教师联系方式教师联系方式冯结冯结 电话电话 :1898076527018980765270，8543600785436007（H H）电子邮箱电子邮箱：本讲稿第二页，共二十三页本课程学习要求本课程学习要求 1.1.必备三物：必备三物：教材，作业本教材，作业本教材，作业本教材，作业本,课堂笔记课堂笔记课堂笔记课堂笔记.2.2.成绩评定：成绩评定：平时成绩占平时成绩占20%20%期中测验占期中测验占20%20%期末考试占期末考试占60%60%本讲稿第三页，共二十三页引例：七桥问题引例：七桥问题一笔画问题：一笔画问题：要求笔不离纸，边不重复要求笔不离纸，边不重复哥尼斯堡七桥问题哥尼斯堡七桥问题本讲稿第四页，共二十三页一个图是由两个集合组成：一个图是由两个集合组成：顶点集顶点集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)。在不致引起混淆的情况下可简记为。在不致引起混淆的情况下可简记为G=(VG=(V，E)E)。什么是图？什么是图？本讲稿第五页，共二十三页常用常用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=(V,E)的图形表示为：的图形表示为：图1本讲稿第六页，共二十三页若一条边的端点为同一顶点，则称此边为若一条边的端点为同一顶点，则称此边为环环。（如图。（如图1 中的中的e5）若若E 中两条或两条以上不同边具有相同端点，则称这些边为中两条或两条以上不同边具有相同端点，则称这些边为 重复边重复边（e1 和和e4）无环无重边的图称为无环无重边的图称为简单图简单图，只有一个顶点的图称为平凡图，其余为非，只有一个顶点的图称为平凡图，其余为非平凡图。无边的图称为平凡图。无边的图称为空图空图。一条边的端点称为与此边一条边的端点称为与此边关联关联的顶点，反之亦然，与同一条边关联的顶点，反之亦然，与同一条边关联的而个顶点称为的而个顶点称为相邻相邻的，与同一顶点关联的两条边也称为相邻的的，与同一顶点关联的两条边也称为相邻的在图在图l 中，中，e1 与与v1，v2 关联，关联，v1 与与v4 相邻，相邻，e1 与与e2 相邻。相邻。本讲稿第七页，共二十三页 与顶点与顶点vi 关联的边的数目称为关联的边的数目称为vi 的的度（或次）度（或次），记为，记为d(vi)，度为，度为0 的顶点称为的顶点称为孤立点孤立点，度为，度为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为悬挂边为悬挂边本讲稿第八页，共二十三页图的本质？图的本质？图最为本质的内容是一个图最为本质的内容是一个二元关系二元关系.相关基本概念：相关基本概念：有序对，有序积有序对，有序积AB（笛卡尔积），（笛卡尔积），无序对，无序积无序对，无序积A&B，A到到B的二元关系，的二元关系，A和和B的二元关系的二元关系图，是某顶点集合图，是某顶点集合V和和V 上的一个二元关系。上的一个二元关系。只要一个系统若具有二元关系便可以考虑采用图来建立模型解只要一个系统若具有二元关系便可以考虑采用图来建立模型解决实际问题。决实际问题。本讲稿第九页，共二十三页几个有趣问题几个有趣问题1.1.一次集会上面许多朋友相互握手，那么握手次数一次集会上面许多朋友相互握手，那么握手次数为奇数的人的数目一定是偶数。为奇数的人的数目一定是偶数。2.2.有有2 2人以上的人群中，总有两人在该人群内恰人以上的人群中，总有两人在该人群内恰好有相同的朋友数。好有相同的朋友数。3.3.证明：任意证明：任意6 6个人中，至少有个人中，至少有3 3人相互认识或人相互认识或者至少有者至少有3 3人相互全都不认识。人相互全都不认识。本讲稿第十页，共二十三页定理定理 设设G=(V，E)是一个图，则是一个图，则度为奇数的点称为度为奇数的点称为奇点奇点，度为偶数的点称为，度为偶数的点称为偶点偶点。推论：推论：在任何图中，在任何图中，奇点的个数必为偶数奇点的个数必为偶数。证明：设证明：设V1 和和V2 分别是偶点集和奇点集，由定理分别是偶点集和奇点集，由定理 可得下式：可得下式：由于由于2是偶数，是偶数，也是偶数，所以也是偶数，所以 必然是偶数。必然是偶数。由于由于 中每一项都是奇数，所以它的项数必须是偶数，中每一项都是奇数，所以它的项数必须是偶数，即奇点数必为偶数。即奇点数必为偶数。本讲稿第十一页，共二十三页节目排序问题节目排序问题要求要求（1）每个演员不连续参加）每个演员不连续参加2个节目的演出；个节目的演出；（2）A和和H必须安排在首尾两个节目。必须安排在首尾两个节目。演员节目12345678910A B CDEFGH 本讲稿第十二页，共二十三页图的作用图的作用图是解决问题的一种工具，是一种重要的数图是解决问题的一种工具，是一种重要的数学模型。学模型。图往往能够使问题得到简化，便于处理。图往往能够使问题得到简化，便于处理。图具有直观性和艺术性。图具有直观性和艺术性。图论与数学（拓扑学，代数学，组合数学）图论与数学（拓扑学，代数学，组合数学）关系密切，如今，它的许多方法在物理学，关系密切，如今，它的许多方法在物理学，化学，通讯科学，计算机技术，运筹学，经化学，通讯科学，计算机技术，运筹学，经济学，生物遗传学，心理学，社会学，人类济学，生物遗传学，心理学，社会学，人类学，语言学等诸多学科的某些领域都有应用。学，语言学等诸多学科的某些领域都有应用。本讲稿第十三页，共二十三页图的分类图的分类有向图，无向图有向图，无向图 平凡图，非平凡图，空图平凡图，非平凡图，空图 连通图，不连通图连通图，不连通图 平面图，非平面图平面图，非平面图 赋权图，无权图赋权图，无权图本讲稿第十四页，共二十三页一些特殊类型的图一些特殊类型的图 完全图完全图：任意一对不同顶都有一条边相连的简单图。：任意一对不同顶都有一条边相连的简单图。n个顶点的完全图记为个顶点的完全图记为Kn二部图（偶图）二部图（偶图）：图：图G=(V，E)的顶点集的顶点集V如能分为两个非空子集如能分为两个非空子集X和和Y，使得，使得E中每条边都是一个端点在中每条边都是一个端点在X中另一个端点在中另一个端点在Y中，则称中，则称G为二部图。为二部图。若若G是简单二部图，且是简单二部图，且X中每一顶点与中每一顶点与Y中每一顶点相连，中每一顶点相连，|X|=m,|Y|=n（符号（符号|A|表示集合表示集合A中元素的个数），则称中元素的个数），则称G为为完全二部图（完全偶图）完全二部图（完全偶图），记为，记为Km,n。v2v3v4v5v2v3v4v5v1v1完全图完全图K5(完全完全)二部图二部图K2,3本讲稿第十五页，共二十三页 k-部图部图：图：图G=(V,E)的顶点集的顶点集V如能分为如能分为k个非空子集个非空子集V1,V2,Vk使得使得E中每一条边都有一个端点在某一中每一条边都有一个端点在某一Vi中，另一端中，另一端 点在某一点在某一Vj中，中，ij,则称则称G为为k-部图。部图。r-正则图正则图：称图：称图G是是r-正则的，如果对所有正则的，如果对所有vV都有都有d(v)=r。本讲稿第十六页，共二十三页图的若干重要定义图的若干重要定义 途径途径：G的一条途径是一个有限非空的的一条途径是一个有限非空的顶点和边的交错序列顶点和边的交错序列W=v0e1v1e2v2ekvk，使得对任何，使得对任何i,ei 的端点是的端点是vi-1和和vi，并称，并称W 是是从从v0 到到 vk的一条途径，或一条的一条途径，或一条(v0,vk)途径。途径。v0 和和vk 分别称为分别称为W 的起的起点和终点，通称为端点，其余的顶点为它的内点，整数点和终点，通称为端点，其余的顶点为它的内点，整数k 称为称为W 的长。的长。注意注意：在一条途径中，顶点和边可以重复出现在一条途径中，顶点和边可以重复出现。若。若W 的起点与终的起点与终点是相同的，则称点是相同的，则称W 为闭途径，否则为开途径。为闭途径，否则为开途径。在表示途径时亦可用边的序列在表示途径时亦可用边的序列e1e2ek 表示，特别在简单图表示，特别在简单图中，由于不存在重边与环，途径可由顶点序列中，由于不存在重边与环，途径可由顶点序列v1v2vk 表示而表示而不至引起混乱。不至引起混乱。本讲稿第十七页，共二十三页v1e1v2e2v3e6v6e5v2e1v1 是闭途径是闭途径 v1e1v2e2v3e6v6e8v5e7v4 是开途径是开途径链链：一条途径若其所有：一条途径若其所有边互不相同边互不相同 则称为链则称为链路路：一条链若其：一条链若其所有顶点互不相同所有顶点互不相同，则称为路，记为，则称为路，记为P。一条路所。一条路所含边的数目称为此路的长，。含边的数目称为此路的长，。圈圈：起点终点相同的链，称为圈，记为：起点终点相同的链，称为圈，记为C。一个圈所含边的数目称。一个圈所含边的数目称为此圈的长。为此圈的长。回路回路：起点终点相同的路，称为回路。：起点终点相同的路，称为回路。v1e1v2e2 v3 为一条路为一条路v1e1v2e9v5e7v4e3v1 为一个圈 连连通通图图：若若图图G 中中任任意意两两点点间间都都存存在在一一条条路路,则则称称G 为为连连通通的。的。本讲稿第十八页，共二十三页 子图与生成子图（部分图）子图与生成子图（部分图）子图子图：称图：称图H 是是G 的的子图子图（记为（记为HG），如果），如果V(H)V(G),E(H)E(G),且且E(H)中的边的端点都是中的边的端点都是V(H)中的顶中的顶点点。若若HG，但，但HG，则称，则称H 为为G 的的真子图真子图。生生成成子子图图：若若H是是G 的的子子图图，且且V(H)=V(G),则则称称H是是G的的生生成成 子图子图。在下图中，。在下图中，a是图是图G 的子图，的子图，b是图是图G 的生成子图。的生成子图。本讲稿第十九页，共二十三页基础简单图基础简单图：从图从图G G 中删去所有的环，并使每一对相邻顶中删去所有的环，并使每一对相邻顶点只留下一条边，这样得到的点只留下一条边，这样得到的G G 的简单生成子图称为的简单生成子图称为G G 的基的基础简单图。础简单图。本讲稿第二十页，共二十三页导导出出子子图图：设设 是是V 的的一一个个非非空空子子集集，以以 为为顶顶点点集集，以以两两个个端端点点均均在在 中中的的边边的的全全体体为为边边集集所所组组成成的的子子图图称称为为G 的的导导出出子子图图，记记为为G 。导导出出子子图图GVV 记记为为GV；它它是是从从G 中中删删去去 V中中的的顶顶点点以以及及与与这这些些项项点点相相关关联联的的边边所所得得到到的的子子图图。若若V=v，则则把把Gv简记为简记为Gv。设设E是是E 的非空子集。以的非空子集。以E为边集，以为边集，以E 中边的端点全体为顶点集中边的端点全体为顶点集所组成的子图称为由所组成的子图称为由E 导出的子图，记为导出的子图，记为G E。边集为。边集为E E 的的G 的生成子图简记为的生成子图简记为GE，它是从，它是从G 中删去中删去E 中的边所得到的子图；中的边所得到的子图；类似地在类似地在G 上添加边集上添加边集E（其中（其中EE=)所得图记为所得图记为G+E，若，若E=e，则用，则用G+e 和和G-e 来代替来代替G+e和和G-e。本讲稿第二十一页，共二十三页本讲稿第二十二页，共二十三页 谢谢 谢！谢！再再 见！见！本讲稿第二十三页，共二十三页