图的定义

图是由顶点的有穷非空集合和顶点之间边的的集合组成,通常表示为: G(V,E), 其中,G表示一个图,V是图G中的顶点的集合,E是图G中边的集合

注意:

  • 线性表中我们把数据元素叫做元素,树中将数据元素叫做结点,在图中数据元素,我们称之为顶点(Vertex)
  • 线性表中可以没有数据元素,称为空表,树中可以没有结点,叫做空树.在图结构中,不允许没有顶点,在定义中,若V是顶点的集合,则强调了顶点集合V有穷非空
  • 线性表中,相邻的数据元素之间具有线性关系,在树结构中,相邻两层的结点具有层次关系,而图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的

各种图的定义

  • 无向边:若顶点vi到vj之间的边没有方向,则称这条边为无向边,用无序偶对(vi, vj)表示.如果图中任意两个顶点之间的边都是无向边,则称该图为无向图

  • 有向边:若顶点vi到vj的边有方向,则称这条边为有向边,也称为弧(Arc). 用有序偶<vi, vj>来表示,vi称为弧尾(tail), vj称为弧头(head),如果图中任意两个顶点之间的边都是有向边,则称该图为有向图.例如:连接顶点A到D的有向边就是弧,A是弧度,D是弧尾,<A, D>表示狐,注意不能写成<D, A>

  • 在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图

  • 在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图,无向完全图有n(n-1)/2条边

  • 在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图

    ,则称该图为有向完全图, 有n(n-1)条边

  • 有很少条边或弧的图称为稀疏图,反之称为稠密图,这里稀疏和稠密是模糊的概念

  • 有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做权(Weight),这些权可以表示从一个顶点到另一个顶点的距离或耗费,这种带权的图通常称为网(network)

  • 假设有两个图G = (V,{E}), G1 = (V1, {E1}), 如果V1包含于V且E1包含于E,则称G1为G的子图(subgraph)

图的顶点和边的关系

对于无向图 G = (V,{E}), 如果边(v, v1) 包含于E, 则称顶点v和v1互为邻接点,即v和v1相邻接,边(v,v1)依附于顶点v和v1,或者说(v,v1)与顶点v和v1相关联.顶点v的度(degree)是和v相关联的边的数目,记为TD(v).

对于有向图G = (V,{E}), 如果弧<v,v1> 包含于E,则称顶点v邻接到顶点v1,顶点v1邻接自顶点v,弧<v,v1>h和顶点v, v1相关联.以顶点v为头的弧的数目称为v的入读(indegree), 记为ID(v); 以v为尾的弧的数目称为v的出度(outDegree), 记为OD(v). 顶点v的度为TD(v) = ID(v) + OD(v).

无向图 G = (V, {E}) 中从顶点v到顶点v1的路径(path) 是一个顶点序列(v = vi.0, vi.2,…., vi.m = v1 ), 其中(vi. j-1, vi, j) 包含于E, i<= j <= m

如果G是无向图,则路径也是有向图,顶点序列应满足<vi.j-1, vi, j> 包含于E, i <= j <= m.

树中根结点到任意结点的路径是唯一的,但是图中顶点与顶点之间的路径却不是唯一的.

路径的长度是路径上的边或者弧的数目.

第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)

序列中顶点不重复出现的路径称为简单路径, 除了第一个顶点和最后一个顶点之外,其余不重复出现的回路,称为简单回路或简单环.

连通相关术语

在无向图G中,如果从顶点v到顶点v1有路径, 则称v和v1是相连通的,如果对于图中任意两个顶点vi, vj 均包含于E, 则vi和vj是相通的,则称G是连通图(connected graph)

无向图中的极大连通子图称为连通分量,注意连通分量的概念, 它强调:

  • 要是子图
  • 子图是连通的
  • 连通子图含有极大顶点数
  • 具有极大定点数的连通子图包含依附于这些顶点的所有边

在有向图G中,如果对于每一对v, v1 包含于V, v != v1, 从v到v1和从v1到v都存在路径,则称G是强连通图.

有向图中的极大强连通子图称作有向图的强连通分量

连通图的生成树定义

一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以够成一棵树的n-1条边.

如果一个有向图恰有一个顶点的入度为0, 其余顶点的入读均为1,则是一颗有向树.

一个有向图的生成森连由若干棵有向数组成,含有图中全部顶点,但只有足以够成若干棵不相交的有向树的弧