§1图的基本概念 (12)孤立结点:不与任何结点相连接的结点 (13)零图:仅包含孤立结点的图,又称(n,0)图 (14)平凡图:只有一个结点的图(1,0)图 《定义》:在有向图中,对于任何结点v,以v为始点的边的条 数,称为结点v的引出度数,记作;以终点的 边的条数称为v的引入度数,记作结点的v的大数 和引出度数之和称为v的度数,用deg(v)表示。 由定义可见 度数deg(v) 对无向图讲:结点的度数等华邾以结点关联的边的条数
§1图的基本概念 (12)孤立结点：不与任何结点相连接的结点 (13)零图：仅包含孤立结点的图，又称（ｎ，０）图 (14)平凡图：只有一个结点的图（1，0）图 《定义》：在有向图中，对于任何结点v，以v为始点的边的条 数，称为结点v的引出度数， 记作 ；以v点为终点的 边的条数称为v的引入度数，记作 结点的v的引入度数 和引出度数之和称为v的度数，用deg（v）表示。 由定义可见： 度数deg（v）＝ 对无向图讲：结点的度数等于和该结点关联的边的条数 deg (v) + deg (v) + deg (v) − deg (v) − +
§1图的基本概念 例 (15)正则图:所有结点均具有同样度数的简单无向图 例 (一次正则图) b (二次正则图) (三次正则图)
§1图的基本概念 例： (15)正则图：所有结点均具有同样度数的简单无向图 例：
s1图的基本概念 《定理》每个图中,结点度数的总和等于边 数的两deg(v)=2e
§1图的基本概念 《定理》： 每个图中，结点度数的总和等于边 数的两倍。 = = n i i v e 1 deg( ) 2
§1图的基本概念 例:若图G有n个顶点,(n+1)条边,则G中至少有 个结点的度数>3 证明:设G中有n个结点分别为v,V2…,Vn,则由握手 定理: ∑deg(v)=2e=2(m+1) 2(n+1) 而结点的平均度数 2+>2 结点中至少有一个顶点的度数>3
§1图的基本概念 例：若图Ｇ有n个顶点，（n+1）条边，则Ｇ中至少有 一个结点的度数≥３。 证明：设Ｇ中有n个结点分别为v1 ,v2 ,…,vn，则由握手 定理： 而结点的平均度数= ∴结点中至少有一个顶点的度数≥３ deg( ) 2 2( 1) 1 = = + = v e n n i i 2 1 2 2( 1) = + + n n n
§1图的基本概念 《推论》: (1)在图中,所有度数之和必为偶数 (2)在图中,度数为奇数的结点必定有偶数个
§1图的基本概念 《推论》： (1)在图中，所有度数之和必为偶数； (2)在图中，度数为奇数的结点必定有偶数个