（1）图的定义
所谓图G是一个三元组，记作G＝〈V（G），E（G），φ（G）），其中：
V（G）＝（v1,v2，…，vn），V（G）=Φ，称为图G的节点集合。
E（G）＝（e1，e2，…，en）是G的边集合，其中ei：为｛vj，vt）或（vj，vt〉。若ei为（vj，vt），称ei为 vj和vt为端点的无向边；若ei为〈vi，vt〉，称色为以vj为起点，vt为终点的有向边。
φ（G）：E→V×V称为关联函数。
（2）无向图
每一条边都是无向边的图称为无向图。
（3）有向图
每一条边都是有向边的图称为有向图。
（4）图的顶点度
设G是任意图，x为G的任一节点，与节点x关联的边数称为x的度数。记作deg（x）。射入x的边数称为宽的入度 ，记作deg＋（x）；射出∝的边数称为贸的出度，记作deg-（x).
（5）连通图
在无向图G中，如果从顶点x到顶点y有路径，则称x和y是连通的。如果对于图中任意两个顶点都是连通的，则称G是连通图。
（6）带权图
有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数称为杈，带权的图称为带权图。
（7）树
无圈连通无向图，树中度数为1的节点称为树的叶，树中度数大于1的节点称为树的分支点或内点。不相交的若干树称为森林。
（8）生成树
如果T是G的一个生成子图而且又是一稞树，则T是图G的一颗生成树。
（9）最小生成树
连通加杈图里杈和最小的生成树称为最小生成树。
