1、第 8章 图论第 8章 图论 8.1 图的基本概念 8.2 路径和回路8. 图的矩阵表示8. 二部图8.5 平面图8.6 树8.7 有向树8.8 运输网络问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。 欧拉在 1736年解决了这个问题 。判定法则：如果通奇数座桥的地方不止两个，那么满足要求的路线便不存在了。如果只有两个地方通奇数座桥，则可从其中任何一地出发找到所要求的路线。若没有一个地 方通奇数座桥，则从任何一地出发，所求的路线都能实现 第 8章 图论定义 8.11 一个 图 G是一个三重组 V(G),E(G),G ,其中V(G)是一个非空的 结点 (或叫顶点 )集合
2、,E(G)是 边 的集合 ,G是从边集 E到结点偶对集合上的函数。一个图可以用一个图形表示。例 1设 G= V(G),E(G),G ,其中 V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,G(e1)=(a,b),G(e2)=(a,c),G(e3)=(b,d),G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d),G(e7)=(b,b)则图 G可用图 8.11 表示。8.1 图的基本概念 8.1.1 图第 8章 图论第 8章 图论定义中的结点偶对可以是有序的 ,也可以是无序的。若边 e所对应的偶对 a,b 是有序的 ,则称 e是 有向边。有向边简称
3、弧 ,a叫弧 e的始点 ,b叫弧 e的终点 ,统称为 e的端点。称 e是关联于结点 a和 b的 ,结点 a和结点 b是 邻接的 。若边 e所对应的偶对 (a,b)是无序的 ,则称 e是 无向边。无向边简称棱 ,除无始点和终点的术语外 ,其它术语与有向边相同。每一条边都是有向边的图称为 有向图 , 第三章中的关系图都是有向图的例子。每一条边都是无向边的图称为 无向图 ；如果在图中一些边是有向边 ,而另一些边是无向边 ,则称这个图是 混合图 。我们仅讨论有向图和无向图 ,且 V(G)和 E(G)限于有限集合。第 8章 图论约定用 a,b 表示有向边 ,(a,b)表示无向边 ,既表示有向边又表示无向
4、边时用 a,b。有向图和无向图也 可互相转化 。例如 ,把无向图中每一条边都看作两条方向不同的有向边 ,这时无向图就成为有向图。又如 ,把有向图中每条有向边都看作无向边 ,就得到无向图。这个无向图习惯上叫做该 有向图的底图。在图中 ,不与任何结点邻接的结点称为 弧立结点 ；全由孤立结点构成的图称为 零图 。关联于同一结点的一条边称为 自回路 ；自回路的方向不定。自回路的有无不使有关图论的各个定理发生重大变化 ,所以有许多场合都略去自回路。第 8章 图论在有向图中 ,两结点间 (包括结点自身间 )若同始点和同终点的边多于一条 ,则这几条边称为 平行边 。在无向图中 ,两结点间 (包括结点自身间
5、)若多于一条边 ,则称这几条边为平行边。两结点 a、 b间互相平行的边的条数称为 边 a,b 的重数 。仅有一条时重数为 1,无边时重数为 0。定义 8.12 含有平行边的图称为 多重图 。非多重图称为 线图 。无自回路的线图称为 简单图 。在图 8.13 中 ,(a)、 (b)是多重图 ,(c)是线图 ,(d)是简单图 ,关系图都是线图。第 8章 图论图 8.13 第 8章 图论定义 8.13 赋权图 G是一个三重组 V,E,g 或四重组 V,E,f,g ,其中 V是结点集合 , E是边的集合 ,f是定义在 V上的函数 ,g是定义在 E上的函数。右图给出一个赋权图。V=v1,v2,v3E=e
6、1,e2=(v1,v2),(v2,v3)f(v1)=5,f(v2)=8,f(v3)=11g(e1)=4.6,g(e2)=7.5第 8章 图论8.1.2 结点的次数定义 8.14 在 有向图中 ,对于任何结点 v,以 v为始点的边的条数称为结点 v的 引出次数 (或出度 ),记为 deg+(v);以 v为终点的边的条数称为结点 v的 引入次数 (或入度 ),记为 deg-(v);结点 v的引出次数和引入次数之和称为结点v的 次数 (或度数 ),记作 deg(v)。 在无向图中 ,结点 v的次数是与结点 v相关联的边的条数 ,也记为 deg(v)。 孤立结点的次数为零。第 8章 图论定理 8.11 设 G是一个 (n,m)图 ,它的结点集合为V=v1,v2, vn,则证 因为每一条边提供两个次数 ,而所有各结点次数之和为 m条边所提供 ,所以上式成立。在有向图中 ,上式也可写成 :
