（1）图的定义

　　所谓图g是一个三元组，记作g＝〈v（g），e（g），φ（g）），其中：

　　v（g）＝（v₁,v₂，…，v_n），v（g）=φ，称为图g的节点集合。

　　e（g）＝（e1，e2，…，en）是g的边集合，其中ei：为｛v_j，v_t）或（v_j，v_t〉。若ei为（v_j，v_t），称ei为 vj和vt为端点的无向边；若ei为〈v_i，v_t〉，称色为以v_j为起点，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）最小生成树

　　连通加杈图里杈和最小的生成树称为最小生成树。

　　欢迎转载，信息来源维库电子市场网（www.dzsc.com）