运筹学图的基本概念名校义.pptVIP

第二十五讲 图的基本概念 §1 引言 §2 图的定义、分类及有关术语 §3 图的矩阵表示 §4 子图及其运算 §5 顶点的度?(v) §6 图的链、路及连通性 §7 树及其性质 §1 引言 （1） 图论是数学中广泛应用的一个分支。 早期图论与“数学游戏”有着密切关系，所谓“哥尼斯堡七桥”问题就是其中之一。原东普鲁士的哥尼斯堡城有一条普莱格尔河，河中有两个小岛，有7座桥把该河的两个小岛与河岸联结起来，如图5-1所示。 图 5-1 A B C D §1 引言 （2） 有人提出这样问题：从河岸或岛上任一地方开始步行，能否通过每一座桥恰恰一次后又返回原地？ 瑞士数学家列昂纳德?欧拉（1707~1783）将这个问题简化为一个如图5-2所示的直观数学模型，即用4个点表示两岸和两个小岛，用两点间联线表示桥。于是问题转化为：在该图中，从任一点出发，能否通过每个线段一次且仅仅一次又回到原出发点。欧拉当时就证明出这是不可能实现的，并为此写了被公认为世界第一篇有关图论方面的论文，并于1736年由圣?彼德堡科学院发表。 ? ? ? ? A C B D 图 5-2 §1 引言 （3） 图论中的“四色猜想”是近代数学中没有解决的最著名问题之一。即在一个平面或球面上的任何地图只需用4种颜色来着色，便可使任何相邻的两个国家（具有公共的边界线，不是仅一点相接）具有不同的颜色。该问题只需几分钟即可对不懂数学的人讲清楚，然而数学家们化了一个多世纪时间也始终未彻底解决这个问题。虽然1976年美国的阿普尔、黑尔和考齐等三人依靠电子计算机用了1200个小时证明该猜想是正确的，然而并不理想，数学家们仍希望不依靠计算机给出证明。 本书只准备介绍图的基本概念以及图论在诸如路径问题、网络流问题和匹配问题等领域中的应用。 §2 图的定义、分类及有关术语（1） 定义：一个图是由一个表示具体事物的点（顶点）的集合和表示事物之间的联系（边）的集合所组成。 分类：通常把图分成两类，图边不带方向的无向图及图边具有方向的方向图。 1．无向图 ①定义及表示 设V={v1，v2，?，vn}是由一个由n个顶点组成的非空集合。 E={e1，e2，?，em}是一个由m条边组成的集合，且知E中元素e是V中的一个无序元素对[u，v]。则称V和E这两个集合共同构成了一个无向图G，记作G＝(V，E)。 §2 图的定义、分类及有关术语（2） 若e＝[u，v]＝[v，u]，则称u与v为无向边e之端点；边e与顶点u、v相关联；顶点u与v相邻。 [例5-1] 已知图G＝（V，E）有5个顶点和8条边，其点边关系示于表5-1中 表5-1 e e1 e2 e3 e4 e5 e6 e7 e8 e＝[u,v] [v1,v2] [v2,v3] [v3,v3] [v3,v4] [v2,v4] [v4,v5] [v2,v5] [v2,v5] §2 图的定义、分类及有关术语（3） 其几何图形示于图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 图的定义、分类及有关术语（4） 2．有向图 ①定义及表示 E中元素e是V中一个有序元素对(u，v)，则称V和E这两个集合构成了一个有向图G，记作G＝(V，E) 。通常e=(u，v)表明u和v分别为边e的起点和终点。 ??②有关术语 (i)平行边（多重边）：起终点全相同的边。 (ii)环：起终点落为一个顶点的边。 (iii)简单图：既无环又无平行边的有向图。 §2 图的定义、分类及有关术语（5） (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就是同构关系。 §2 图的定义、分类及有关术语（6） x v v3 w ? ? ? ? ? h e2 a e c d f 图5-7 y v2 v4 v3 v5 ? ? ?