图（Graph）由非空的顶点（vertices）集合和一个描述顶点之间关系——边（无向边edges）或弧（有向边）的有限集合组成的，可以用二元组定义为：G=(V,VR)

其中，G表示一个图，V是图中顶点的集合，VR是图中边或弧的集合。

VR代表弧的集合时，VR＝{<v,w>| v,w∈V 且 P(v,w)定义了弧<v,w>的意义}。<v,w>表示从 v 到 w 的一条弧，并称 v 为弧尾，w 为弧头。

由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。图7.1是一个有向图G1， G₁ = (V₁, VR₁) ，其中V₁={A, B, C, D, E}，VR₁={<A,B>, <A,E>, <B,C>, <C,D>, <D,B>, <D,A>, <E,C> }。

若<v, w>ÎVR 必有<w, v>ÎVR, 则称 (v,w) 为顶点v 和顶点 w 之间存在一条边，即一条边相当与两条互相指向的有向边。由顶点集和边集构成的图称作无向图。图7.2是一个无向图G2，G₂=(V₂,VR₂) 其中V₂={A, B, C, D, E, F}，VR₂={（A,B）,（A,E）,（B,E）,（C,D）, （D,F）,（B,F）, （C,F）}。

下面是图的基本术语：

（1）网、子图。

弧或边带权的图分别称作有向网或无向网，图7.3是一个有向网。设图G=(V,{VR}) 和图 G¢=(V¢,{VR¢})，且 V¢ÍV, VR¢ÍVR，则称 G¢ 为 G 的子图。

（2）完全图、稀疏图、稠密图。

假设图中有 n 个顶点，e 条边，则含有 e=n(n-1)/2 条边的无向图称作完全图；含有 e=n(n-1) 条弧的有向图称作有向完全图；若边或弧的个数很少，习惯值是n(n-1)的70%以下，则称作稀疏图，否则称作稠密图。

（3）邻接点、度、入度、出度。

对于无向图来说，假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点，边(v,w) 和顶点v 和w 相关联。和顶点v 关联的边的数目定义为顶点v的度，记为ID(v)。例图7.2中，ID(B) = 3 ，ID(A) = 2。

对有向图来说，以顶点v为弧尾的弧的数目称为为顶点的出度，记为OD(v)。以顶点v为弧头的弧的数目称为顶点的入度，记为ID(v)。出度和入度之和称为顶点的度，记为TD(v)。例图7.1中，OD(B) = 1，ID(B) = 2，TD(B) = 3。

（4）路径、路径长度、简单路径、简单回路。

设图G=(V, VR)中的一个顶点序列{ u=v_i,0,v_i,1, …, v_i,m=w}中，(v_i,j-1,v_i,j)ÎVR 1≤j≤m, 则称从顶点u 到顶点w 之间存在一条路径。路径上边的数目称作路径长度。例图7.1中，路径{A,B,C,D}的长度为3。

简单路径：序列中顶点不重复出现的路径。

简单回路：序列中第一个顶点和最后一个顶点相同的简单路径。

（5）连通图、连通分量、强连通图、强连通分量。

若图G中任意两个顶点之间都有路径相通，则称此图为连通图。图7.2就是一个连通图。

若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。去掉图7.2中结点B、F之间的边，则此连通图变为非连通图，图中有两个连通分量

对于有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。极大连通子图称作强连通分量。图7.1就是一个强连通图。

（6）生成树、生成森林。

假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。

对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。