杭州免费建站,wordpress局域网无法访问,广州手机网站定制如何,秦皇岛网站优化图论1
图论 (Graph theory) 是数学的一个分支#xff0c;图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形#xff0c;这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物#xff0c;连接两顶点的边则用于表示两个事物…图论1
图论 (Graph theory) 是数学的一个分支图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物连接两顶点的边则用于表示两个事物间具有这种关系。
1、图的理论基础
图Graph
用大写字母如 G G G表示图通常记为 G ( V , E ) G(V,E) G(V,E)其中 V V V 表示顶点集 E E E 表示边集。例如设 G ( V , E ) G(V,E) G(V,E) 是一个无向图 V V V 包含多个顶点 E E E 包含连接这些顶点的边。
相邻Adjacent
若顶点 u u u 和 v v v 相邻可表示为 u ∼ v u \sim v u∼v。例如在图 G G G 中若顶点 u u u 和 v v v 之间有边相连则有 u ∼ v u \sim v u∼v。
简单图Simple Graph
设 G ( V , E ) G(V,E) G(V,E) 为简单图特点是不存在自环即不存在边 e ( u , u ) e(u,u) e(u,u) u ∈ V u\in V u∈V和多重边任意两顶点间不存在多条相同边可描述为 G ( V , E ) G(V,E) G(V,E) 是简单图满足无自环与多重边条件。
度数Degree 无向图中顶点度数无向图里顶点 v v v 的度数用 deg ( v ) \deg(v) deg(v) 表示比如在无向图 G G G 中顶点 v v v 的度数记为 deg ( v ) \deg(v) deg(v)其值等于与 v v v 相连的边的数量。 有向图中顶点度数有向图中顶点 v v v 的入度表示为 indeg ( v ) \text{indeg}(v) indeg(v)出度表示为 outdeg ( v ) \text{outdeg}(v) outdeg(v)。例如在有向图 G G G 中顶点 v v v 的入度为 indeg ( v ) \text{indeg}(v) indeg(v)出度为 outdeg ( v ) \text{outdeg}(v) outdeg(v)度数可结合二者考量。
路径Path
用 P ( v 0 , v 1 , ⋯ , v n ) P(v_0,v_1,\cdots,v_n) P(v0,v1,⋯,vn) 表示从顶点 v 0 v_0 v0 出发依次经过 v 1 , ⋯ , v n v_1,\cdots,v_n v1,⋯,vn 这些顶点的路径。例如在图 G G G 中存在路径 P ( v 1 , v 2 , v 3 ) P(v_1,v_2,v_3) P(v1,v2,v3)即从顶点 v 1 v_1 v1 出发依次经过 v 2 v_2 v2 和 v 3 v_3 v3 的路线。
子图Subgraph
设 $G(V,E)$ 是原图$G(V,E)$ 是它的子图关系表示为$V\subseteq V$ 且 $E\subseteq E$同时 $E$ 中边的端点都在 $V$ 中则 $G(V,E)$ 为 $G$ 的子图。 比如已知图 G ( V , E ) G(V,E) G(V,E)取 V ′ V V′ 为 V V V 的部分顶点集 E ′ E E′ 为相应连接这些顶点的部分边集满足条件后 G ′ ( V ′ , E ′ ) G(V,E) G′(V′,E′) 就是 G G G 的子图。
连通Connected 无向图连通设 G ( V , E ) G(V,E) G(V,E) 为无向图若对任意 u , v ∈ V u,v\in V u,v∈V都存在一条路径连接 u u u 和 v v v则称 G G G 是连通的可写成 ∀ u , v ∈ V \forall u,v\in V ∀u,v∈V存在路径连接 u u u 与 v v v则 G G G 连通。 有向图连通相关强连通和弱连通 强连通对于有向图 G ( V , E ) G(V,E) G(V,E)若对任意 u , v ∈ V u,v\in V u,v∈V都存在从 u u u 到 v v v 的有向路径以及从 v v v 到 u u u 的有向路径则 G G G 是强连通的即 ∀ u , v ∈ V \forall u,v\in V ∀u,v∈V存在从 u u u 到 v v v 及从 v v v 到 u u u 的有向路径则 G G G 强连通。 弱连通若把有向图 G ( V , E ) G(V,E) G(V,E) 的边看作无向边时图是连通的则 G G G 是弱连通的表示为将有向图 G ( V , E ) G(V,E) G(V,E) 的边视为无向边时图连通则 G G G 弱连通。
无向图Undirected Graph
直接用 $G(V,E)$ 表示无向图并说明其边无方向特点。 如 G ( V , E ) G(V,E) G(V,E) 为无向图其边没有方向即对边 e ( u , v ) ∈ E e(u,v)\in E e(u,v)∈E u u u 与 v v v 的关系是对称的。
有向图Directed Graph
用 G ( V , E ) G(V,E) G(V,E) 表示有向图强调边有方向。
例如 G ( V , E ) G(V,E) G(V,E) 为有向图边 e ( u , v ) ∈ E e(u,v)\in E e(u,v)∈E 有方向从 u u u 指向 v v v表示一种单向关系。
割Cut 边割针对无向图设 G ( V , E ) G(V,E) G(V,E) 是连通无向图若存在边子集 E ′ ⊆ E E\subseteq E E′⊆E去掉 E ′ E E′ 后使得图不再连通则 E ′ E E′ 是 G G G 的一个边割可表示为 G ( V , E ) G(V,E) G(V,E) 连通无向图 ∃ E ′ ⊆ E \exists E\subseteq E ∃E′⊆E去掉 E ′ E E′ 后 G G G 不连通则 E ′ E E′ 为 G G G 的边割。 点割针对无向图对于连通无向图 G ( V , E ) G(V,E) G(V,E)若存在顶点子集 V ′ ⊆ V V\subseteq V V′⊆V去掉 V ′ V V′ 以及和这些顶点相关联的边后使得图不再连通则 V ′ V V′ 是 G G G 的一个点割写成 G ( V , E ) G(V,E) G(V,E) 连通无向图 ∃ V ′ ⊆ V \exists V\subseteq V ∃V′⊆V去掉 V ′ V V′ 及相关边后 G G G 不连通则 V ′ V V′ 为 G G G 的点割。
稀疏图/稠密图Sparse Graph / Dense Graph 稀疏图对于图 G ( V , E ) G(V,E) G(V,E)若 ∣ E ∣ ≪ ∣ V ∣ 2 |E| \ll |V|^2 ∣E∣≪∣V∣2这里 ≪ \ll ≪ 示意边数量远小于顶点数量平方的大概关系则 G G G 为稀疏图如 G ( V , E ) G(V,E) G(V,E)当 ∣ E ∣ ≪ ∣ V ∣ 2 |E| \ll |V|^2 ∣E∣≪∣V∣2 时 G G G 为稀疏图。 稠密图与稀疏图对应若 ∣ E ∣ |E| ∣E∣ 接近 ∣ V ∣ 2 |V|^2 ∣V∣2 量级可写成 G ( V , E ) G(V,E) G(V,E)当 ∣ E ∣ |E| ∣E∣ 接近 ∣ V ∣ 2 |V|^2 ∣V∣2 时 G G G 为稠密图。
补图Complement Graph
设 G ( V , E ) G(V,E) G(V,E) 是无向简单图其补图 G ‾ ( V , E ‾ ) \overline{G}(V,\overline{E}) G(V,E)其中 E ‾ \overline{E} E 包含了所有不在 E E E 中但两端点在 V V V 中的边可表示为 G ( V , E ) G(V,E) G(V,E) 为无向简单图其补图 G ‾ ( V , E ‾ ) \overline{G}(V,\overline{E}) G(V,E) E ‾ { ( u , v ) ∣ u , v ∈ V , ( u , v ) ∉ E } \overline{E}\{(u,v)\mid u,v\in V,(u,v)\notin E\} E{(u,v)∣u,v∈V,(u,v)∈/E}。
反图Inverse Graph
对于有向图 G ( V , E ) G(V,E) G(V,E)其反图 G − 1 ( V , E − 1 ) G^{-1}(V,E^{-1}) G−1(V,E−1)这里 E − 1 E^{-1} E−1 是把 E E E 中每条边的方向都反转所得到的边集写成 G ( V , E ) G(V,E) G(V,E) 为有向图其反图 G − 1 ( V , E − 1 ) G^{-1}(V,E^{-1}) G−1(V,E−1) E − 1 { ( v , u ) ∣ ( u , v ) ∈ E } E^{-1}\{(v,u)\mid (u,v)\in E\} E−1{(v,u)∣(u,v)∈E}。
特殊的图
完全图Complete Graph
无向完全图用 K n K_n Kn 表示 n n n 个顶点的无向完全图其边数为 n ( n − 1 ) 2 \frac{n(n - 1)}{2} 2n(n−1)。例如 K 5 K_5 K5 是有 5 5 5 个顶点的无向完全图边数为 5 × ( 5 − 1 ) 2 10 \frac{5\times(5 - 1)}{2}10 25×(5−1)10。有向完全图用 D n D_n Dn 表示 n n n 个顶点的有向完全图其边数为 n ( n − 1 ) n(n - 1) n(n−1)。树Tree树可描述为无向连通且无环的图记为 T ( V , E ) T(V,E) T(V,E) 为树即 T T T 是无向连通且无环的图。二分图Bipartite Graph设顶点集 V V V 可分成两个互不相交的子集 V 1 V_1 V1 和 V 2 V_2 V2使图中每条边的两个端点分别属于 V 1 V_1 V1 和 V 2 V_2 V2可写成 G ( V , E ) G(V,E) G(V,E) 为二分图 ∃ V 1 , V 2 ⊆ V \exists V_1,V_2\subseteq V ∃V1,V2⊆V V 1 ∩ V 2 ∅ V_1\cap V_2\varnothing V1∩V2∅且 ∀ e ( u , v ) ∈ E \forall e(u,v)\in E ∀e(u,v)∈E u ∈ V 1 u\in V_1 u∈V1 且 v ∈ V 2 v\in V_2 v∈V2 或 u ∈ V 2 u\in V_2 u∈V2 且 v ∈ V 1 v\in V_1 v∈V1。
同构Isomorphism
设 G ( V , E ) G(V,E) G(V,E) 和 G ′ ( V ′ , E ′ ) G(V,E) G′(V′,E′) 是两个图若存在双射函数 f : V → V ′ f: V \to V f:V→V′使得对于任意的 u , v ∈ V u,v \in V u,v∈V ( u , v ) ∈ E (u,v) \in E (u,v)∈E 当且仅当 ( f ( u ) , f ( v ) ) ∈ E ′ (f(u),f(v)) \in E (f(u),f(v))∈E′则称 G G G 和 G ′ G G′ 是同构的表示为 G ( V , E ) G(V,E) G(V,E) G ′ ( V ′ , E ′ ) G(V,E) G′(V′,E′)若 ∃ f : V → V ′ \exists f: V \to V ∃f:V→V′ 双射满足 ∀ u , v ∈ V \forall u,v\in V ∀u,v∈V ( u , v ) ∈ E ⇔ ( f ( u ) , f ( v ) ) ∈ E ′ (u,v)\in E \Leftrightarrow (f(u),f(v))\in E (u,v)∈E⇔(f(u),f(v))∈E′则 G G G 与 G ′ G G′ 同构。
无向简单图的二元运算
并运算Union设 G 1 ( V 1 , E 1 ) G_1(V_1,E_1) G1(V1,E1) 和 G 2 ( V 2 , E 2 ) G_2(V_2,E_2) G2(V2,E2) 是两个无向简单图它们的并 G 1 ∪ G 2 ( V 1 ∪ V 2 , E 1 ∪ E 2 ) G_1\cup G_2(V_1\cup V_2, E_1\cup E_2) G1∪G2(V1∪V2,E1∪E2)可写成 G 1 ( V 1 , E 1 ) G_1(V_1,E_1) G1(V1,E1) G 2 ( V 2 , E 2 ) G_2(V_2,E_2) G2(V2,E2)则 G 1 ∪ G 2 ( V 1 ∪ V 2 , E 1 ∪ E 2 ) G_1\cup G_2(V_1\cup V_2, E_1\cup E_2) G1∪G2(V1∪V2,E1∪E2)。例如已知 G 1 G_1 G1 和 G 2 G_2 G2 两个无向简单图计算它们的并图 G 1 ∪ G 2 G_1\cup G_2 G1∪G2。
交运算Intersection G 1 ∩ G 2 ( V 1 ∩ V 2 , E 1 ∩ E 2 ) G_1\cap G_2(V_1\cap V_2, E_1\cap E_2) G1∩G2(V1∩V2,E1∩E2)表示为 G 1 ( V 1 , E 1 ) G_1(V_1,E_1) G1(V1,E1) G 2 ( V 2 , E 2 ) G_2(V_2,E_2) G2(V2,E2)则 G 1 ∩ G 2 ( V 1 ∩ V 2 , E 1 ∩ E 2 ) G_1\cap G_2(V_1\cap V_2, E_1\cap E_2) G1∩G2(V1∩V2,E1∩E2)。
差运算Difference G 1 − G 2 ( V 1 , E 1 − E 2 ) G_1 - G_2(V_1, E_1 - E_2) G1−G2(V1,E1−E2)写成 G 1 ( V 1 , E 1 ) G_1(V_1,E_1) G1(V1,E1) G 2 ( V 2 , E 2 ) G_2(V_2,E_2) G2(V2,E2)则 G 1 − G 2 ( V 1 , E 1 − E 2 ) G_1 - G_2(V_1, E_1 - E_2) G1−G2(V1,E1−E2)。
特殊的点集/边集
支配集Dominating Set
在无向图 G ( V , E ) G(V,E) G(V,E) 中顶点子集 D ⊆ V D\subseteq V D⊆V 称为支配集若对任意顶点 v ∈ V − D v\in V - D v∈V−D都存在顶点 u ∈ D u\in D u∈D 使得 u u u 和 v v v 相邻可表示为 G ( V , E ) G(V,E) G(V,E) 无向图 ∃ D ⊆ V \exists D\subseteq V ∃D⊆V ∀ v ∈ V − D \forall v\in V - D ∀v∈V−D ∃ u ∈ D \exists u\in D ∃u∈D u ∼ v u \sim v u∼v则 D D D 为支配集。
边支配集Edge Dominating Set
在无向图 G ( V , E ) G(V,E) G(V,E) 中边子集 F ⊆ E F\subseteq E F⊆E 称为边支配集若对任意边 e ∈ E − F e\in E - F e∈E−F都存在边 f ∈ F f\in F f∈F 与 e e e 相邻共享端点写成 G ( V , E ) G(V,E) G(V,E) 无向图 ∃ F ⊆ E \exists F\subseteq E ∃F⊆E ∀ e ∈ E − F \forall e\in E - F ∀e∈E−F ∃ f ∈ F \exists f\in F ∃f∈F e e e 与 f f f 共享端点则 F F F 为边支配集。
独立集Independent Set
在无向图 G ( V , E ) G(V,E) G(V,E) 中顶点子集 I ⊆ V I\subseteq V I⊆V 称为独立集若 I I I 中任意两个顶点都不相邻即 G ( V , E ) G(V,E) G(V,E) 无向图 ∃ I ⊆ V \exists I\subseteq V ∃I⊆V ∀ u , v ∈ I \forall u,v\in I ∀u,v∈I u u u 与 v v v 不相邻则 I I I 为独立集。
匹配Matching
在无向图 G ( V , E ) G(V,E) G(V,E) 中边子集 M ⊆ E M\subseteq E M⊆E 称为匹配若 M M M 中的边两两之间没有公共端点可表示为 G ( V , E ) G(V,E) G(V,E) 无向图 ∃ M ⊆ E \exists M\subseteq E ∃M⊆E ∀ e 1 , e 2 ∈ M \forall e_1,e_2\in M ∀e1,e2∈M e 1 e_1 e1 与 e 2 e_2 e2 无公共端点则 M M M 为匹配。
点覆盖Vertex Cover
在无向图 G ( V , E ) G(V,E) G(V,E) 中顶点子集 C ⊆ V C\subseteq V C⊆V 称为点覆盖若图 G G G 中的每条边至少有一个端点在 C C C 中写成 G ( V , E ) G(V,E) G(V,E) 无向图 ∃ C ⊆ V \exists C\subseteq V ∃C⊆V ∀ e ∈ E \forall e\in E ∀e∈E ∃ v ∈ C \exists v\in C ∃v∈C v v v 为 e e e 的端点则 C C C 为点覆盖。
边覆盖Edge Cover
在无向图 G ( V , E ) G(V,E) G(V,E) 中边子集 L ⊆ E L\subseteq E L⊆E 称为边覆盖若对于任意顶点 v ∈ V v\in V v∈V都存在边 e ∈ L e\in L e∈L 使得 v v v 是 e e e 的端点可表示为 G ( V , E ) G(V,E) G(V,E) 无向图 ∃ L ⊆ E \exists L\subseteq E ∃L⊆E ∀ v ∈ V \forall v\in V ∀v∈V ∃ e ∈ L \exists e\in L ∃e∈L v v v 为 e e e 的端点则 L L L 为边覆盖。
团Clique
在无向图 G ( V , E ) G(V,E) G(V,E) 中顶点子集 K ⊆ V K\subseteq V K⊆V 称为团若 K K K 中任意两个顶点都相邻即 K K K 所诱导出的子图是完全图可表示为 G ( V , E ) G(V,E) G(V,E) 无向图 ∃ K ⊆ V \exists K\subseteq V ∃K⊆V ∀ u , v ∈ K \forall u,v\in K ∀u,v∈K u ∼ v u \sim v u∼v则 K K K 为团。
图的矩阵表示(存储方式)
邻接矩阵Adjacency Matrix
对于一个无向图 G ( V , E ) G(V,E) G(V,E) 设顶点集 V { v 1 , v 2 , ⋯ , v n } V \{v_1, v_2, \cdots, v_n\} V{v1,v2,⋯,vn}其邻接矩阵 A A A 是一个 n × n n\times n n×n 的矩阵其中元素 a i j a_{ij} aij 定义为若顶点 v i v_i vi 和 v j v_j vj 相邻则 a i j 1 a_{ij} 1 aij1对于无向简单图若不相邻则 a i j 0 a_{ij} 0 aij0。
用公式表示为 a i j { 1 , v i ∼ v j 相邻 0 , v i ∼ v j 不相邻 a_{ij} \begin{cases}1, v_i \sim v_j\text{相邻} \\ 0, v_i \sim v_j\text{不相邻}\end{cases} aij{1,0,vi∼vj相邻vi∼vj不相邻
例如对于一个简单的三角形形状的无向图其邻接矩阵为 ( 0 1 1 1 0 1 1 1 0 ) \begin{pmatrix}0 1 1 \\ 1 0 1 \\ 1 1 0\end{pmatrix} 011101110 。
对于有向图若存在从顶点 v i v_i vi 指向 v j v_j vj 的边则 a i j 1 a_{ij} 1 aij1否则 a i j 0 a_{ij} 0 aij0。其邻接矩阵能反映出有向图中顶点之间的有向连接关系。
关联矩阵Incidence Matrix
设无向图 G ( V , E ) G(V,E) G(V,E) 顶点集 V { v 1 , v 2 , ⋯ , v n } V \{v_1, v_2, \cdots, v_n\} V{v1,v2,⋯,vn}边集 E { e 1 , e 2 , ⋯ , e m } E \{e_1, e_2, \cdots, e_m\} E{e1,e2,⋯,em}其关联矩阵 M M M 是一个 n × m n\times m n×m 的矩阵元素 m i j m_{ij} mij 定义如下若顶点 v i v_i vi 与边 e j e_j ej 关联即 v i v_i vi 是 e j e_j ej 的一个端点则 m i j 1 m_{ij} 1 mij1若不关联则 m i j 0 m_{ij} 0 mij0。
用公式表示为 m i j { 1 , 如果 v i 关联 e j 0 , 如果 v i 不关联 e j m_{ij} \begin{cases}1, \text{如果} v_i \text{关联} e_j \\ 0, \text{如果} v_i \text{不关联} e_j\end{cases} mij{1,0,如果vi关联ej如果vi不关联ej
例如对于一个简单的有四条边、三个顶点的无向图其关联矩阵可能为 ( 1 1 0 0 1 0 1 1 0 1 1 0 ) \begin{pmatrix}1 1 0 0 \\ 1 0 1 1 \\ 0 1 1 0\end{pmatrix} 110101011010 。 有向图的关联矩阵定义稍有不同对于有向边 e j e_j ej 若顶点 v i v_i vi 是边 e j e_j ej 的起点则 m i j 1 m_{ij} 1 mij1若 v i v_i vi 是边 e j e_j ej 的终点则 m i j − 1 m_{ij} -1 mij−1若 v i v_i vi 与 e j e_j ej 不关联则 m i j 0 m_{ij} 0 mij0。
2、图的存储
n为图的顶点数m为图的边数 d ( u ) d^(u) d(u)为点u的出度 d − ( u ) d^-(u) d−(u)为点u的入度
2.1、直接存边
实现
使用多个数组来存储变得起点终点和权值。
复杂度
查询是否存在某条边 O ( m ) O(m) O(m)
遍历一个点的所有出边 O ( m ) O(m) O(m)
遍历整张图 O ( n m ) O(nm) O(nm)
空间复杂度 O ( m ) O(m) O(m)
注在Kruskal算法中需要把边按权值排序需要直接存储边。
2.2、邻接矩阵
实现
使用二维数组 a d j [ u ] [ v ] adj[u][v] adj[u][v] 来存储 a d j [ u ] [ v ] adj[u][v] adj[u][v]的值表示 u u u 到 v v v 是否有边。
用公式表示为 a d j [ u ] [ v ] { 1 , 存在 u 到 v 的边 0 , 不存在 u 到 v 的边 adj[u][v] \left\{\begin{matrix} 1 ,存在u到v的边\\ 0 ,不存在u到v的边 \end{matrix}\right. adj[u][v]{10,存在u到v的边,不存在u到v的边
代码
复杂度
查询是否存在某条边 O ( 1 ) O(1) O(1)
遍历一个点的所有出边 O ( n ) O(n) O(n)
遍历整张图 O ( n 2 ) O(n^2) O(n2)
空间复杂度 O ( n 2 ) O(n^2) O(n2)
邻接矩阵只适用于没有重边的图
由于邻接矩阵在稀疏图上效率很低尤其是在点数较多的图上空间无法承受所以一般只会在稠密图上使用邻接矩阵。
2.3、邻接表
2.4、链式前向星
