第10周图（上）第1讲-图的概念.pdf

《第10周图（上）第1讲-图的概念.pdf》由会员分享，可在线阅读，更多相关《第10周图（上）第1讲-图的概念.pdf（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第8章章 图图 图图（Graph）G由顶点集合由顶点集合V(G)和边集合和边集合E(G)构成。构成。 8.1.1 图的定义图的定义 说明：说明：对于对于n个顶点的图，对每个顶点连续编号，即顶点的编号为个顶点的图，对每个顶点连续编号，即顶点的编号为 0n- -1。通过编号唯一确定一个顶点。通过编号唯一确定一个顶点。 1 302 4 G=（V，E） V = 0，1，2，3，4 E = (0,1)，(0,4)，(1,2)， (1,3)，(2,3)，(3,4) 图抽象数据类型逻辑结构基本运算（运算描述）图抽象数据类型逻辑结构基本运算（运算描述） 图的基本运算如下：图的基本运算如下： 在图在图G中中，

2、如果代表边的顶点对是无序的如果代表边的顶点对是无序的，则称则称G为为无向图无向图。用圆括号用圆括号 序偶表示无序偶表示无向向边边。 (0,1) 1 302 4 如果如果表示边的顶点对是有序的表示边的顶点对是有序的，则称则称G为为有向图有向图。用尖括号序偶表示用尖括号序偶表示 有向边有向边。 1 302 4 无向图：若无向图：若存在一条边存在一条边(i，j) 顶点顶点i和顶点和顶点j为为端点端点，它们互，它们互为为邻接邻接 点点。 有向图：若有向图：若存在一条边存在一条边 顶点顶点i为为起始端点起始端点（简称为简称为起点起点）， 顶点顶点j为为终止终止端点端点（简称简称终点终点），它们互它们互为

3、为邻接点邻接点。 8.1.2 图的基本术语图的基本术语 1、端点和邻接点、端点和邻接点 2、顶点、顶点的度、入度和的度、入度和出出度度 1 302 4 1 302 4 无向图：以顶点无向图：以顶点i为端点的边数称为该为端点的边数称为该顶点的度顶点的度。 有向图：有向图：以顶点以顶点i为终点的入边的数目，称为该为终点的入边的数目，称为该 顶点的入度顶点的入度。以顶点。以顶点i为始点的出边的数目，称为始点的出边的数目，称 为该为该顶点的出度顶点的出度。一个顶点的入度与出度的和。一个顶点的入度与出度的和 为该为该顶点的度顶点的度。 顶点顶点1的度为的度为3 顶点顶点0的入度为的入度为1 顶点顶点0的

4、出度为的出度为2 顶点顶点0的度为的度为1+2=3 1 0 2 1 n i i de 若一个图中有若一个图中有n个顶点和个顶点和e条边，每个顶点的度为条边，每个顶点的度为di（0in- -1），）， 则有：则有： 1 302 4 n=5，e=8 d0=3，d1=3 ，d2=3 ，d3=4，d4=3 (d0+ d1+ d2+ d3+ d4)/2 = 8 n=5，e=8 d0=3，d1=3 ，d2=3 ，d3=4，d4=3 (d0+ d1+ d2+ d3+ d4)/2 = 8 1 302 4 无向图：每无向图：每两个顶点之间都存在着一两个顶点之间都存在着一条条边，称为边，称为完全无向图完全无向图，

5、 包含有包含有 n(n- -1)/2条边。条边。 有向图：每有向图：每两个顶点之间都存在着方向相反的两两个顶点之间都存在着方向相反的两条条边，称为边，称为完全有向完全有向 图图，包含包含有有n(n- -1)条边条边。 1 02 3 完全无向图：完全无向图：n=4，e=n(n- -1)/2=6 1 02 3 完全有向图：完全有向图：n=4，e=n(n- -1)=12 3、完全图、完全图 当当一个图接近完全图时一个图接近完全图时，则称为则称为稠密图稠密图。 相反相反，当一个图含有较少的边数当一个图含有较少的边数（即当即当en(n- -1)）时时，则称为则称为 稀疏图稀疏图。 4、稠密图、稀疏图、稠

