s1图的基本概念 《定理》每个图中,结点度数的总和等于边 数的两eg)=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+ 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)在图中，度数为奇数的结点必定有偶数个
§1图的基本概念 《定理》:在任何有向图中,所有结点的入度之 和等于所有结点的出度之和
§1图的基本概念 《定理》：在任何有向图中，所有结点的入度之 和等于所有结点的出度之和
§1图的基本概念 2.子图和图的同构: 《定义》:设G=<V,E>,G’=<V’,E’> 是二个图 若V’∝V,E’E,则称G’是G的子图; 若V’cV或E’cE,则称G’是G的真子图; 若V 支 例:
§1图的基本概念 ２．子图和图的同构： 《定义》：设Ｇ＝<Ｖ，Ｅ>，Ｇ’＝<Ｖ’，Ｅ’> 是二个图 若Ｖ’Ｖ，Ｅ’Ｅ,则称Ｇ’是Ｇ的子图； 若Ｖ’Ｖ或Ｅ’Ｅ,则称Ｇ’是Ｇ的真子图； 若Ｖ’＝Ｖ，Ｅ’Ｅ,则称Ｇ’是Ｇ的生成子图(支 撑子图)。 例：Ｇ图如下：Ｇ的真子图： 支撑子图：