路由算法基本概念

　　（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）最小生成树

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