运筹学第06章图论概述.ppt

运筹学 第六章 图论概述 本章重点 图的基本概念 常见的四个问题的求解方法 图的含义 图是一种模型 如公路、铁路交通图，通讯网络图等 图是对现实的抽象 很多问题都可以用顶点和边来表示，一般顶点表示实体，边(顶点与顶点之间的连线)表示实体之间的关系，顶点和边的集合定义为图 图论的提出(1) 用图来描述事物及其联系，最早是由瑞士数学家欧拉(Euler)于1736年解决哥尼斯堡七桥问题时提出的 图论的提出(2) 用图来表示这个问题 用四个顶点表示四个地区 用七条边表示七座桥 图的基本概念(1) 图：顶点和边的集合 点的集合用V表示，边的集合用E表示，则图可以表示为G=(V, E) 如下图 图的基本概念(2) 边都没有方向的图称为无向图，前面所讲的图就是无向图。无向图的边eij=(vi, vj)=(vj, vi)= eji 当图中的边都有方向时，称为有向图。为了区别于无向图，有向图用G(V,A)表示 在有向图中，有向边又称为弧，用 aij=(vi, vj)表示， (vi, vj)≠(vj, vi)，弧的方向用箭头标识 既有边又有弧的图称为混合图 下图中从左向右依次为：无向图，有向图，混合图 图的基本概念(3) 集合V中元素的个数称为图G的顶点数，记作p(G)。前例中，p(G)=4 集合E(或A)中元素的个数称为图G的边数，记作q(G)。前例中，q(G)=7 若e=(u, v)∈E(或a=(u, v)∈A)，则称u和v为e (或a )的端点，e (或a )称为顶点u和v的关联边，也称u, v与边e (或a )相关联。前例中，A, B是边e1 的端点，e1 是A, B的关联边 若顶点u和v与同一条边相关联，则称u和v为相邻点 若两条边ei 和ej 有同一个端点，则称ei 和ej 为相邻边 图的基本概念(4) 若一条边的两个端点是同一个顶点，则称该边为环 若两个端点之间有多于一条边，则称为重边(书上称为多重边)，前例中，A, C之间和B, C之间都有两条边 无环也无重边的图称为简单图 与顶点v相关联的边的数目，称为该顶点的“度”(书上称为次)，记为d(v) 度数为奇数的顶点称为奇点，度数为偶数的顶点称为偶点 在有向图中，由顶点指向外的弧的数目称为正度，记为d+，指向该顶点的弧的数目称为负度，记为 d– 度数为0的点称为孤立点，度数为1的点称为悬挂点 图的基本概念(5) 与悬挂点连接的边称为悬挂边 若图中所有的点都是孤立点，则称为空图 定理6.1 所有顶点的度数之和，等于所有边数的两倍 原因：每条边关联两个顶点，计算顶点的度数时，每条边计算了2次 定理6.2 图中奇点的个数总是偶数个 原因：所有顶点的度数之和是偶数，偶点的度数之和也是偶数，因此，奇点的度数之和必为偶数，因此，奇点的个数必是偶数个 图的基本概念(6) 点边交错序列v0, e1, v1, e2, v2, …, vn-1, en, vn 称为链。其中v0称为路的起点， vn称为路的终点 若v0≠vn，称为开链；反之，称为闭链(对于无向图而言，也称为回路) 若链中所含的边均不相同，称为简单链 若链中所含的顶点均不相同，称为初等链(对于无向图而言，也称为通路) 除起点和终点外均不相同的闭链，称为圈(对于无向图而言，也称为初等回路) 图的基本概念(7) 在有向图中，点边交错序列v0, e1, v1, e2, v2, …, vn-1, en, vn (其中ek=(vk-1, vk) )称为路 若v0≠vn，称为开路；反之，称为回路(注意和无向图的回路区分开来) 若路中所含的边均不相同，称为简单路 若路中所含的顶点均不相同，称为初等路 除起点和终点外均不相同的回路，称为初等回路(注意和无向图的初等回路区分开来) 图的基本概念(8) 若一个图(无向图或有向图)中任意两点之间至少有一条初等链连接，则称该图为连通图，否则称为不连通图 在一个有向图中，若任意两点u和v， u到v和v到u之间都至少有一条初等路连接，则称该图为强连通图，否则称为非强连通图 图的基本概念(9) 图的基本概念(10) 如下图，右图是左图的真子图 图的基本概念(11) 如下图，右图是左图的导出子图 图的基本概念(12) 一个没有圈的图称为无圈图或称为林 一个连通的无圈图称为树 一个林的每个连通子图都是一个树 定理6.3：关于树的以下描述是等价的 无圈连通图(定义) 无圈图G，q(G)=p(G)-1(定义+对顶点个数用归纳法) 连通图G，q(G)=p(G)-1(定义+对顶点个数用归纳法) 无圈，但增加一条边可以得到唯一的圈(定义+对顶点个数用归纳法) 连通，但去掉一条边就不连通(反证法) 每一对顶点之间有且仅有一条初等链(反证法) 图的基本概念(13) 若T是图G的部分图，且T是树，则称T为G的生成树(书上称为部分树)