1.1 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成。 1.2 通常表示为G(V,E) ,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。 1.3 线性表中把数据元素叫元素,树中将数据元素叫结点,在图中数据元素叫做顶点。 1.4 在线性表中可以没有数据元素,称为空表。 树中可以没有结点,称之为空树。 但是在图中不能没有顶点。这在定义中也有体现:V是顶点的有穷非空集合。 1.5 在线性表中相邻的数据元素之间具有线性关系。 在树的结构中,相邻两层的结点具有层次关系。 在图中,任意两个顶点之间都有可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空集。
2.1 无向边:顶点vi 到vj 之间的边没有方向,则这条边为无向边,用无序偶对(vi,vj)来表示。 2.2 无向图:如果图中任意两个顶点之间的边都是无向边,则该图称为无向图。 如图下图所示: 从A到D的边是无向边,所以可以表示成无序对(A,D)或者·(D,A)。
2.3 有向边:从顶点vi到vj 的边有方向,则称这条为有向边,也·称为弧。用有序偶<vi.vj> 来表示,vi称为弧尾(tail),vj称为弧头(head)。 2.4 有向图:图中任意两个顶点之间的边都是有向边,则称图为有向图。 如下图所示: 从A到B的边就是有向边(弧),A是弧尾 B是弧头。<A,B>表示弧。(不能写成<B,A>)
2.5 无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称为无向完全图。(也就是每个顶点除了它自身之外都要有一条边与其它顶点相连) 如下图所示:
含有n个顶点的无向完全图有n*(n-1)/2 个边。 上图也就是有43/2 =6 条边。 2.6 有向完全图:在有向图中,如何任意两个顶点之间都存在方向互为相反的两条弧,则称为有向完全图。 如下图所示:
其中含有n个顶点的有向完全图有n(n-1) 条边。
得出结论: 对于n个顶点和e条边数的图 无向图—0<=e<=n(n-1)/2 有向图—0<=e<=n*(n-1) 2.7 稠密图与稀疏图: 稠密图—有很多条边或弧的图 稀疏图—有很少条边或弧的图 这里稀疏图和稠密图的概念是相对而言的。 2.8 网:带权的图称为网 带权指的是图的边或者弧具有与它相关的数字 如下图所示:
2.9 子图:假设有两个图G=(v,{e})和G1=(v1,{e1}),如果v1属于而且e1属于e,则称G1是G的子图。 如下图所示:右边的图都是左边图的子图
3.1 对于无向图G=(v,{E}),如果存在边(v,v1)属于E,则顶点v与v1互为邻接点,边(v,v1)依附于顶点v和v1,或者是(v,v1)与顶点v,v1相关联。 顶点v的度是和v相关联的边的数目,记为TD(v)。 通过以上面的图,我们可以不难发现各个顶点的度之和=所以边数之和*2 3.2 对于有向图G=(v,{E}),如果弧<v,v1>属于E,则称则顶点v邻接到顶点v1,顶点v1邻接自顶点v。弧<v,v1>和顶点v,v1相关联。 以顶点v为头的弧的数目称为v的入度,记为ID(V); 以顶点v为尾的弧的数目称为v的出度,记为OD(V); 所以顶点v的度为出度+入度,即TD(V)=ID(V)+OD(V); 3.3 在树中根结点到任意结点的路径是唯一的,但是图中顶点与顶点之间的路径却不是唯一的。 3.3.1 路径的长度:是路径上的边或弧的数目之和。 3.3.2 回路/环: 第一个顶点到最后一个顶点相同的路径。 3.3.3 简单路径:序列中顶点不重复出现的路径。 3.3.4 简单回路/简单环:除了第一个顶点和最后一个顶点之外,其余顶点都不重复出现的回路。
4.1连通图:在无向图中,如果从顶点v到顶点v1有路径,则称为v和v1是连通的。如果图中任意两个顶点vi,vj 属于E,vi和vj都是连通的。则称图G是连通图。 如下图所示就是一个连通图:
如下图所示,就不是连通图, 因为,中间的两个顶点和外面的四个顶点都互不相连。
4.2 连通分量 无向图中的极大连通子图称为连通分量。 连通分量强调: 1.是子图 2.子图要是连通的 3.连通子图有极大顶点数 4.具有极大顶点数的连通子图包含依附于这些顶点的所有边 4.3 强连通图 在有向图G中,如果对于每一对vi,vj属于V,vi不等于vj,从vi到vj和从vj到vi都存在路径,则G是强连通图. 有向图的极大强连通子图称为有向图的强连通分量。
上面这个图就不是强连通图,因为在A和D之间,D到A就没有路径。
此图就是强连通图,它是上一个图的极大强连通子图,即是它的强连通分量。 4.4 无向图中连通且n个顶点n-1条边叫生成树。 有向图中一顶点入度为0其余顶点入度为·1的叫做有向树。 一个有向图由若干棵有向树构成生成森林。