图论 - 版本历史

13944556914：13944556914移动页面图论 Graph theory至图论覆盖重定向

2024-06-03T08:31:55Z

13944556914移动页面图论 Graph theory至图论覆盖重定向

2024年6月3日 (一) 08:31 13944556914

2024-06-03T08:31:39Z

2020年8月14日 (五) 00:55 薄荷

2020-08-14T00:55:13Z

薄荷：/* 编者推荐 */

2020-04-23T08:42:09Z

编者推荐

薄荷：/* 课程推荐 */

2020-04-23T08:39:41Z

课程推荐

薄荷：/* 图论问题 */

2020-04-23T08:37:38Z

图论问题

薄荷：/* 子图相关问题 */

2020-04-23T08:37:20Z

子图相关问题

薄荷：/* 图论问题 */

2020-04-23T08:36:32Z

图论问题

2020年4月23日 (四) 08:35 薄荷

2020-04-23T08:35:14Z

显示更改

薄荷：/* 图论问题 */

2020-04-23T08:26:28Z

图论问题

@@ 第4行： / 第4行： @@
 }}
-'''图论 Graph theory'''是指研究图和网络的数学分支，常被认为是'''组合数学 Combinatorial mathematics'''的一个分支，但这一分支已经发展得足够庞大和有特点，并有自身领域所研究的问题，因此被视为一个独立的主题。它和其他数学分支，如群论、矩阵论、拓扑学有着密切关系。'''图 graph'''是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点代表事物，连接两顶点的边则表示两个事物间具有这种关系。
+'''图论 （Graph theory）'''是指研究图和网络的数学分支，常被认为是'''组合数学 Combinatorial mathematics'''的一个分支，但这一分支已经发展得足够庞大和有特点，并有自身领域所研究的问题，因此被视为一个独立的主题。它和其他数学分支，如群论、矩阵论、拓扑学有着密切关系。'''图 graph'''是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点代表事物，连接两顶点的边则表示两个事物间具有这种关系。
 [[File:connections.jpeg|缩略图|400px|关联关系：图形通常用来描述某些事物之间的某种特定关系。顶点代表事物，连接两顶点的边则表示两事物间具有这种关系]]

@@ 第5行： / 第5行： @@
 '''图论 Graph theory'''是指研究图和网络的数学分支，常被认为是'''组合数学 Combinatorial mathematics'''的一个分支，但这一分支已经发展得足够庞大和有特点，并有自身领域所研究的问题，因此被视为一个独立的主题。它和其他数学分支，如群论、矩阵论、拓扑学有着密切关系。'''图 graph'''是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点代表事物，连接两顶点的边则表示两个事物间具有这种关系。
-[[File:connections.jpeg|缩略图|400px|市场中的关联关系：图形通常用来描述某些事物之间的某种特定关系。顶点代表事物，连接两顶点的边则表示两个事物间具有这种关系]]
+[[File:connections.jpeg|缩略图|400px|关联关系：图形通常用来描述某些事物之间的某种特定关系。顶点代表事物，连接两顶点的边则表示两事物间具有这种关系]]
 == 定义 ==
@@ 第47行： / 第47行： @@
 === [[有向图]] ===
 [[File:Directed.png|缩略图|有三个顶点和四条有向边的有向图（双箭头表示双指向）]]
