边:不带箭头的联线,表示对称关系。 弧:带箭头的联线,表示不对称关系。 无向图:简称图,有点和边组成。 表示为:G=(V,E) V-点集合E-边集合 例:右图 V={v1,v2,v3,V4 E={el,e2,,e7} el=lvl, v2]e2=vl, v2I ,e7=v4,v4] 脑O2
运筹学 边：不带箭头的联线，表示对称关系。 弧：带箭头的联线，表示不对称关系。 无向图：简称图，有点和边组成。 表示为： G=（V，E） V--点集合 E--边集合 例：右图 V={v1，v2，v3，v4} E={e1，e2，…,e7} e1=[v1,v2]e2=[v1,v2], …,e7=[v4,v4] v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7
有向图:由点和弧组成。表示为 D=(VA V-点集合A-孤集合 点数p(G)或p(D) 边数:q(G) 弧数:q(D) VI v4 例:右图 V={vl,v22,V5} v3 Afal, a2,..., a7) al={v1,v5},a2={v5,V4}2a7={vl,v4
运筹学 有向图：由点和弧组成。表示为： D=（V，A） V--点集合 A--弧集合 点数: p(G) 或 p(D) 边数: q(G) 弧数:q(D) v1 v2 v3 v4 v5 例：右图 V={v1，v2,…,v5} A={a1，a2,…,a7} a1={v1,v5},a2={v5,v4},…,a7={v1,v4}
无向图的有关概念 端点:e=[uv∈E则uV是e的端点称 uv相邻 关联边:e是点uv的关联边 环:若u=ve是环 多重边:两点之间多于一条边 简单图:无环无多重边的图 多重图:无环允许有多重边的图 □合
运筹学 无向图的有关概念 端点: e=[u,v]∈E, 则u,v是e的端点, 称 u,v相邻. 关联边: e是点u,v的关联边. 环: 若u=v, e是环. 多重边: 两点之间多于一条边. 简单图: 无环,无多重边的图. 多重图: 无环,允许有多重边的图
次:以点v为端点的边的个数称为v的次 表示为:dv) 悬挂点次为1的点 悬挂边:悬挂点的关联边 孤立点:次为0的点 奇点次为奇数的点 偶点:次为偶数的点 悬挂边 d(v)=4,d(v2)=3 孤立点
运筹学 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 v5 次: 以点v为端点的边的个数称为v的次. 表示为: d(v) 悬挂点: 次为1的点. 悬挂边: 悬挂点的关联边. 孤立点: 次为0的点. 奇点: 次为奇数的点. 偶点: 次为偶数的点. 孤立点 悬挂边 d(v1 ) = 4,d(v2 ) = 3
定理1:图G=(V,E)中所有点的次之和是 边数的两倍,即 ∑d()=2q v∈ 定理2:任意一图中,奇点的个数为偶数 证明;设v1-奇点的集合, V2-偶点的集合 ∑d()+∑4(v)=∑d()=2q v∈I v∈2 v∈ 偶数 偶数 偶数
运筹学 定理1: 图G=(V,E)中,所有点的次之和是 边数的两倍, 即: 定理2: 任意一图中, 奇点的个数为偶数. 证明:设 V1--奇点的集合, V2--偶点的集合 d v q v V ( ) = 2 d v d v d v q v V v V v V ( ) ( ) ( ) 2 1 2 + = = 偶数 偶数 偶数