一个无环，无多重边的图称为简单图；一个 无环，但允许有多重边的图称为多重图。
第1节 图的概念
以点v为端点的边的个数称为v的次，记为dG (v) 或 d(v) 。
注意：图中环在计算边时记做两次。
称次为1的点为悬挂点，悬挂点的关连边称为 悬挂边，次为零的点称为孤立点。
第1节 图的概念
定理1 图 G (V, E) 中，所有点的次之和是边数 的两倍，即
(vi1 , vi2 ,, vik1 , vik )
点 vi1 , vi2 ,, vik1 , vik 都是不同的，则称之为初等链；若
圈 中，点 都是不同的，则称 (vi1 , vi2 ,, vik1 , vi1 )
vi1 , vi2 ,, vik1
之为初等圈；若链（圈）中含的边均不相同，则称
有向图实例
第1节 图的概念
图G或D中的点数记为p(G)或p(D)，边（弧）
数记为q(G)或q(D) 。简记为p或q。
第1节 图的概念
三、术语
1、无向图 G (V , E)
若 e [u,v] E ，则称u，v是e的端点，也称u， v是相邻的。称e是点u（及点v）的关连边。
若图G中，某个边e的两个端点相同，则称e是 环；若两个点之间有多于一条的边，称这些边为多 重边。
2.2 图的支撑树
例6 在图7-15中，用“破圈法” 求出图的一 个支撑树。
2.2 图的支撑树
另外一种寻求连通图的支撑树的方法—“避圈 法” ：在图中任取一条边e1 ，找一条与e1 不构成 圈的边e2 ，再找一条与{e1,e2} 不构成圈的边e3 。一 般，设已有{e1, e2,, ek}，找一条与{e1, e2,, ek}中的任何 一条边不构成圈的边ek 1。重复上述过程，直到不能 进行为止。
