更改

图论 (查看源代码)

2020年8月14日 (五) 08:55的版本

删除77字节、 2020年8月14日 (五) 08:55

无编辑摘要

第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>棵指定树。

薄荷

7,129

个编辑