运筹学图的基本概念名校讲义课件.ppt

1、 图论是数学中广泛应用的一个分支。早期图论与“数学游戏”有着密切关系，所谓“哥尼斯堡七桥”问题就是其中之一。原东普鲁士的哥尼斯堡城有一条普莱格尔河，河中有两个小岛，有7座桥把该河的两个小岛与河岸联结起来，如图5-1所示。图 5-1A B C D 有人提出这样问题：从河岸或岛上任一地方开始步行，能否通过每一座桥恰恰一次后又返回原地？瑞士数学家列昂纳德欧拉（17071783）将这个问题简化为一个如图5-2所示的直观数学模型，即用4个点表示两岸和两个小岛，用两点间联线表示桥。于是问题转化为：在该图中，从任一点出发，能否通过每个线段一次且仅仅一次又回到原出发点。欧拉当时就证明出这是不可能实现的，并为此

2、写了被公认为世界第一篇有关图论方面的论文，并于1736年由圣彼德堡科学院发表。A C B D 图 5-2 图论中的“四色猜想”是近代数学中没有解决的最著名问题之一。即在一个平面或球面上的任何地图只需用4种颜色来着色，便可使任何相邻的两个国家（具有公共的边界线，不是仅一点相接）具有不同的颜色。该问题只需几分钟即可对不懂数学的人讲清楚，然而数学家们化了一个多世纪时间也始终未彻底解决这个问题。虽然1976年美国的阿普尔、黑尔和考齐等三人依靠电子计算机用了1200个小时证明该猜想是正确的，然而并不理想，数学家们仍希望不依靠计算机给出证明。本书只准备介绍图的基本概念以及图论在诸如路径问题、网络流问题和匹

3、配问题等领域中的应用。定义：一个图是由一个表示具体事物的点（顶点）的集合和表示事物之间的联系（边）的集合所组成。分类：通常把图分成两类，图边不带方向的无向图及图边具有方向的方向图。1无向图定义及表示设V=v1，v2，vn是由一个由n个顶点组成的非空集合。E=e1，e2，em是一个由m条边组成的集合，且知E中元素e是V中的一个无序元素对u，v。则称V和E这两个集合共同构成了一个无向图G，记作G(V，E)。若eu，vv，u，则称u与v为无向边e之端点；边e与顶点u、v相关联；顶点u与v相邻。例5-1 已知图G（V，E）有5个顶点和8条边，其点边关系示于表5-1中 表5-1e e1 e2 e3 e4

4、 e5 e6 e7 e8 eu,v v1,v2 v2,v3 v3,v3 v3,v4 v2,v4 v4,v5 v2,v5 v2,v5 其几何图形示于图5-4中。有关术语（在图G(V，E)中）(i)平行边（或多重边，重复边）：具有相同端点的边。(ii)环：两个端点落在一个顶点的边。(iii)简单图：无平行边和环的图。(iv)完备图：点点有通路，又无平行边，这类图又可称完全图或完美图。e3 v1 v2 v4 v3 v5 e1 e2 e4 e5 e6 e7 e8 图5-4 2有向图定义及表示E中元素e是V中一个有序元素对(u，v)，则称V和E这两个集合构成了一个有向图G，记作G(V，E)。通常e=(u

5、，v)表明u和v分别为边e的起点和终点。有关术语 (i)平行边（多重边）：起终点全相同的边。(ii)环：起终点落为一个顶点的边。(iii)简单图：既无环又无平行边的有向图。(iv)完备图：图中任意两点u，v间有且仅有2条有向边(u，v)及(v，u)的有向图。(v)基本图：将图G中的有向边全变为无向边后所得的图G称为G的基本图。3同构如果图G=(V，E)和G=(V，E)的各自顶点集合V与V之间以及各自边集合E与E之间在保持关联性质条件下一一对应，则称图G与G同构，即同构图的点边关系一样，而形状和点边符号可以不同。例如，图5-6和图5-7就是同构关系。x v v3 w h e2 ae c d f

