（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）最小生成树　　连通加杈图里杈和最小的生成树称为最小生成树。　　欢迎转载，信息来源维库电子市场网（）