6、密图、稀疏图 设有设有两个图两个图G=(V，E)和和G=(V，E)，若若V是是V的子集的子集，即即V V， 且且E是是E的子集的子集，即即E E，则则称称G是是G的的子图子图。 1 302 4 5、子图、子图 1 302 4 1 302 4 6、路径路径和和路径路径长度长度 在一个图在一个图G=(V，E)中，从顶点中，从顶点i到顶点到顶点j的一条的一条路径路径（i，i1，i2，im， j）。其中所有的）。其中所有的(ix，iy) E(G)，或者，或者 E(G) 路径长度路径长度是指一条路径上经过的边的数目。是指一条路径上经过的边的数目。 若一条路径上除开始点和结束点可以相同外，其余顶点均不相同

7、，则称若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称 此路径为此路径为简单路径简单路径。 0 1的一条的一条简单路简单路 径，长度为径，长度为2 1 02 3 7、回路回路或或环环 若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回 路或环。开始点与结束点相同的简单路径被称为路或环。开始点与结束点相同的简单路径被称为简单回路简单回路或或简单环简单环。 （0，2，1，0）就是）就是一条简一条简 单回路，其长度为单回路，其长度为3。 1 02 3 1 02 3 一个非一个非连通图连通图 8、连通连通、连通图和连通图和

8、连通连通分量分量 1 02 3 一个一个连通图连通图 两个两个连通分量连通分量 无向图：若从顶点无向图：若从顶点i到顶点到顶点j有路径有路径，则称顶点则称顶点i和和j是是连通连通的的。 若图中任意两个顶点都连通若图中任意两个顶点都连通，则称为则称为连通图连通图，否则称为否则称为非连通图非连通图。 无向图无向图G中的极大连通子图称为中的极大连通子图称为G的的连通分量连通分量。显然显然，任何连通图的连任何连通图的连 通分量只有一个通分量只有一个，即本身即本身，而非连通图有多个而非连通图有多个连通分量连通分量。 9、强连通、强连通图和图和强连通强连通分量分量 1 02 3 一个一个强连通图强连通图

9、1 02 3 一个非一个非强连通图强连通图 有向图：若从顶点有向图：若从顶点i到顶点到顶点j有路径，则称从顶点有路径，则称从顶点i到到j是是连通连通的。的。 若图若图G中的任意两个顶点中的任意两个顶点i和和j都连通，即从顶点都连通，即从顶点i到到j和从顶点和从顶点j到到i都存在都存在 路径，则称图路径，则称图G是是强连通图强连通图。 有向图有向图G中的极大强连通子图称为中的极大强连通子图称为G的的强连通分量强连通分量。显然，强连通图。显然，强连通图 只有一个强连通分量，只有一个强连通分量，即即本身。非本身。非强连通图有多个强连通分量。强连通图有多个强连通分量。 两个强两个强连通分量连通分量 1

10、 02 3 一个非一个非强连通图强连通图 在一个非强连通中在一个非强连通中找强连通分量找强连通分量的方法。的方法。 在图中找有向环。在图中找有向环。 扩展该有向环：如果某个顶点到该环中任一顶点有路径，并且该环扩展该有向环：如果某个顶点到该环中任一顶点有路径，并且该环 中任一顶点到这个顶点也有路径，则加入这个顶点。中任一顶点到这个顶点也有路径，则加入这个顶点。 1 02 3 一个非一个非强连通图强连通图 4 5 3个强个强连通分量连通分量 1 02 34 5 10、权和网权和网 1 2 0 3 2 3 5 6 一个一个网网 图中每一条边都可以附带有一个对应的数值，这种与边相关的数图中每一条边都可以附带有一个对应的数值，这种与边相关的数 值称为值称为权权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。权可以表示从一个顶点到另一个顶点的距离或花费的代价。 边上带有权的图称为边上带有权的图称为带权图带权图，也称作也称作网网。 本讲完本讲完