7.1.2 图的基本术语.pptx

7.1.2图的基本术语;（2）端点和相邻点

在一个无向图中，若存在一条边(i,j)，则称顶点i、j为该边的两个端点，并称它们互为相邻点（或者邻接点）。

例如，图7.1(a)中，顶点0和顶点1是两个端点，它们互为相邻点。;在一个有向图中，若存在一条边i,j，则称此边是顶点i的一条出边，同时也是顶点j的一条入边，称顶点i和j分别为此边的起始端点（简称为起点）和终止端点（简称终点）。

例如，图7.1(b)中，对于边0,1，该边是顶点0的出边，顶点1的入边，同时，顶点0称为起点，顶点1称为终点。;（3）度、入度和出度

顶点v的度记为D(v)。对于无向图，每个顶点的度定义为以该顶点为一个端点的边数。

对于有向图，顶点v的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。

例如，图7.1(a)中，D(0)=2。;在图7.1(b)中，顶点4的入度为2，出度为1，所以D(4)=3。;若一个图（无论有向图或无向图）中有n个顶点和e条边，每个顶点的度为di（0≤i≤n-1），则有：;【例7.2】一个无向图中有16条边，度为4的顶点有3个，度为3的顶点有4个，其余顶点的度均小于3，则该图至少有（）个顶点。

A.10 B.11 C.12 D.13;（4）子图

设有两个图G=(V,E)和G=(V,E)，若V是V的子集，即V?V，且E是E的子集，即E?E，则称G是G的子图。;注意：对于一个图G=(V,E)，V是V的子集，即V?V，E是E的子集，即E?E。而(V,E)可能不是一个图，所以由V的子集和E的子集并非一定构成G的子图。;（5）完全无向图和完全有向图

对于无向图，若具有n(n-1)/2条边，则称之为完全无向图。

例如，图7.2(a)是完全无向图G3，这里n=4，边数为6。;（5）完全无向图和完全有向图

对于有向图，若具有n(n-1)条边，则称之为完全有向图。

例如，图7.2(b)是完全有向图G4，这里n=4，边数为12。;（6）稀疏图和稠密图

边数较少（边数enlog2n，其中n为顶点数）的图称为稀疏图。边总较多的图称为稠密图。;（7）路径和路径长度;（8）???单路径

若一条路径的顶点序列中顶点不重复出现，称该路径为简单路径。

例如，图7.1(a)中，路径0→1→2→4是一条简单路径，其长度为3。;图7.1(b)中，路径0→1→3→2是一条简单路径，其长度也为3。;（9）回路（环）

若一条路径上的开始点和结束点为同一个顶点，则称该路径为回路（环）。除开始点与结束点相同外，其余顶点不重复出现的回路称为简单回路（简单环）。

例如，图7.1(a)中，路径0→1→2→4→3→0是一条回路（环），也是一条简单回路（简单环）。;（10）连通、连通图和连通分量

在无向图G中，若从顶点i到顶点j有路径，则称顶点i和j是连通的。若图G中任意两个顶点都是连通的，则称G为连通图，否则为非连通图。无向图G中极大连通子图称为G的连通分量。

例如，图7.1(a)的连通分量就是自身，因为该图是连通图。;（11）强连通图和强连通分量

在有向图G中，若任意两个顶点i和j都是连通的，即从顶点i到j和从顶点j到i都存在路径，则称该图是强连通图。

有向图G中极大强连通子图称为G的强连通分量。;对于图7.1(b)的有向图，顶点0的入度为0，也就是说其余顶点都没有到达顶点0的路径，所以单个顶点0是一个强连通分量；

顶点1只有一条从顶点0到它的入边，除顶点0外其余顶点没有到达顶点1的路径，所以单个顶点1也是一个强连通分量；

点2、3、4构成一个有向环，这些顶点之间都有路径，该图的强连通分量。;（12）权和网

在一个图中，每条边可以标上具有某种含义的数值，该数值称为该边的权。边上带权的图称为带权图，也称为网。

图7.4中的图G5就是一个带权图。本书中规定所有边的权均为非负数。;【例7.3】如果图G是一个具有n个顶点的连通无向图，那么G最多有多少条边？G最少有多少条边？

如果图G是一个具有n个顶点的强连通有向图，那么G最多有多少条边？G最少有多少条边？;图G为强连通有向图:

图G为完全有向图时边最多，即图G最多有n(n-1)条边；

图G为一棵树时边最少，即G最少有n条边。