§71图的基本概念 G2=<V2,E2> V2={vov1,2,v3 E2={<vo,v1>,<vo,v2>,<v2,V3>,<v3,vo) 有序对<v;,v;>: V2) V3 用以为v;起点、以v;为终点 的有向线段表示,称为有向 G2图示 边或弧; 无向图:在图G中,若所有边是无向边,则称G为无向图; 有向图:在图G中,若所有边是有向边,则称G为有向图; 混和图:在图G中,即有无向边也有有向边,则称G为混合图;
G2 图示 有序对<vi,vj> ： 用以为vi起点、以vj为终点 的有向线段表示，称为有向 边或弧； 无向图：在图G中，若所有边是无向边，则称G为无向图； 有向图：在图G中，若所有边是有向边，则称G为有向图； 混和图：在图G中，即有无向边也有有向边，则称G为混合图； §7.1 图的基本概念 V0 V1 V2 V3 G2=<V2,E2> V2={v0 v1,v2,v3} E2={<v0,v1 > , <v0,v2 >, <v2,v3 >,<v3,v0 >}
§71图的基本概念 二图的应用举例 例1交通图(公路、铁路) 顶点:地点 边:连接地点的公路 交通图中的有单行道双行道,分别用有向边、无向边表示; 例2电路图 顶点:元件 VO 边:连接元件之间的线路 例3通讯线路图 (v2 顶点:地点 V3 边:地点间的连线 例4各种流程图 如产品的生产流程图 顶点:工序 边:各道工序之间的顺序关系 V
二 图的应用举例 例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示； 例2 电路图 顶点：元件 边：连接元件之间的线路 例3 通讯线路图 顶点：地点 边：地点间的连线 例4 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系 §7.1 图的基本概念 V0 V3 V4 V1 V2 V0 V1 V2 V3
§71图的基本概念 图的基本术语 1邻接点及关联边 邻接点:边的两个顶点 关联边:若边e=(v,u),则称顶点v、u关连边e 2顶点的度、入度、出度 V3) V4) 顶点V的度=与V相关联的边的数目 在有向图中: 顶点V的出度=以V为起点有向边数 顶点V的入度=以V为终点有向边数 顶点V的度=V的出度+V的入度 设图G的顶点数为n,边数为e 图的所有顶点的度数和=2*e V3) (每条边对图的所有顶点的度数和“贡献”2度)
1 邻接点及关联边 邻接点：边的两个顶点 关联边：若边e= (v, u), 则称顶点v、u 关连边e 2 顶点的度、入度、出度 顶点V的度 = 与V相关联的边的数目 在有向图中： 顶点V的出度=以V为起点有向边数 顶点V的入度=以V为终点有向边数 顶点V的度= V的出度+V的入度 设图G的顶点数为n，边数为e 图的所有顶点的度数和 = 2*e （每条边对图的所有顶点的度数和“贡献”2度） e 三 图的基本术语 §7.1 图的基本概念 V0 V3 V4 V1 V2 V0 V1 V2 V3
§71图的基本概念 3路径、回路 无向图G=(V,E)中的顶点序列v1,V2,,Ⅴk,若 (vi,vi+1)∈E(i=1,2,…kx-1),ⅴ=v1,u=vk,则称该序列是 从顶点v到顶点u的路径;若v=u,则称该序列为回路 有向图D=(V,E)中的顶点序列v1,v2,…,vk,若 <vi,vi+1>∈E(i=1,2,…kx-1),ⅴ=v1,u=vk,则称该序列是 从顶点v到顶点u的路径;若v=u,则称该序列为回路; 例 在图1中,V0,Ⅵ1,V2,V3是V0到V3的路径;V0,V1,V2,V3,V0是回 路;在图2中,V0,V2,V3是V0到V3的路径;VO,V2,V3,V0是回 路 无向图G1 V2 有向图G2 V3) V3
3 路径、回路 无向图G=（V，E）中的顶点序列v1,v2,… ,vk,若 (vi,vi+1)E( i=1,2,…k-1), v =v1, u =vk, 则称该序列是 从顶点v到顶点u的路径；若v=u，则称该序列为回路； 有向图D=（V，E）中的顶点序列v1,v2,… ,vk, 若 <vi,vi+1>E (i=1,2,…k-1), v =v1, u =vk, 则称该序列是 从顶点v到顶点u的路径；若v=u，则称该序列为回路； 在图1中，V0,V1,V2,V3 是V0到V3的路径； V0,V1,V2,V3,V0是回 路；在图2中，V0,V2,V3 是V0到V3的路径； V0,V2,V3,V0是回 路； 无向图G1 有向图G2 例 §7.1 图的基本概念 V0 V3 V4 V1 V2 V0 V1 V2 V3
§71图的基本概念 3简单路径和简单回路 在一条路径中,若除起点和终点外,所有顶点各不相同,则称 该路径为简单路径; 由简单路径组成的回路称为简单回路; 例 在图1中,V0,Ⅵ1,V2,V3是简单路径;V0,V1,V2,V4,Ⅵ不是 简单路径;在图2中,V0,V2,V3,V0是简单回路; VO 无向图G1 有向图G2 V3) V3
3 简单路径和简单回路 在一条路径中,若除起点和终点外,所有顶点各不相同,则称 该路径为简单路径； 由简单路径组成的回路称为简单回路； 在图1中，V0,V1,V2,V3 是简单路径； V0,V1,V2,V4,V1不是 简单路径；在图2中， V0,V2,V3,V0是简单回路； 无向图G1 有向图G2 例 §7.1 图的基本概念 V0 V3 V4 V1 V2 V0 V1 V2 V3