二、常用名词: 端点和关联边: 若e=(v,)∈E则称点v、v是边e的端点, 边e是点v和v的关联边 2、相邻点和相邻边: 条边的两个端点称为相邻点,简称邻点, 端点落在同一个顶点的边称为相邻边,简称邻边 3、多重边与环: 具有相同端点的边称为多重边或平行边; 两个端点落在同一个顶点的边称为环 4、多重图和简单图: 含有多重边的图称为多重图 无环也无多重边的图称为简单图
二、常用名词： • • • • 1 v 2 v 3 v 4 v 1 e 2 e 3 e 4 e 5 e 6 e 1、端点和关联边： ( ) 边 是点 和 的关联边 若 则称点 、 是边 的端点， k i j k i j i j k e v v e = v ,v E, v v e 2、相邻点和相邻边： 端点落在同一个顶点的边称为相邻边，简称邻边 一条边的两个端点称为相邻点，简称邻点， 3、多重边与环： 两个端点落在同一个顶点的边称为环。 具有相同端点的边称为多重边或平行边； 4、多重图和简单图： 无环也无多重边的图称为简单图。 含有多重边的图称为多重图； 1 e 4 e
5、次:以点v为端点的边的条数称为点v的次,d(v) 6、悬挂点和悬挂边: 次为的点称为悬挂点,与悬挂点相联的边称为悬挂边 7、孤立点:次为的点称为孤立点 8、奇点与偶点: 次为奇数的点称为奇点,次为偶数的点称为偶点 d(v1)=3,d(V2)=1,d(v3)=4 v为悬挂点,e2为悬挂边 vs为孤立点, Vv2、v4、v为奇点,、v为偶点 ∑d(v)=12,G的边数m=6 即∑d(V)=2m
5、次： ( ) i i i 以点v 为端点的边的条数称为点v 的次，d v 6、悬挂点和悬挂边： 7、孤立点： 8、奇点与偶点： ( ) 3, d v1 = 次为1的点称为悬挂点，与悬挂点相联的边称为悬挂边。 v2 、v6 为悬挂点，e2、e5为悬挂边， 次为0的点称为孤立点 v5为孤立点， 次为奇数的点称为奇点，次为偶数的点称为偶点 • • • • 1 v 2 v 3 v 4 v 2 e 3 e 4 e 5 e 1 e 5 •v v6 • 6 e v1 、v2 、v4 、v6 为奇点，v5、v3为偶点 ( ) 4 d(v2 ) =1, d v3 = ( ) 3, d v4 = ( ) 0, d v5 = ( ) 1, d v6 = d(vi ) = 12 ，G的边数m=6 即 d(vi ) = 2m
三、次的性质 定理1在图G=(VE)中,所有点的次之和是边数m 的两倍。 证明:由于每条边均与两个顶点关联, 因此在计算顶点的次时每条边都计算了两遍 所以顶点次数的总和等于边数的二倍
定理1 在图G=(V,E)中，所有点的次之和是边数m 的两倍。 证明： 由于每条边均与两个顶点关联， 因此在计算顶点的次时每条边都计算了两遍 所以顶点次数的总和等于边 数的二倍。 三、次的性质
定理52在任何图G=(VE)中,奇点的个数为偶数 证明:设V和V2分别是图G中奇点和偶点的集合 则V∪V2=且V∩V2=Φ ∑a(v)=∑d(v)+∑d(v)=2m(定理51) V2是偶点的集合,(v)(∈V2)均为偶数 所以∑偶数→∑d(v)为偶数 i∈V1 而v是奇点的集合(v∈V)均为奇数 只有偶数个奇数相加才能得到偶数 所以V中的点,即奇点的个数为偶数
定理5.2 在任何图G=(V,E)中，奇点的个数为偶数 证明： 设V1 和V2 分别是图G中奇点和偶点的集合 则V1 V2 =V且V1 V2 = = + 1 2 ( ) ( ) ( ) i V i i V i i V i d v d v d v = 2m （定理5.1） V2 是偶点的集合,d(vi )(i V2 )均为偶数 所以 为偶数 2 ( ) i V i d v 为偶数 1 ( ) i V d vi 而V1 是奇点的集合,d(vi )(i V1 )均为奇数 只有偶数个奇数相加才能得到偶数 所以V1 中的点，即奇点的个数为偶数
四、链:对无向图G=(V,E) 1、链的定义:在图G=(V,E)中,一个点与边的交错序列 021121l2i2 ik-22ik-12ik-12ik2 且en=(vn1,vn)(t=12…k,则称这个点边序列为 连接vo与v的一条链,简记为={vo,n12…,vk2,vk1,vk 简单链:在链中,所含的边均不相同 初等链:在链中,所含的顶点、边均不相同 } 初等链 6:71c8:4 不是链 」简 单链 e. v.e.v.e.ve.veoy 连接v与v的一条链
1、链的定义： 连接 与 的一条链 且 则称这个点边序列为 在图 （ ， ）中，一个点与边的交错序列 i i k i t i t i t i i i i i k i k i k i k i k v v e v v t k v e v e v e v e v G V E 0 1 0 1 1 2 2 1 1 ( , )( 1,2, ), { , , , , , , , , }, = = = − − − − { , , , , , , , , , , }, 5 4 4 9 2 2 3 3 4 8 1 v e v e v e v e v e v { , , , , } 6 5 5 7 1 v e v e v { , , , , } 6 7 1 8 4 v e v e v •简单链：在链中，所含的边均不相同 •初等链： 简单链 链 四、链： , { , , , , } i0 i1 i k 2 i k 1 i k v v v v v 简记为 = ， − − 1 e 2 e 3 e 4 e 5 e 6 e • • • • 1 v 2 v 3 v 4 v 5 v 6 v • • 7 e 8 e 9 e 在链中，所含的顶点、边均不相同 连接v5 与v1 的一条链不是链 对无向图G =（V，E） 初等