图相关定义

图的定义

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

关于图的定义我们应该注意的几个地方:

1.线性表中我们把数据元素叫做元素，树中将元素叫做结点，在图中数据元素，我们称之为顶点（Vertex）
2.线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。但是在图中，不允许没有顶点，在定义中强调了顶点集合为有穷非空集合
3.线性表中,相邻的数据元素之间具有线性关系，在树结构中，相邻的两层具有层次关系，顶点之间的关系用边来表示，边集可以是空的

各种图的定义

1.无向边:若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge）,用无序偶对（vi,vj）或者（vj,vi）表示如果图中任意两个顶点之间的边都是无向边，那么称该图为无向图
无向图

2.有向边:若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧(Arc),用有序偶对<vi,vj>表示，如果图中任意两个顶点之间都是有向边，则称该图为有向图
有向图

3.在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图
4.无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的完全无向图有n*(n-1)/2条边
无向完全图:

5.在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称改图为有向完全图
有向完全图

6.对于有n个顶点和e条边的图·，无向图0<=e<=n*（n-1）/2,有向图0<=e<=n*(n-1)
7.有很少边的图称为稀疏图，反之为稠密图，这里稀疏和稠密是相对而言没有明确的标准
8.有些图的边或者是弧具有与它相关的数字，这种与图的边或者弧相关的数叫做权（weight）。这些权可以表示从一个顶点到另一个顶点的距离或者是耗费。这种带权图称为网（Network）
网

9.假设有两个图G=(V,{E})和G`=(V’,{E’}),如果V’包含于V并且E’包含于E,则称G’为G的子图（Subgraph）
右侧均为左侧子图:

图与顶点之间的关系

1.对于无向图G=(V,{E}),如果边（v,v’）∈ E,则称顶点v,v’互为邻接点（Adjacent）,即v和v’相邻接。边（v,v’）
依附（incident）于顶点v和v’,或者说（v,v’）与顶点v和v’相关联。顶点v的度（Degree）是和v相关联的边的数目，记为TD(v),边和度的关系:e=1/2*（TD(v1)+TD(v2)+TD(v3)+…+TD(vn)）
2.对于有向图G=(V,{E}),如果弧<v,v’>∈E,则称顶点v邻接到v’,顶点v’邻接自顶点v。弧<v,v’>和顶点v,v’相关联，以顶点v为头的弧的数目称为v的入度（InDegree）,记为ID（v）;以v为尾的弧的数目称之为出度(OutDegree),记为OD(v),顶点v的度为TD(v)=ID(v)+OD(v),边和度的关系为:e=(ID(v1)+ID(v2)+ID(v3)+…+ID(vn))=(OD(v1)+OD(v2)+OD(v3)+…+OD(vn))
3.无向图G=(V,{E})中从顶点v到顶点v’的路径（Path）是一个顶点序列（v=vi,0,vi,1…,vi,m=v’）,其中（vi,j-1，vi,j）∈ E,1<=j<=m
4.路径的长度是路径上的边或弧的数目
5.第一个顶点到最后一个顶点相同的路径称为回路或者是环（Cycle）.序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或者是简单环
简单环

非简单环

(原因:C点在路径上重复)

连通图相关术语

1.在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。如果对于图中任意两个顶点vi,vj∈V,vi和vj都是连通的，则G是连通的
连通图

非连通图

（G和F孤立和其他点不连通）
2.无向图中的极大连通子图称为连通分量,他强调:
2.1:要是子图
2.2:子图要是联通的
2.3:连通子图含有极大顶点数
2.4:具有极大顶点数的连通子图包含依附于这些定点的所有边
上图的连通分量


3.在有向图G中，如果对于每一对vi,vj∈V,.vi≠vj,从vi到vj和从vj到vi都存在路径,则称G为强连通图。有向图中的·极大强连通子图乘做有向图的强连通分量
强连通图

4.连通图的生成树定义:
一个连通图的生成树是一个极小连通子图，它含有图中的全部的n个顶点，但只有构成一棵树的n-1条边
该图的生成树

生成树1：

生成树2：

5.如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一颗有向树
6.一个有向树的生成森林由若干棵有向树组成，含有图中的所有顶点，但只有足以构成若干颗不相交的有向树的弧
右侧两个为左侧图的生成森林，右侧的每一个为一个有向树