物流网站免费模板,吉林省建设招标网站,免费情感网站哪个好,网站哪里备案408答疑 文章目录 一、图的基本概念图的定义非空性非线性结构 顶点和边的表示顶点边 有向图 无向图有向图有向图 G 1 G_1 G1 的表示 无向图无向图 G 2 G_2 G2 的表示 简单图 多重图简单图多重图 顶点的度、入度和出度顶点的度有向图的度 路径、路径长度和回路… 408答疑 文章目录 一、图的基本概念图的定义非空性非线性结构 顶点和边的表示顶点边 有向图 无向图有向图有向图 G 1 G_1 G1 的表示 无向图无向图 G 2 G_2 G2 的表示 简单图 多重图简单图多重图 顶点的度、入度和出度顶点的度有向图的度 路径、路径长度和回路距离子图完全图简单完全图无向完全图有向完全图 连通图、连通分量、强连通图强连通分量连通性连通图强连通图 连通分量强连通分量 生成树 生成森林生成树生成森林 边的权、网和带权路径长度边的权网带权路径长度 稠密图 稀疏图稀疏图稠密图 有向树 六、参考资料鲍鱼科技课件26王道考研书 一、图的基本概念
图的定义
图 G G G 由顶点集 V V V 和边集 E E E 组成记为 G ( V , E ) G (V, E) G(V,E)其中 V ( G ) V(G) V(G) 表示图 G G G 中顶点的有限非空集 E ( G ) E(G) E(G) 表示图 G G G 中顶点之间的关系边集合。
非空性
线性表可以是空表树可以是空树但图不可以是空图。也就是说图中不能一个顶点也没有图的顶点集 V V V 一定非空但边集 E E E 可以为空此时图中只有顶点而没有边。
非线性结构
图是非线性结构由顶点和边组成。
顶点和边的表示
若 V { v 1 , v 2 , ⋯ , v n } V \{v_1, v_2, \cdots, v_n\} V{v1,v2,⋯,vn}则用 ∣ V ∣ |V| ∣V∣ 表示图 G G G 中顶点的个数。边集 E { ( u , v ) ∣ u ∈ V , v ∈ V } E \{(u, v) | u \in V, v \in V\} E{(u,v)∣u∈V,v∈V}用 ∣ E ∣ |E| ∣E∣ 表示图 G G G 中边的条数。
顶点
图中的结点称为顶点。
边
连接顶点之间的线称为边。 无向边简称为边。有向边称为弧。
有向图 无向图
有向图
有向图的边使用尖括号 ⟨ ⟩ \langle \rangle ⟨⟩ 表示。弧是顶点的有序对记为 ⟨ v , w ⟩ \langle v, w \rangle ⟨v,w⟩其中 v , w v, w v,w 是顶点 v v v 称为弧尾 w w w 称为弧头。 ⟨ v , w ⟩ \langle v, w \rangle ⟨v,w⟩ 称为从 v v v 到 w w w 的弧也称 v v v 邻接到 w w w。
有向图 G 1 G_1 G1 的表示 G 1 ( V 1 , E 1 ) G_1 (V_1, E_1) G1(V1,E1) V 1 { 1 , 2 , 3 } V_1 \{1, 2, 3\} V1{1,2,3} E 1 { ⟨ 1 , 2 ⟩ , ⟨ 2 , 1 ⟩ , ⟨ 2 , 3 ⟩ } E_1 \{\langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 2, 3 \rangle\} E1{⟨1,2⟩,⟨2,1⟩,⟨2,3⟩} 无向图
无向图的边使用圆括号 ( ) ( ) () 表示。边是顶点的无序对记为 ( v , w ) (v, w) (v,w) 或 ( w , v ) (w, v) (w,v)。可以说 w w w 和 v v v 互为邻接点。边 ( v , w ) (v, w) (v,w) 依附于 w w w 和 v v v或称边 ( v , w ) (v, w) (v,w) 和 v , w v, w v,w 相关联。
无向图 G 2 G_2 G2 的表示 G 2 ( V 2 , E 2 ) G_2 (V_2, E_2) G2(V2,E2) V 2 { 1 , 2 , 3 , 4 } V_2 \{1, 2, 3, 4\} V2{1,2,3,4} E 2 { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } E_2 \{(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\} E2{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} 简单图 多重图
简单图
不存在重复边。不存在顶点到自身的边。 多重图
允许两个顶点之间的边数大于 1 条。允许顶点通过一条边和自身关联。 顶点的度、入度和出度
顶点的度
连接顶点边的数量称为顶点的度记为 T D ( v ) TD(v) TD(v)。在无向图中每条边和两个顶点相关联因此无向图的全部顶点的度之和等于边数的 2 倍。在下图中每个顶点的度均为 3。 有向图的度
对于有向图顶点 v v v 的度分为入度和出度。 入度以顶点 v v v 为终点的有向边的数目记为 I D ( v ) ID(v) ID(v)。出度以顶点 v v v 为起点的有向边的数目记为 O D ( v ) OD(v) OD(v)。 顶点 v v v 的度等于其入度与出度之和即 T D ( v ) I D ( v ) O D ( v ) TD(v) ID(v) OD(v) TD(v)ID(v)OD(v)。有向图的全部顶点的入度之和与出度之和相等并且等于边数这是因为每条有向边都有一个起点和终点。
路径、路径长度和回路 路径 顶点 v p v_p vp 到顶点 v q v_q vq 之间的一条路径是指顶点序列 v p , v i 1 , v i 2 , ⋯ , v i m , v q v_p, v_{i_1}, v_{i_2}, \cdots, v_{i_m}, v_q vp,vi1,vi2,⋯,vim,vq。路径上的边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 n n n 个顶点且有大于 n − 1 n-1 n−1 条边则此图一定有环。 简单路径 在路径序列中顶点不重复出现的路径称为简单路径。 简单回路 除第一个顶点和最后一个顶点外其余顶点不重复出现的回路称为简单回路。
距离
从顶点 u u u 出发到顶点 v v v 的最短路径若存在则此路径的长度称为从 u u u 到 v v v 的距离。若从 u u u 到 v v v 根本不存在路径则记该距离为无穷 ∞ \infty ∞。
子图
设有两个图 G ( V , E ) G (V, E) G(V,E) 和 G ′ ( V ′ , E ′ ) G (V, E) G′(V′,E′)若 V ′ V V′ 是 V V V 的子集且 E ′ E E′ 是 E E E 的子集则称 G ′ G G′ 是 G G G 的子图。若有满足 V ( G ′ ) V ( G ) V(G) V(G) V(G′)V(G) 的子图 G ′ G G′则称其为 G G G 的生成子图。注意并非 V V V 和 E E E 的任何子集都能构成 G G G 的子图因为这样的子集可能不是图即 E E E 的子集中的某些边关联的顶点可能不在这个 V V V 的子集中。下图中(2)为(1)的子图。 完全图简单完全图
无向完全图
对于无向图边的取值范围为 0 0 0 到 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1)。如果图有 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1) 条边则无向图称为无向完全图。在完全图中任意两个顶点之间都存在边。 有向完全图
对于有向图边的取值范围为 0 0 0 到 n ( n − 1 ) n(n-1) n(n−1)。如果图有 n ( n − 1 ) n(n-1) n(n−1) 条弧则有向图称为有向完全图。在有向完全图中任意两个顶点之间都存在方向相反的两条弧。 连通图、连通分量、强连通图强连通分量
连通性
连通图
在无向图中若从顶点 v v v 到顶点 w w w 有路径存在则称 v v v 和 w w w 是连通的。若图 G G G 中任意两个顶点都是连通的则称图 G G G 为连通图否则称为非连通图。
强连通图
在有向图中若有一对顶点 v v v 和 w w w从 v v v 到 w w w 和从 w w w 到 v v v 之间都有路径则称这两个顶点是强连通的。若图中任意一对顶点都是强连通的则称此图为强连通图。 连通分量
无向图中的极大连通子图称为连通分量。在下图中图 G G G 有 3 个连通分量。假设一个图有 n n n 个顶点若边数小于 n − 1 n-1 n−1则此图必是非连通图。 若该图是非连通图非连通情况下边最多的情况由 n-1 个顶点构成一个完全图此时再加入一个顶点则变成非连通图。 强连通分量
有向图中的极大强连通子图称为有向图的强连通分量。在下图中图 G G G 有 2 个连通分量。假设一个有向图有 n n n 个顶点若该图是强连通图则连通情况下边最少的情况至少需要 n 条边构成一个环路。 注意在无向图中讨论连通性在有向图中讨论强连通性
生成树 生成森林
生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n n n则它的生成树含有 n − 1 n-1 n−1 条边。包含图中全部顶点的极小连通子图只有生成树满足这个极小条件对生成树而言若砍去它的一条边则会变成非连通图若加上一条边则会形成一个回路。 生成森林
非连通图中连通分量的生成树构成了非连通图的生成森林。
注意区分极大连通子图和极小连通子图。极大连通子图要求子图必须连通而且包含尽可能多的顶点和边极小连通子图是既要保持子图连通又要使得边数最少的子图。
边的权、网和带权路径长度
边的权
在一个图中每条边都可以标上具有某种含义的数值该数值称为该边的权值。
网
这种边上带有权值的图称为带权图也称网。
带权路径长度
路径上所有边的权值之和称为该路径的带权路径长度。
稠密图 稀疏图
稀疏图
边数很少的图称为稀疏图。稀疏和稠密本身是模糊的概念稀疏图和稠密图常常是相对而言的。一般当图 G G G 满足 ∣ E ∣ ∣ V ∣ log 2 ∣ V ∣ |E| |V|\log_2|V| ∣E∣∣V∣log2∣V∣ 时可以将 G G G 视为稀疏图。
稠密图
反之称为稠密图。
有向树
一个顶点的入度为 0 0 0、其余顶点的入度均为 1 1 1 的有向图称为有向树。
六、参考资料
鲍鱼科技课件
b站免费王道课后题讲解: link
网课全程班: link
26王道考研书
