全国计算机等级考试四级含金量,2017年全国计算机等级考试四级复习纲要：图

五、图

图的概念

图是一种较线性表和树形结构更为复杂的数据结构。在线性表中每个数据元素只有一个（直接）前驱和后继，即各数据元素之间仅有线性关系。在树形结构中，数据元素之间有明显的层次关系，每一层中的数据元素只和上一层中的一个元素（即双亲结点）相关。而在图中，任意两个数据元素之间均有可能相关。

图（graph）是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都有着广泛的应用。图的二元组定义为:

G=（V，E）

其中，V是非空的顶点集合，即

V=｛v i |1≤i≤n，n≥1，v i ∈elemtype，n为顶点数｝

E是V上二元关系的集合，一般只讨论仅含一个二元关系的情况，且直接用E表示这个关系。这样，E就是V上顶点的序偶或无序对（每个无序对（x，y）是两个对称序偶和的简写形式）的集合。对于V上的每个顶点，在E中都允许有任意多个前驱和任意多个后继，即对每个顶点的前驱和后继个数均不加限制。回顾一下线性表和树的二元组定义，都是在其二元关系上规定了限制条件，线性表的限制条件是只允许每个结点有一个前驱和一个后继，树的限制条件是只允许每个结点有一个前驱。因此，图比线性表和树更具有广泛性，它包含线性表和树在内，线性表和树可以认为是图的简单情况。来源：www.examda.com

对于一个图G，若E是序偶的集合，则每个序偶对应图形中的一条有向边，若E是无序对的集合，则每个无序对对应图形中的一条无向边，所以可把E看作为边的集合。这样，图的二元组定义可叙述为:图的非空顶点集（vertexset）和边集（edgeset）所组成。针对图G，顶点集和边集可分别记为V（G）和E（G）。边集E（G）允许是空集，若是空集，图G中的顶点均为孤立顶点。对于一个图G，若边集E（G）为有向边的集合，则称此图为有向图（digraph），若边集E（G）为无向边的集合，则称此图为无向图（undigraph）。

本文来源：https://www.wddqw.com/K4oO.html