6、图5-7y v2 v4 v3 v5 e1 e2 e4 e5 e6 e7 e8 图5-6v1 e3 用矩阵表示无环图中点与边的联接关系可使人们一目了然。可用4种矩阵表示一个图，是关联矩阵、邻接矩阵、回路矩阵、割集矩阵。我们只介绍最常用的前两种矩阵。1无向图的矩阵表示关联矩阵A(G)，该矩阵是表示顶点与边的联接关系。令图G=(V，E)，V=v1，v2，vn，E=e1，e2，em，则矩阵A(G)元素aij（A阵为nm）定义为：为：的关联矩阵例如，图关联与，表示不关联与，表示)(8510GAeeajijiij11000100111100001000000001011001011 54321765432

7、1eeeeeeee6 v1 v2 v4 v3 v5 e1 e2 e4 e5 e7 图5-8e3 e6 邻接矩阵B(G)，该阵表示顶点之间的邻接关系。令图G=(V，E)，V=v1，v2，vn，E=e1，e2，em，则矩阵B(G)元素bij（B阵为nn）定义为：之间的联接边数与表示无联接边与表示jijiijNb 0显然，图5-8的邻接矩阵B(G)可表达为：01002 100201111000100110105432154321 2有向图的矩阵表示（与无向图定义相似）关联矩阵A(G)元素aij定义为：邻接矩阵B(G)元素bij定义为以为vi起点和以vj为终点的边数。针对有向图5-9，可分别写出相应的

8、关联矩阵A(G)和邻接矩阵B(G)为：的终点为表示的起点为表示不关联与表示jijijiijeeea 1 1 0011000011011000011111100001147654323211(G)Aeeeeeee 0000102110010 0 1 0)(43214321GB显然，A(G)中列元素和必为0。B(G)中，i行元素和为以vi为起点的有向边数，j列元素和为以vj为终点的有向边数。v2 v1 e1 v4 v3 e2 e4 e5图5-9e3 e6e7 1子图的有关定义：设G1=(V1，E1)，G=(V，E)，若V1V，E1E，则称G1为G的子图，记为G1G。若G1G，且G1G时，称G1为G

9、的真子图，记为G1G。若G1G，且V1=V时，称G1为G的生成子图（即两图的顶点一样）。2子图运算（略）在无向图G=(V，E)中，与顶点v相联的边数，称为v的度(v)。1若(v)为偶数，称为偶度顶点。若(v)为奇数，称为奇度顶点。2定理一：图的顶点度之和为2 m（m为图中总边数）3任一图中，奇度顶点个数必为偶数。4如果图G=(V，E)中，所有顶点的度均相等，则称G为正则的，顶点度均为的正则图称为度正则的。0度正则图根本无边，1度正则图只有一条边。kkksssijiijiijieeeQ11110)1(ksesj1sisikiiiQ10kii01无向图的有关术语设 是无向图G=(V，E)中的由顶点

10、和边交错而成的非空有限有序列，且序列中边 的2个端点恰为序列中顶点 与 ，则定义：链：满足上述条件的Q，即为G中的链。在简单图中，链可用顶点序列表示(因为无平行边)，例如可写为 。闭链和开链：在Q链中，在k0时，若 ，则称Q为闭链，否则为开链。初等链：开链Q中，顶点都不相同。回路C：除起始点与终点重合外，其余顶点都不同的闭链称为回路，记为C。点连通：G中两点u，v之间存在链，称u，v是连通的。连通图：G中任两点间都连通，则称G为连通图；否则称为分离图。G内顶点连通关系满足等价关系。据此，可把G中顶点集合V分成几个互不相交的子集V1，V2，V，使得只有两个顶点同属一个子集时，才能连通。分支：上述

11、子集V1，V2，V所对应的子图G1，G2，G称为分支。图G的分支个数记为(G)。割边：若eE(G)，且(Ee)(G)，则称e为G的割边。kkksssijiijiijieeeQ11110sje1sisi0iki0iki2有向图的有关术语链（初等链）：若Q是有向图G的基本图中的一条链（初等链），则Q亦是G的链（初等链）。路：若G的链中的每条边 恰以为 起点，以 为终点，则称Q为从 至 的单向路，简称路。路径：G的路Q中每个顶点都不相同，称Q为从 至的单向路径，简称路径。回路:起终点重合的单向路径称为单向回路，简称回路。可达性：从u至v若存在路径，称u可达v。连通图：G中任意两点间存在链的有向图。强连通图：G中任意两点间相互可达的有向图。1树的定义及术语树：无回路的连通无向图称为树。枝：树中的边称为枝。生成树：若树T是无向图G的生成图，则称T是G的生成树。根：有向图G中可以到达图中任一顶点的顶点u称为G的根。根树：若有向图G有根u，且它的基本图是一棵树，则称G 为以u为根的根树或有向树。2树的性质树必连通，但无回路。树必有n1条边（设有n个顶点）。树无回路，但不相邻顶点联以一边，恰得一回路。树连通，但去掉任一边，必变为不连通。树中任两点间，恰有一条初等链。