基本概念
图（graph）是数学关系的表示，由非空节点集V和有限边集E组成。
不同节点组成的无序对称作边（edge）。
设图G，若令V={v1,v2,...,vn}是包含n个节点的集合，其m条边的集合E={e1,e2,...,em}，其中，每一条边都是集合V的二元素子集{vi,vj}，简记为vivj或vjvi。
集合V(G)中的基数n表示图的阶（rank）。
集合E(G)中的基数m表示图的规模（size）。
若vi∈V(G)，vj∈V(G)，且vivj组成的节点对vivj∈E(G)，或者说vivj是图G的边，则称vi和vj邻接（adjacency），否则，称vi和vj不邻接（unadjacency）。
结点的度（degree）是指与v邻接的节点数，记作deg(v)，若特指图G的结点v的度就写作degG(v)。
边vivj与vi和vj相关联（relevancy）。
度为零的点称作孤立点（isolated point）。
度为1的结点称为端结点（end point），若是一个很像树的图，度为1的结点又称为叶子（leaf）。
图G的最小度（min degree）是指所有结点中的最小度数，记作δ(G)。
图G的最大度（max degree）是指所有结点中的最大度数，记作Δ(G)。
若图G的所有结点有相同的度数，那么δ(G)=Δ(G)，图G称为正则图（regular graph）。
若图G的所有结点的度都是r，则图G称为r-正则图（r-regular graph）。
基本定理
欧拉定理 在任何图中，结点度的总和等于边数的两倍。
推论 在任何图中，结点度的总和是一个非负偶数。
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
