《图论的介绍》PPT课件.ppt
《《图论的介绍》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《图论的介绍》PPT课件.ppt(108页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、图论的介绍哥尼斯堡七桥问題(Bridges of Koenigsberg)能不能走过每一个桥能不能走过每一个桥刚好一次并且回到原來的地方?刚好一次并且回到原來的地方?欧拉路径解決哥尼斯保七桥问題原來是一笔画问题啊!数学家欧拉(Euler,1707-1783)于1736年严格的证明了上述哥尼斯堡七桥问题无解,并且由此开创了图论的典型思维方式及论证方式实际生活中的图论Graph Model电路模拟电路模拟例:例:Pspice、Cadence、ADS.PspiceCadence交通网络航空网络航空网络!捷運路線图!捷運路線图!网络架构图网络架构图计算机网络有向图有有单行道的街道!单行道的街道!行程表
2、!行程表!Social NetworkHigh School Datingcorporate e-mailReference:Bearman,Moody and Stovel,2004image by Mark NewmanReference:Adamic and Adar,2004Protein interaction networkReference:Jeong et al,Nature Review|GeneticsPower transmission grid of Western USThe InternetThe Internet as mapped by The Opte Pro
3、jecthttp:/More ApplicationsnHypertextsq网页包含到其他网页的超链接。整个网页包含到其他网页的超链接。整个Web是一个图是一个图.搜搜索引擎需要图处理算法。索引擎需要图处理算法。nMatchingq职位招聘,如何有效将职位与应聘者匹配?职位招聘,如何有效将职位与应聘者匹配?nSchedulesq工程项目的任务安排,如何满足限制条件,并在最短时工程项目的任务安排,如何满足限制条件,并在最短时间内完成?间内完成?nProgram structureq大型软件系统,函数(模块)之间调用关系。编译器分大型软件系统,函数(模块)之间调用关系。编译器分析调用关系图确定如
4、何最好分配资源才能使程序更有效析调用关系图确定如何最好分配资源才能使程序更有效率。率。Graph ApplicationsGraph Problems and Algorithms哈密頓(Hamilton)周遊世界问題哈密頓路径至今尚无有效方法來解決!正十二面体有二十个顶点表示世界上20个城市各经每个城市一次最后返回原地投影至平面最短路径问題最短路径问題(Shortest Path Problem)最快航線最快航線 最快的最快的routing最短路径算法最短路径算法Dijkstra算算法法n可以求出從某一点到图上其他任一点的最短路径可以求出從某一点到图上其他任一点的最短路径走迷宫与深度优先搜索
5、走迷宫与深度优先搜索(Depth-First Search)老鼠走迷宮老鼠走迷宮深度优先搜索深度优先搜索一直往前走一直往前走碰壁就回碰壁就回头換条路找头換条路找沿途要记录下走过的路线沿途要记录下走过的路线Some graph-processing problemsnPath.Is there a path between s to t?nShortest path.What is the shortest path between s and t?nLongest path.What is the longest simple path between s and t?nCycle.Is th
6、ere a cycle in the graph?nEuler tour.Is there a cycle that uses each edge exactly once?nHamilton tour.Is there a cycle that uses each vertex exactly once?nConnectivity.Is there a way to connect all of the vertices?nMST.What is the best way to connect all of the vertices?nBiconnectivity.Is there a ve
7、rtex whose removal disconnects the graph?nPlanarity.Can you draw the graph in the plane with no crossing edges?First challenge:Which of these problems is easy?difficult?intractable?图论图论的术语的术语什么是图?什么是图?一堆顶点和边的组合!一堆顶点和边的组合!Set of vertices connected pairwise by edges.例一例一 例二例二 图论的术语顶点(Vertex)边(Edge)一个图
8、G=(V,E)V:顶点的集合E:边的集合例:如右图V=a,b,c,d,eE=(a,b),(a,c),(a,d),(b,e),(c,d),(c,e),(d,e)再來一些术语连通图(connected graph)子图(subgraph)树(tree)沒有回路的连通图森林(forest)一堆树的集合树的实例 行政组织图有向图(Digraph)有向图(Digraph)有向且无简单回路的图(directed acyclic graph)加权图(Weighted Graph)生成树(Spanning Tree)生成树包括图中所有的顶点,并且是一棵树可运用生成树的实例Graph Terminology一些
9、特殊的图完全图 Complete graphsn任意两点之间都有一条边与其相连的图称为完全图,以Kn 來表示,n为顶点数二分图(偶图)Bipartite graphsnA graph that can be decomposed into two partite sets but not fewer is bipartitenIt is a complete bipartite if its vertices can be divided into two non-empty groups,A and B.Each vertex in A is connected to B,and vice-
10、versa Complete bipartite graph K2,3The graph is bipartite平面图 Planar graphsnA planar graph is a graph that can be embedded in a plane so that no edges intersectPlanar:=NOT Planar:平面图实例n8个顶点(V=8)n12条边(E=12)n6个面 (F=6)n8-12+6=2更多平面图实例 树 Trees n树(tree):连通无简单回路无向图q若有n个顶点,則有n-1条边q任两点之间仅有一条路径n生成树(spanning t
11、ree):包括图中所有的顶点,并且是一棵树A connected graph GSpanning trees of Gtree图术语回顾点:点:研究对象(陆地、路口、国家、球队);点间连线:点间连线:对象之间的特定关系(陆地间有桥、路口 之间道路、两国边界、两球队比赛及结果)。对称关系:对称关系:桥、道路、边界;用不带箭头的连线表示,称为边。用不带箭头的连线表示,称为边。非对称关系:非对称关系:甲队胜乙队,用带箭头的连线表示,称为弧。图:图:点及边(或弧)组成。例:例:有甲、乙、丙、丁、戊五个球队,各队之间比赛有甲、乙、丙、丁、戊五个球队,各队之间比赛 情况如表:情况如表:点:球队;点:球队;
12、连线:两个球队之间比赛过,如甲胜乙,用连线:两个球队之间比赛过,如甲胜乙,用 v1 v2表示。表示。v1v2v3v4v5 图的定义图的定义定义定义1:一个图,是由非空集合:一个图,是由非空集合V(G)=vi 和和V(G)中中 元素的有序对(或无序对)的集合元素的有序对(或无序对)的集合E(G)=ek 所组成的二元组(所组成的二元组(V(G),E(G))所构成。)所构成。记为记为 G=(V(G),E(G))简记简记 G=(V,E)其中其中 V=vi 称为点集,称为点集,vi为点为点。E=ek称为边集,称为边集,ek为边(或弧)。为边(或弧)。当当V,E为有限集时,称为有限集时,称G为有限图。为有
13、限图。否则,称否则,称G为无限图。为无限图。无向图:由点及边构成无向图:由点及边构成,边,边vi,vj有向图:由点及弧构成,弧(有向图:由点及弧构成,弧(vi,vj)图图G中点集中点集V的顶点个数,记为的顶点个数,记为p(G);边数记为边数记为q(G),简记简记 p,q。1.简单图与多重图简单图与多重图某条边两个端点相同,称这条边为环。某条边两个端点相同,称这条边为环。若两点之间有多于一条的边,称这些边为多重边。若两点之间有多于一条的边,称这些边为多重边。无环、无多重边的无环、无多重边的图称为简单图。图称为简单图。多重图:无环、但多重图:无环、但允许有多重边。允许有多重边。v1e1e2e3v2
14、v3e5e4v4二、图论中常用术语二、图论中常用术语2.相邻与关联相邻与关联 若边若边e=u,vE,称,称u,v是是e的端点,也称的端点,也称u,v是是相邻的。称相邻的。称e是点是点u(及点(及点v)的关联边。)的关联边。若两条边有一个公共的端点,则称这两条边相邻接。若两条边有一个公共的端点,则称这两条边相邻接。vivjevi,vj相邻相邻 e 与与vi,vj关联关联vie1vjvke2 点与边关联点与边关联点与点点与点相邻相邻边与边相邻接边与边相邻接定理定理1 图图G=(V,E)中,所有点的次之和为边数)中,所有点的次之和为边数的两倍,的两倍,即即 3.奇点与偶点奇点与偶点次为奇数的点称为奇
15、点,否则称为偶点。次为奇数的点称为奇点,否则称为偶点。定理定理2 任一图中奇点的个数为偶数。任一图中奇点的个数为偶数。证明:证明:设设v0和和v e分别是分别是G中的奇点和偶点的集合,中的奇点和偶点的集合,由定理由定理1,有,有因因 是偶数,是偶数,也是偶数,故也是偶数,故必为偶数。即在一个图中奇点的个数必为偶数。必为偶数。即在一个图中奇点的个数必为偶数。4.节点度与悬挂点、孤立点节点度与悬挂点、孤立点图图G中以点中以点v为端点的边的数目,称为为端点的边的数目,称为v在在G中的度,中的度,记为记为d(v)。)。d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1度为度为1 的点为的点
16、为悬挂点悬挂点,悬挂点的关联边称为,悬挂点的关联边称为悬挂边悬挂边,度为零的点称为度为零的点称为孤立点孤立点。v1e1e2e3v2v3e5e4v45.链与圈链与圈 给定一个图给定一个图G=(V,E),),G中的一个中的一个点、边交错点、边交错序列序列(vi1,ei1,vi2,ei2,vik-1,eik-1,vik),如果满),如果满足足eit=vit,vit+1(t=1,2,k-1),则称为一条联接),则称为一条联接vi1和和vik的的链链,记为,记为=(vi1,vi2,vik)。)。链(链(vi1,vi2,vik)中,若)中,若vi1=vik,称之为一,称之为一个个圈圈,记为,记为C=(vi
17、1,vi2,vik-1,vi1)。初等链:链中点都不同。初等链:链中点都不同。简单链:链中边都不同。简单链:链中边都不同。(边能否相同?)边能否相同?)(点能否相同?)点能否相同?)v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9简单链简单链:1=(v2,v1,v3,v6,v4,v3,v5)初等链初等链:2=(v2,v1,v3,v5)简单圈简单圈:C1=(v1,v2,v4,v3,v5,v6,v3,v1)初等圈:初等圈:C2=(v1,v2,v4,v6,v5,v3,v1)有向图中,不考虑弧的方向,有类似链(圈)的定义。有向图中,不考虑弧的方向,有类似链(圈)的定义。当链(圈)上
18、弧的方向一致时,称为路(回路)。当链(圈)上弧的方向一致时,称为路(回路)。3.连通图连通图 给定图G=(V,E),任何两点间至少有一条链,则称G是连通图,否则为不连通图。若G是不连通的,它的每个连通部分称为G的连通分图。一些特殊图类一些特殊图类 1.平凡图平凡图 节点数n=1,边数m=0的图。2.零图零图 边数m=0的图。5.完备图完备图 无向图的完备图:任何两点之间有一条边;有向图的完备图:任何两点u与v之间有两条有向边(u,v)及(v,u)。基本图:把有向图的每条边除去方向得到的无向图。若V(G)=X Y,X Y=,X、Y中的任两顶点不相邻,则G称为二分图,记为(S,X,Y)。4.4.树
19、树 无圈连通图。6.6.二分图二分图9.网络网络 若对图G=(V,E)中每条边vi,vj赋予一个数wij,则称wij为边vi,vj的权,并称图G为网络(或赋权图)。网络:无向网络、有向网络。7.完全二分图完全二分图 若V(G)=(S,X,Y),如果任意X、Y,都有,E,则称G是完全的二分图。8.正则图正则图 如果G中每个点的次数都相同,则G叫做正则图。1.子图与支撑子图子图与支撑子图定义定义2 给定图给定图G=(V,E),若图),若图G1=(V1,E1),其),其 中中V1 V,E1=uv|uvE,u,v v1,则称,则称G1是是G的子图。的子图。定义定义3 给定图给定图G=(V,E),若图)
20、,若图G1=(V,E1),其),其 中中E1 E,则称,则称G1是是G的一个支撑子图。的一个支撑子图。点全部保留点全部保留(a)(b)子图子图(c)支撑子图支撑子图四四 、图的运算、图的运算 2.2.图的收缩运算图的收缩运算 设图设图G=(V,E),V1 V,在在G中收缩中收缩V1是指在图是指在图G中,中,在在V1中的点重为一个点,中的点重为一个点,G与与V1中的点相关联的边变中的点相关联的边变为与这个新点相关联的边,称这样的图为关于为与这个新点相关联的边,称这样的图为关于V1收缩收缩。3.割集割集 给定图给定图G=(V,E),点的子集),点的子集S V,T V,定,定义义G中中边的集合边的集
21、合S,TG=uv|u s,v T为一个割集。为一个割集。若若X=v1若若X V是是V的真子集,的真子集,常记为常记为v6v2v3v4v5v1v1v2v3v4v5v6若若X=v1,v2,4.图的同构图的同构定义定义4 设图设图G=(V,E)与)与G1=(V1,E1),若它们),若它们的点之间存在一一对应,并且保持同样的相邻关系,的点之间存在一一对应,并且保持同样的相邻关系,则称则称G与与G1同构。记为同构。记为G G1。v1v2v3v4abcdv1v2v3v4abcd?(a)(b)图图(a)和和(b)就为同构就为同构五、图的矩阵表示五、图的矩阵表示 图的矩阵表示方法有:邻接矩阵、关联矩阵、可图的
22、矩阵表示方法有:邻接矩阵、关联矩阵、可达矩阵、权矩阵等。达矩阵、权矩阵等。1.1.邻接矩阵邻接矩阵 邻接矩阵用于描述两个顶点之间是否有边(弧)相连。邻接矩阵用于描述两个顶点之间是否有边(弧)相连。对于有n个顶点的无向图G=(V,E),定义邻接矩阵(B=bij)nn。其中,对于有几个顶点的有向图G=(V,A),定义邻接矩阵(B=bij)nn。其中,例题例题1 已知无向图所示,求其邻接矩阵。已知无向图所示,求其邻接矩阵。v5v3v1v2v4v6则 显然,无向图的邻接矩阵是关于对角线的对称矩阵。例例 2 已知:图所示,求其邻接矩阵。已知:图所示,求其邻接矩阵。v2v5v3v1v4v6则:v1 v2
23、v3 v4 v5 v6 v1 0 1 1 0 0 0 v2 0 0 1 1 1 0 v3 0 0 0 1 0 0 v4 0 0 0 0 1 1 v5 0 0 1 0 0 1 v6 0 0 0 0 0 0其邻接矩阵为:其邻接矩阵为:v4v5v2v1v3当当G为为无向图无向图时,时,邻接矩阵邻接矩阵为为对称对称矩阵。矩阵。在有向图中可达矩阵用于描述两点之间是否有路相连,即R=(rij)nn ,其中,2.2.可达矩阵可达矩阵 例题例题3 求例题求例题2的可达矩阵的可达矩阵则 v1 v2 v3 v4 v5 v6 v1 1 1 1 1 1 1 v2 0 1 1 1 1 1 v3 0 0 1 1 1 1
24、v4 0 0 0 1 1 1 v5 0 0 0 0 1 1 v6 0 0 0 0 0 13.关联矩阵关联矩阵有向图的关联矩阵也称顶点边关联矩阵。设有向图 G=(V,A),其中rij=V=v1,v2,v3vn,则关联矩阵可定义为 M=(mij)nm其中:例题例题4 4 求下图的关联矩阵求下图的关联矩阵v4v2v1v3a4a3a1a2a6a5则其关联矩阵为:a1 a2 a3 a4 a5 a6 v1 0 1 -1 0 0-1 v2 1 0 1 1 0 0 v3 -1-1 0 0 1 0 v4 0 0 0 -1 -1 1 权矩阵是最流行的一种网络矩阵表示法。对于有n个顶点的无向网络G=(V,E,W),
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图论的介绍 介绍 PPT 课件
限制150内