-'''有向图 directed graph/digraph'''是边有方向的图。，<ref> {{cite book |last1=Bender |first1=Edward A. |last2=Williamson |first2=S. Gill |date=2010 |title=Lists, Decisions and Graphs. With an Introduction to Probability |url=https://books.google.fr/books?id=vaXv_yhefG8C |location= |page= |isbn= |author-link= }}p.161</ref>通常定义为一个'''有序对 ordered pair''' <math>G=(V,E)</math>，其中
+'''有向图 directed graph/digraph'''是边有方向的图。<ref> {{cite book |last1=Bender |first1=Edward A. |last2=Williamson |first2=S. Gill |date=2010 |title=Lists, Decisions and Graphs. With an Introduction to Probability |url=https://books.google.fr/books?id=vaXv_yhefG8C |location= |page= |isbn= |author-link= }}p.161</ref>通常定义为一个'''有序对 ordered pair''' <math>G=(V,E)</math>，其中
 * <math>V</math> 是顶点 vertices/nodes/points的集合；
-* <math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是边 edges/directed edges/directed links/directed lines/arrows/arcs的集合，边由所有顶点的无序对 ordered pair构成（换句话说，边连接了顶点对）。
+* <math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是边 edges/directed edges/directed links/directed lines/arrows/arcs的集合，边由所有顶点的有序对 ordered pair构成（换句话说，边连接了顶点对）。
-为避免歧义，上面定义的对象可被更精准地称作有向简单图 directed simple graph。
+为避免歧义，上面定义的对象可被更精准地称作'''有向简单图 directed simple graph'''。
-在从<math> x </math>指向<math> y </math>的边<math>(x,y)</math>中，顶点 x 和 y 称为边的端点 endpoints，<math> x </math>为边的尾部 tail ，<math> y </math>为边的头部 head。 边<math>(y,x)</math>称为<math>(x,y)</math>的inverted edge。边称为连接 join/incident on<math> x </math>和<math> y </math>。 图中的某顶点可能不属于任意一条边。'''自环 loop'''是连接顶点与自身的边。'''重边 Multiple edges'''是连接同一对顶点的两条或多条边。
+在从<math> x </math>指向<math> y </math>的边<math>{x,y}</math>中，顶点 x 和 y 称为边的端点 endpoints，<math> x </math>为边的尾部 tail ，<math> y </math>为边的头部 head。 边<math>{y,x}</math>称为<math>{x,y}</math>的inverted edge。边称为连接 join/incident on<math> x </math>和<math> y </math>。 图中的某顶点可能不属于任意一条边。'''自环 loop'''是连接顶点与自身的边。'''重边 Multiple edges'''是连接同一对顶点的两条或多条边。
@@ 第61行： / 第61行： @@
 * <math>V</math> 是点集；
 * <math>E</math> 是边集；
-* <math>\phi:E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是一个将每条边映射到一个无序顶点对的关联函数（于是边连接了顶点对）。
+* <math>\phi:E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是一个将每条边映射到一个有序顶点对的关联函数（于是边连接了顶点对）。
-为避免歧义，上面定义的对象可被更精准地称作有向多重图 directed multigraph。
+为避免歧义，上面定义的对象可被更精准地称作'''有向多重图 directed multigraph'''。
-上述两个定义中的图不能有自环。为了允许自环，需要扩展定义。对于有向简单图，<math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math>应为<math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2 \right\}</math>。对于有向多重图，<math>E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math>应为<math>E\to\left\{\left\{x,y\right\}:(x,y)\in V^2\right\}</math>。为避免歧义，这些类型的对象可以分别称为带自环的有向简单图 undirected simple graph permitting loops和带自环的有向多重图 undirected multigraph permitting loops/箭图 quiver。
+上述两个定义中的图不能有自环。为了允许自环，需要扩展定义。对于有向简单图，<math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math>应为<math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2 \right\}</math>。对于有向多重图，<math>E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math>应为<math>E\to\left\{\left\{x,y\right\}:(x,y)\in V^2\right\}</math>。为避免歧义，这些类型的对象可以分别称为带自环的有向简单图 directed simple graph permitting loops和带自环的有向多重图 undirected multigraph permitting loops/箭图 quiver。
-带自环的有向简单图<math>G</math>在其顶点上诱导出一个对称齐次关系 homogeneous relation，称为<math>G</math>的邻接关系 adjacency relation。具体来说，对每条边<math>\{ x,y \}</math>，端点<math>x</math>和<math>y</math>称为彼此邻接 adjacent，表示为<math>x\sim y</math>。
+带自环的有向简单图<math>G</math>在其顶点上诱导出一个不对称齐次关系 homogeneous relation，称为<math>G</math>的邻接关系 adjacency relation。具体来说，对每条边<math>\{ x,y \}</math>，端点<math>x</math>和<math>y</math>称为彼此邻接 adjacent，表示为<math>x\sim y</math>。
 == 应用 ==
@@ 第159行： / 第159行： @@
-=== 子图相关问题 subgraph isomorphism problem===
+=== 子图相关 subgraph isomorphism===
 子图同构问题：给定两个图<math> G </math>和<math> H </math>，问<math> G </math>中是否存在一个子图与<math> H </math>同构。这是一个NP完全问题。
 * 哈密顿回路问题可视为一个子图同构问题，即给定一个<math> n </math>个顶点的图，问是否存在一个子图与具有<math> n </math>个顶点的圈同构。
@@ 第195行： / 第195行： @@
-=== 路径问题 Route problems===
+=== 路径 Route ===
 [[File:seven_bridge.jpeg|300px|thumb|right|柯尼斯堡七桥问题：在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？]]
 * 柯尼斯堡七桥问题 Seven bridges of Königsberg
@@ 第215行： / 第215行： @@
-=== 可见性问题 Visibility problems===
+=== 可见性 Visibility ===
 * 博物馆保安问题 Museum guard problem
-=== 覆盖问题 Covering problems ===
+=== 覆盖 Covering ===
 图的覆盖问题可能涉及到顶点/子图子集上的各种集合覆盖问题  set cover problem(SCP)。
 * 控制集 Dominating set问题是集合覆盖问题的特例，其中集是封闭邻域 neighborhoods
@@ 第226行： / 第226行： @@
-=== 分解问题 Decomposition problems===
+=== 分解 Decomposition===
 分解，被定义为对图的边集进行划分（在划分的每个部分的边上有必要的多个顶点），有各类问题。通常，需要将图分解为与给定图同构的子图; 例如，将一个完全图 complete graph分解为哈密顿圈 Hamiltonian cycle。其他问题指定一个图族，其中一个给定的图应该被分解，例如，一个圈族，或将一个完全图<math>K_n</math>分解为分别分别有<math>1,2,3,...,n-1</math>条边的<math>n-1</math>棵指定树。

@@ 第319行： / 第319行： @@
 [[File:图论导论.jpg|200px|thumb|right|《图论导论》封面]]
 [[File:种群结果如何影响自然选择.jpeg|300px|thumb|right|[https://swarma.org/?p=1113 种群结构如何影响自然选择？图论对进化生物学的启发] ]]
-[[File:图网络读书会.png|300px|thumb|right|图网络读书会]]
+[[File:图网络读书会.png|300px|thumb|right|[https://campus.swarma.org/course/1167 图网络读书会]]]

@@ 第351行： / 第351行： @@
 :'''[https://campus.swarma.org/course/1169  图网络解决优化问题]'''
-:'''https://campus.swarma.org/course/1172 图网络中的对抗学习问题]'''
+:'''[https://campus.swarma.org/course/1172 图网络中的对抗学习问题]'''
 :'''[https://campus.swarma.org/course/1168 GNN 算法变体]'''

←上一版本		2020年4月23日 (四) 08:37的版本
第176行：		第176行：

	一个尚未解决的与子图相关的猜想，'''重构猜想 Reconstruction conjecture'''：一个<math> n </math>阶图是否能够由其所有<math>n-1</math>阶导出子图唯一确定？		一个尚未解决的与子图相关的猜想，'''重构猜想 Reconstruction conjecture'''：一个<math> n </math>阶图是否能够由其所有<math>n-1</math>阶导出子图唯一确定？
		+

	=== 染色 Graph coloring===		=== 染色 Graph coloring===

←上一版本	2024年6月3日 (一) 08:31的版本
（没有差异）

@@ 第159行： / 第159行： @@
-=== 子图相关问题 ===
+=== 子图相关问题 subgraph isomorphism problem===
-'''子图同构问题 subgraph isomorphism problem'''：给定两个图<math> G </math>和<math> H </math>，问<math> G </math>中是否存在一个子图与<math> H </math>同构。这是一个NP完全问题。
+子图同构问题：给定两个图<math> G </math>和<math> H </math>，问<math> G </math>中是否存在一个子图与<math> H </math>同构。这是一个NP完全问题。
 * 哈密顿回路问题可视为一个子图同构问题，即给定一个<math> n </math>个顶点的图，问是否存在一个子图与具有<math> n </math>个顶点的圈同构。
@@ 第176行： / 第176行： @@
 一个尚未解决的与子图相关的猜想，'''重构猜想 Reconstruction conjecture'''：一个<math> n </math>阶图是否能够由其所有<math>n-1</math>阶导出子图唯一确定？
 === 染色 Graph coloring===

@@ 第155行： / 第155行： @@
 == 图论问题 ==
-=== 图枚举 ===
+=== 图枚举 Graph enumeration===
-图枚举 graph enumeration是满足特定条件的图的计数问题，相关文献很多。
+图枚举是满足特定条件的图的计数问题，相关文献很多。
@@ 第178行： / 第178行： @@
-=== 染色 ===
+=== 染色 Graph coloring===
 图论中的许多问题和定理都与图的着色有关。通常，染色需使任意两个相邻顶点不同色或任意邻接边不同色。有关图染色的著名结果和猜想如下:
 * 四色问题 Four-color theorem
@@ 第207行： / 第207行： @@
-=== 网络流 network flow===
+=== 网络流 Network flow===
 在与网络流概念有关的应用中出现了许多问题，例如：
 * 最大流最小割定理

@@ 第217行： / 第217行： @@
 === 可见性问题 ===
 * 博物馆保安问题 Museum guard problem
 === 覆盖问题 ===