其中，V={Vi | Vi ∈datatype, i=0,1,……,n-1} 是图中元素Vi（称为顶点Vertex ）的集合，n=0时，V为空集，记为φ。
R是顶点之间的关系集，P(Vi,Vj)为顶点Vi与Vj之间是否存在路径的判定条件，即若Vi与Vj之间的路径存在，则关系< Vi,Vj >∈R。
二、图的基本术语
1)有向图(Digraph)
设Vi、Vj为图中的两个顶点，若关系存在方向性，即: ≠ ,则称相应的图为有向图。< Vi,Vj >∈R，表示从顶点 Vi到Vj的一条弧（Arc）：
Vi为弧尾，Vj为弧头
2)无向图(Undigraph)
设Vi、Vj为图中的两个顶点，若关系无方向性，即：当∈R时，必有∈R，则称此时的图为无向图。关系用（Vi,Vj）或（Vj,Vi）表示，称为图中的一条边（Edge）：（Vi,Vj）
eg:
设有向图G1 = (V,R)
V={V0,V1,V2,V3,V4,V5} (n = 6)
R = { }
则G1的表示如下图所示:
值的注意的是，按照图的定义，图中的顶点V0经过V2到达V5,存在一条路径(V0,V2,V5),但G1的R中并未出现这样的关系，这是因为在关系R的等价闭包R'中，应包括关系传递性，即若:、 ∈R，则有∈R'。
故图的关系集一般是取最小关系集，即只写出图中弧的条数即可。
9)生成树(Spanning Tree)
无向连通图的生成树是图中的一个极小连通子图，它包含有图中全部顶点(设顶点数为n),但只有足以构成一棵树的n-1条边。如图的G2中，以V0为起点(根)的一棵生成树如图所示。若在生成树上增加一条边，必定形成回路，因为它使得两顶点间有了第二条通路。若图中有n个顶点，而小于n-1条边，则图是 非连通的，但有n-1条边的图不一定是树。
10)生成森林
若有向图中恰有一个顶点入度为0,其余顶点入度全为1,则此图可视为一棵有向树。有向图的生成森林F由图中若干棵有向树 组成。F是有向图的一个子图,包含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
如图G4,其生成森林如下:
几个问题
1.什么是子图?
答:假设G=(V,E)和G'=(V',E')是两个图(同为无向图或同为有向图)，若V'∈V,并且E'∈E,则称G'是G的子图。
2.什么是路径长度?
答:无向图G=(V,E)中，若存在顶点序列Vi0,Vi1,...,Vin,使得(Vi0,Vi1)，(Vi1,Vi2),...,(Vin-1,Vin)都在E中(若是有向图，则使得,,...,都在E中),则称从顶点Vi0到Vin存在一条路径，路径长度为路径上的边数。
3.什么是连通图?
答:无向图G=(V,E)中，若从Vi到Vj有一条路径(从Vj到Vi也一定有一条路径),则称Vi和Vj是连通的。若V(G)中任意两个不同的顶点Vi和Vj都是连通的(即有路径),则称G为连通图。
3.什么是强连通图?
答:有向图G=中，若V(G)中任意两个不同的顶点Vi和Vj都存在从Vi到Vj以及从Vj到Vi的路径，则称图G是强连通图。
