顶点和边 顶点通过边邻接,边依附于顶点 不考虑顶点到自身有边的情况 n个顶点的有向图,最大边数为n(n-1) n个顶点的无向图,最大边数为n(n-1)/2 达到最大边数的图称为完全( complete)图,边数 接近完全的图称为稠密( dense)图,边数远小于完 全的图称为稀疏( sparse)图 每个顶点所关联的边的数目称为度( degree) 有向图中又分为入度( indegree)和出度( outdegree) 顶点的度和图的边数满足e=∑=1D(v) 2021/2/11 数据结构及其算法第7章图
•顶点和边 •顶点通过边邻接，边依附于顶点 •不考虑顶点到自身有边的情况 • n个顶点的有向图，最大边数为n(n-1) • n个顶点的无向图，最大边数为n(n-1)/2 •达到最大边数的图称为完全(complete)图，边数 接近完全的图称为稠密(dense)图，边数远小于完 全的图称为稀疏(sparse)图 •每个顶点所关联的边的数目称为度(degree) • 有向图中又分为入度(indegree)和出度(outdegree) •顶点的度和图的边数满足𝑒 = 1 2 σ𝑖=1 𝑛 𝐷(𝑣𝑖 ) 2021/2/11 数据结构及其算法 第7章 图 7
例 顶点数:4 边数:4 V1的入度1,出度2 V4的入度1,出度1 柯尼斯堡七桥问题无解, 顶点数:5 因为顶点的度都是奇数 边数:6 V1的度2 V4的度2 2021/2/11 数据结构及其算法第7章图
•例 2021/2/11 数据结构及其算法 第7章 图 8 顶点数：4 边数：4 V1的入度1，出度2 V4的入度1，出度1 顶点数：5 边数：6 V1的度2 V4的度2 柯尼斯堡七桥问题无解， 因为顶点的度都是奇数
子图( subgraph) .g=(,Ei G=(v,ei VCv,Ece yih (a) 2021/2/11 数据结构及其算法第7章图
•子图(subgraph) •𝐺 = (𝑉, 𝐸); 𝐺 ′ = (𝑉 ′ ,𝐸′); 𝑉 ′ ⊆ 𝑉, 𝐸′ ⊆ 𝐸 2021/2/11 数据结构及其算法 第7章 图 9
路径和连通 路径(path):图中两顶点(ⅴ,v′)之间的路径是 个顶点序列,序列的首元为v,末元为v′,序列中 后两元之间的边在图中存在 路径的长度是路径中的边的数目 ⅴ=v′的路径称为回路或环( cycle 序列中顶点无重复的路径称为简单路 连通:若路径(ⅴ,v)存在,则称ⅴ与v′连通 任意两个顶点均连通的无向图称为连通图 任意一对顶点均连通的有向图称为强连通图 2021/2/11 数据结构及其算法第7章图 10
•路径和连通 •路径(path)：图中两顶点(v,v’)之间的路径是一 个顶点序列，序列的首元为v，末元为v’，序列中 前后两元之间的边在图中存在 • 路径的长度是路径中的边的数目 • v=v’的路径称为回路或环(cycle) • 序列中顶点无重复的路径称为简单路径 •连通：若路径(v,v’)存在，则称v与v’连通 •任意两个顶点均连通的无向图称为连通图 •任意一对顶点均连通的有向图称为强连通图 2021/2/11 数据结构及其算法 第7章 图 10
例 (Ⅵ1,V3,V4,Ⅵ1,V2)是一条路径, 长度为4 不是简单路径(V1重复) (V1,V3,V4,V1)是一条简单环 不是强连通图 (Ⅵ1,V2,V3,5)是一条路径, ④长度为3, 是简单路径 (V2,v3,V5,V2)是一条简单环 是连通图 2021/2/11 数据结构及其算法第7章图 11
•例 2021/2/11 数据结构及其算法 第7章 图 11 (V1,V3,V4,V1,V2)是一条路径， 长度为4， 不是简单路径(V1重复) (V1,V3,V4,V1)是一条简单环 不是强连通图 (V1,V2,V3,V5)是一条路径， 长度为3， 是简单路径 (V2,V3,V5,V2)是一条简单环 是连通图