稀疏图:边较少的图。通常边数<m2 稠密图:边很多的图。无向图中,边数接近mm1)2; 有向图中,边数接近m(n-1) 子图:设有两个图G=(V,E)和G=(V,E)。若WcV且 E'cE,则称图G是图G的子图。 (a)G1 子图 子图 子图 (b)63子图子图子图
11
带权图:即边上带权的图。其中权是指每条边可以标上 具有某种含义的数值(即与边相关的数) 网络:=带权图 连通图:在无向图中,若从顶点v到顶点n有路径则称顶点v 与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。 非连通图的极大连通子图叫做连通分量。 强连通图在有向图中,若对于每一对顶点和v,都存在一条从 到v和从到v的路径,则称此图是强连通图 非强连通图的极大强连通子图叫做强连通分量。 有两类图形 (O 不在本课程 (2) 讨论之列: (a)带自身环的图 (b)多重图
12
邻接点:若(u,)是E(G)中的一条边,则称u与v互为邻接顶点 弧头和弧尾:有向边(u,n)称为弧,边的始点叫叫弧尾,终点v叫弧头 度、入度和出度:顶点v的度是与它相关联的边的条数。记作D(v) 在有向图中顶点的度等于该顶点的入度与出度之和。 顶点v的入度是以v为终点的有向边的条数,记作ID(v 顶点v的出度是以v为始点的有向边的条数,记作OD(y) 问:当有向图中仅1个顶点的入度为0,其余顶点的 入度均为1,此时是何形状? 答:是树!而且是一棵有向树! 生成树:是一个极小连通子图,它含有图中全部顶点但只有n-1条边。 今如果在生成树上添加条边,必定构成一个环。 ◆若图中有n个顶点,却少于-1条边,必为非连通图。 生成森林:由若干棵生成树组成,含全部顶点,但构成这些 树的边是最少的
13
路径:在图G=(V,E)中,若从顶点v出发,沿一些边经过一些顶 点vn,",…,rm,到达顶点y。则称顶点序列(nVn"2… m1y)为从顶点到顶点v的路径。它经过的边("m) (7,y)…、(vmp)应当是属于E的边 路径长度非带权图的路径长度是指此路径上边的条数; 带权图的路径长度是指路径上各边的权之 和 简单路径:路径上各顶点v1,V2,Vm均不互相重复。 路: 若路径上第一个顶点v1与最后一个顶点vm重合,则 称这样的路径为回路或环 例: (3 (a)简单路径 (b)非简单路径 (C)回路
14
例 有向完备图 无向完备图 例 Q④⑤ ① 图与子图 例 例 顶点5的度:3 顶点2入度:1出度:3 顶点2的度: 顶点4入度:1出度:0
15