1.图的基本概念例1：铁路交通图例2：球队比赛图点：表示研究对象连线：表示两个对象之间的某种特定关系。关系的对称性：两对象之间的关系可互换
1.图的基本概念 例 1: 铁路交通图 例 2: 球队比赛图 点: 表示研究对象. 连线：表示两个对象之间的某种特定关系。 关系的对称性：两对象之间的关系可互换
边：不带箭头的联线，表示对称关系。弧：带箭头的联线，表示不对称关系。无向图：简称图，由点和边组成。表示为：G=（V，E)eV一点集合E一边集合ViV2eo例：右图e6V={Vi, V2, V3, V4]ese3E={ej, e2, ...,ef]Vee1=[V1,V2] e2=[Vi, V2],23en..,e,=[v4, 4]
边：不带箭头的联线，表示对称关系。 弧：带箭头的联线，表示不对称关系。 无向图：简称图，由点和边组成。 表示为： 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= (V, A)其中：V--点集合A--弧集合点数: p(G)或 p(D)边数: q(G)V弧数: q(D)例：右图V=-{Vi, V2...,Vs]1A=a1. a2....a7]ai={V1,Vs], a2={Vs,V4],..., a,={V1,V4]
例：右图 V={v1，v2 ,.,v5 } A={a1，a2 ,.,a7 } a1={v1 ,v5 }, a2={v5 ,v4 },., a7={v1 ,v4 } 有向图：由点和弧组成。表示为： D =（V，A） 其中：V-点集合 A-弧集合 点数: p(G) 或 p(D) 边数: q(G) 弧数: q(D) v1 v2 v3 v4 v5
无向图的有关概念端点：e=[u,]eE,则u,v是e的端点,称u,vV相邻。关联边：e是点u,v的关联边环：若u=v,e是环多重边：两点之间多于一条边简单图：无环无多重边的图多重图：无环允许有多重边的图
无向图的有关概念 端点: e=[u,v] E, 则u,v是e的端点, 称u,v 相邻. 关联边: e是点u,v的关联边. 环: 若u=v, e是环. 多重边: 两点之间多于一条边. 简单图: 无环,无多重边的图. 多重图: 无环,允许有多重边的图
次：以点v为端点的边的个数称为v的次表示为: d(v)悬挂点：次为1的点。悬挂边：悬挂点的关联边孤立点：次为0的点。e奇点：次为奇数的点悬挂边偶点：次为偶数的点VV4d(v) = 4,d(v2) = 3e6V孤立点e5V
v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 v5 次: 以点v为端点的边的个数称为v的次. 表示为: d(v) 悬挂点: 次为1的点. 悬挂边: 悬挂点的关联边. 孤立点: 次为0的点. 奇点: 次为奇数的点. 偶点: 次为偶数的点. 孤立点 悬挂边 d(v ) 4,d(v ) 3 1 2