更改

* <math>V</math> 是点集；

* <math>V</math> 是点集；

* <math>E</math> 是边集；

* <math>E</math> 是边集；

* <math>\phi:E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是一个将每条边映射到一个无序顶点对的关联函数 incidence function（于是边连接了顶点对）。

* <math>\phi:E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是一个将每条边映射到一个无序顶点对的关联函数（于是边连接了顶点对）。

=== 语言学 ===

=== 语言学 ===

现有研究通过多种途径证明了图论在语言学研究中的作用，因为自然语言往往有适合自己的离散结构。传统上，语法和组合语义遵循基于树的结构，其表达能力基于复合性原理 principle of compositionality，且是在层次图中建模的。更现代的方法，如中心语驱动词组结构律 head-driven phrase structure grammar(HPSG)，使用类型特征结构 typed feature structures——有向无环图对自然语言的语法建模。在尤其是应用于计算机的词汇语义学 lexical semantics中，当一个给定词可被相关的词解释时，建立词义模型变得更加容易; 因此，语义网络 semantic networks在计算语言学中很重要。不过，音系学 phonology中的其他方法（例如使用'''格图 lattice graphs'''的优选论 optimality theory）和形态学 morphology（例如使用有限状态置换器 finite-state transducers的有限状态构词法 finite-state morphology）在将语言作为图形分析时很常见。实际上，数学的这个领域对语言学的用处已经促进了一些组织的出现，如[http://www.textgraphs.org/ TextGraphs]，以及各种各样的“Net”项目，如[http://wordnet.princeton.edu/ WordNet]、[https://en.wikipedia.org/wiki/VerbNet VerbNet]等。

现有研究通过多种途径证明了图论在语言学研究中的作用，因为自然语言往往有适合自己的离散结构。传统上，语法和组合语义遵循基于树的结构，其表达能力基于复合性原理 principle of compositionality，且是在层次图中建模的。更现代的方法，如中心语驱动词组结构律 head-driven phrase structure grammar(HPSG)，使用类型特征结构——有向无环图对自然语言的语法建模。在尤其是应用于计算机的词汇语义学中，当一个给定词可被相关的词解释时，建立词义模型变得更加容易; 因此，语义网络在计算语言学中很重要。不过，音系学中的其他方法（例如使用'''格图 lattice graphs'''的优选论 optimality theory）和形态学（例如使用有限状态置换器 finite-state transducers的有限状态构词法 finite-state morphology）在将语言作为图形分析时很常见。实际上，数学的这个领域对语言学的用处已经促进了一些组织的出现，如[http://www.textgraphs.org/ TextGraphs]，以及各种各样的“Net”项目，如[http://wordnet.princeton.edu/ WordNet]、[https://en.wikipedia.org/wiki/VerbNet VerbNet]等。

=== 物理和化学 ===

=== 物理和化学 ===

图论在化学和物理学中也被用来研究分子。在凝聚态物理学中，通过收集与原子拓扑结构有关的图论性质的统计数据，可以定量地研究复杂模拟原子结构的三维结构。此外，“'''费曼图 Feynman diagram'''和计算规则以一种与人们想要理解的实验数字密切相关的形式总结了量子场论 。”<ref>{{cite book|first=J. D.|last=Bjorken |first2=S. D. |last2=Drell |title=Relativistic Quantum Fields |url=https://archive.org/details/relativisticquan0000bjor_c5q0|url-access=registration|publisher=McGraw-Hill |location=New York |year=1965 |page=viii }}</ref> 在化学中，图为分子建立了一个自然的模型，其中顶点代表原子，边代表键 bonds。这种方法特别适用于分子结构的计算机处理，从[https://en.wikipedia.org/wiki/Molecule_editor '''分子编辑器 chemical editors''']到数据库检索。在统计物理学中，图可以表示系统中相互作用的部分之间的局部联系，以及这些系统上物理过程的动态。类似地，在计算神经科学中，图可以用来表示大脑区域之间的功能联系，这些区域相互作用产生各种认知过程，顶点代表大脑的不同区域，边代表这些区域之间的联系。图论在电网络的电学建模中起着重要作用，在这里，权值与导线段的电阻联系起来，以获得网络结构的电学特性。<ref>{{Cite journal|last=Kumar|first=Ankush|last2=Kulkarni|first2=G. U.|date=2016-01-04|title=Evaluating conducting network based transparent electrodes from geometrical considerations|journal=Journal of Applied Physics|volume=119|issue=1|pages=015102|doi=10.1063/1.4939280|issn=0021-8979|bibcode=2016JAP...119a5102K}}</ref> 图形也用来表示多孔介质的微尺度通道，其中顶点代表孔隙，边代表连接孔隙的较小通道。'''化学图论 Chemical graph theory'''利用分子图 molecular graph来建立分子模型。图形和网络是研究和理解相变和临界现象的优秀模型。去除节点或边会导致了临界过渡，在此过程中网络分裂成小簇，作为相变研究。分裂过程被用逾渗理论 percolation theory研究。<ref>{{Cite book |last = Newman| first = Mark | title = Networks: An Introduction| publisher=Oxford University Press| date = 2010|  url = http://math.sjtu.edu.cn/faculty/xiaodong/course/Networks%20An%20introduction.pdf}}</ref>

图论在化学和物理学中也被用来研究分子。在凝聚态物理学中，通过收集与原子拓扑结构有关的图论性质的统计数据，可以定量地研究复杂模拟原子结构的三维结构。此外，“'''费曼图 Feynman diagram'''和计算规则以一种与人们想要理解的实验数字密切相关的形式总结了量子场论 。”<ref>{{cite book|first=J. D.|last=Bjorken |first2=S. D. |last2=Drell |title=Relativistic Quantum Fields |url=https://archive.org/details/relativisticquan0000bjor_c5q0|url-access=registration|publisher=McGraw-Hill |location=New York |year=1965 |page=viii }}</ref> 在化学中，图为分子建立了一个自然的模型，其中顶点代表原子，边代表键 bonds。这种方法特别适用于分子结构的计算机处理，从[https://en.wikipedia.org/wiki/Molecule_editor '''分子编辑器 chemical editors''']到数据库检索。在统计物理学中，图可以表示系统中相互作用的部分之间的局部联系，以及这些系统上物理过程的动态。类似地，在计算神经科学中，图可以用来表示大脑区域之间的功能联系，这些区域相互作用产生各种认知过程，顶点代表大脑的不同区域，边代表这些区域之间的联系。图论在电网络的电学建模中起着重要作用，在这里，权值与导线段的电阻联系起来，以获得网络结构的电学特性。<ref>{{Cite journal|last=Kumar|first=Ankush|last2=Kulkarni|first2=G. U.|date=2016-01-04|title=Evaluating conducting network based transparent electrodes from geometrical considerations|journal=Journal of Applied Physics|volume=119|issue=1|pages=015102|doi=10.1063/1.4939280|issn=0021-8979|bibcode=2016JAP...119a5102K}}</ref> 图形也用来表示多孔介质的微尺度通道，其中顶点代表孔隙，边代表连接孔隙的较小通道。'''化学图论 Chemical graph theory'''利用分子图来建立分子模型。图形和网络是研究和理解相变和临界现象的优秀模型。去除节点或边会导致了临界过渡，在此过程中网络分裂成小簇，作为相变研究。分裂过程被用逾渗理论 percolation theory研究。<ref>{{Cite book |last = Newman| first = Mark | title = Networks: An Introduction| publisher=Oxford University Press| date = 2010|  url = http://math.sjtu.edu.cn/faculty/xiaodong/course/Networks%20An%20introduction.pdf}}</ref>

<ref>Reuven Cohen, Shlomo Havlin (2010). Complex Networks: Structure, Robustness and Function  Cambridge University Press. </ref>

<ref>Reuven Cohen, Shlomo Havlin (2010). Complex Networks: Structure, Robustness and Function  Cambridge University Press. </ref>

图论也用于连接组学 connectomics；<ref>{{Cite journal|last=Shah|first=Preya|last2=Ashourvan|first2=Arian|last3=Mikhail|first3=Fadi|last4=Pines|first4=Adam|last5=Kini|first5=Lohith|last6=Oechsel|first6=Kelly|last7=Das|first7=Sandhitsu R|last8=Stein|first8=Joel M|last9=Shinohara|first9=Russell T|date=2019-07-01|title=Characterizing the role of the structural connectome in seizure dynamics|journal=Brain|language=en|volume=142|issue=7|pages=1955–1972|doi=10.1093/brain/awz125|issn=0006-8950}}</ref> 神经系统可以看作一个图，其中节点是神经元，边是它们之间的连接。

图论也用于连接组学；<ref>{{Cite journal|last=Shah|first=Preya|last2=Ashourvan|first2=Arian|last3=Mikhail|first3=Fadi|last4=Pines|first4=Adam|last5=Kini|first5=Lohith|last6=Oechsel|first6=Kelly|last7=Das|first7=Sandhitsu R|last8=Stein|first8=Joel M|last9=Shinohara|first9=Russell T|date=2019-07-01|title=Characterizing the role of the structural connectome in seizure dynamics|journal=Brain|language=en|volume=142|issue=7|pages=1955–1972|doi=10.1093/brain/awz125|issn=0006-8950}}</ref> 神经系统可以看作一个图，其中节点是神经元，边是它们之间的连接。

欧拉的论文发表后一个多世纪，凯莱 Cayley研究了在微分学中出现的一种数学分析的特殊形式，而这最终将他引向对一种特殊的被称为“树”的图的研究。<ref>citation|first=A.|last=Cayley|authorlink=Arthur Cayley|year=1857|title=On the theory of the analytical forms called trees|journal=Philosophical Magazine|series=Series IV|volume=13|issue=85|pages=172–176|doi=10.1017/CBO9780511703690.046|isbn=9780511703690</ref> 由于有机化学中有许多树状结构的分子，这些研究对于理论化学有着重要意义，尤其是其中关于具有某一特定性质的图的计数问题。除凯莱的成果外，波利亚 Pólya也于1935至1937年发表了一些成果，1959年，De Bruijn做了一些推广。<ref name="Cayley1">{{Citation|author=Cayley, A.|year=1875|journal=Berichte der Deutschen Chemischen Gesellschaft|title=Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen|volume=8|pages=1056–1059|doi=10.1002/cber.18750080252|postscript=.|issue=2}}</ref> 这些研究成果奠定了图的计数理论的基础。凯莱将他关于树的研究成果与当时有关化合物的研究联系起来，<ref name="Cayley1">{{Citation|author=Cayley, A.|year=1875|journal=Berichte der Deutschen Chemischen Gesellschaft|title=Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen|volume=8|pages=1056–1059|doi=10.1002/cber.18750080252|postscript=.|issue=2}}</ref> 而图论中有一部分术语正是来源于这种将数学与化学相联系的做法。

欧拉的论文发表后一个多世纪，凯莱 Cayley研究了在微分学中出现的一种数学分析的特殊形式，而这最终将他引向对一种特殊的被称为“树”的图的研究。<ref>citation|first=A.|last=Cayley|authorlink=Arthur Cayley|year=1857|title=On the theory of the analytical forms called trees|journal=Philosophical Magazine|series=Series IV|volume=13|issue=85|pages=172–176|doi=10.1017/CBO9780511703690.046|isbn=9780511703690</ref> 由于有机化学中有许多树状结构的分子，这些研究对于理论化学有着重要意义，尤其是其中关于具有某一特定性质的图的计数问题。除Cayley的成果外，波利亚 Pólya也于1935至1937年发表了一些成果，1959年，De Bruijn做了一些推广。<ref name="Cayley1">{{Citation|author=Cayley, A.|year=1875|journal=Berichte der Deutschen Chemischen Gesellschaft|title=Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen|volume=8|pages=1056–1059|doi=10.1002/cber.18750080252|postscript=.|issue=2}}</ref> 这些研究成果奠定了图的计数理论的基础。Cayley将他关于树的研究成果与当时有关化合物的研究联系起来，<ref name="Cayley1">{{Citation|author=Cayley, A.|year=1875|journal=Berichte der Deutschen Chemischen Gesellschaft|title=Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen|volume=8|pages=1056–1059|doi=10.1002/cber.18750080252|postscript=.|issue=2}}</ref> 而图论中有一部分术语正是来源于这种将数学与化学相联系的做法。

'''四色问题 four color problem'''可谓是图论研究史上最著名也是产生成果最多的问题之一：“是否任何一幅画在平面上的地图都可以用四种颜色染色，使得任意两个相邻的区域不同色？”这一问题由Francis Guthrie于1852年提出，而最早的文字记载则出现在德摩根 De Morgan于1852年写给哈密顿的一封信上。包括凯莱、肯普 Kempe等在内的许多人都曾给出过错误的证明。泰特Peter Guthrie Tait、希伍德 Percy John Heawood、拉姆齐 Ramsey和Hugo Hadwiger对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，Heinrich Heesch发表了一个用计算机解决此问题的方法。<ref>Heinrich Heesch: Untersuchungen zum Vierfarbenproblem. Mannheim: Bibliographisches Institut 1969.</ref>1976年，阿佩尔 Kenneth Appel和沃夫冈·哈肯 Wolfgang Haken借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色。但此方法由于过于复杂，在当时未被广泛接受。<ref name="AA1">{{Citation|author1=Appel, K.  |author2=Haken, W.|title=Every planar map is four colorable. Part I. Discharging|journal=Illinois J. Math.|volume=21|issue=3|year=1977|pages=429–490|postscript=.|doi=10.1215/ijm/1256049011|doi-access=free}}</ref><ref name="AA2">{{Citation|author1=Appel, K.  |author2=Haken, W.|title=Every planar map is four colorable. Part II. Reducibility|journal=Illinois J. Math.|volume=21|issue=3|year=1977|pages=491–567|postscript=.|doi=10.1215/ijm/1256049012|doi-access=free}}</ref>  

'''四色问题 four color problem'''可谓是图论研究史上最著名也是产生成果最多的问题之一：“是否任何一幅画在平面上的地图都可以用四种颜色染色，使得任意两个相邻的区域不同色？”这一问题由Francis Guthrie于1852年提出，而最早的文字记载则出现在德摩根 De Morgan于1852年写给哈密顿的一封信上。包括Cayley、肯普 Kempe等在内的许多人都曾给出过错误的证明。泰特Peter Guthrie Tait、希伍德 Percy John Heawood、拉姆齐 Ramsey和Hugo Hadwiger对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，Heinrich Heesch发表了一个用计算机解决此问题的方法。<ref>Heinrich Heesch: Untersuchungen zum Vierfarbenproblem. Mannheim: Bibliographisches Institut 1969.</ref>1976年，阿佩尔 Kenneth Appel和沃夫冈·哈肯 Wolfgang Haken借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色。但此方法由于过于复杂，在当时未被广泛接受。<ref name="AA1">{{Citation|author1=Appel, K.  |author2=Haken, W.|title=Every planar map is four colorable. Part I. Discharging|journal=Illinois J. Math.|volume=21|issue=3|year=1977|pages=429–490|postscript=.|doi=10.1215/ijm/1256049011|doi-access=free}}</ref><ref name="AA2">{{Citation|author1=Appel, K.  |author2=Haken, W.|title=Every planar map is four colorable. Part II. Reducibility|journal=Illinois J. Math.|volume=21|issue=3|year=1977|pages=491–567|postscript=.|doi=10.1215/ijm/1256049012|doi-access=free}}</ref>  

1860年之1930年间，若当 Jordan、库拉托夫斯基 Kuratowski和惠特尼 Whitney从之前独立于图论发展的拓扑学中吸取大量内容进入图论，而现代代数方法的使用更让图论与拓扑走上共同发展的道路。其中应用代数较早者如物理学家 Gustav Kirchhoff于1845年发表的电路定律 Kirchhoff's circuit laws。

1860年之1930年间，若当 Jordan、库拉托夫斯基 Kuratowski和惠特尼 Whitney从之前独立于图论发展的拓扑学中吸取大量内容进入图论，而现代代数方法的使用更让图论与拓扑走上共同发展的道路。其中应用代数较早者如物理学家基尔霍夫 Gustav Kirchhoff于1845年发表的基尔霍夫电路定律 Kirchhoff's circuit laws。

== 图论问题 ==

== 图论问题 ==

=== 图枚举 ===

=== 图枚举 ===

图形枚举 graph enumeration是满足特定条件的图的计数问题，相关文献很多。

图枚举 graph enumeration是满足特定条件的图的计数问题，相关文献很多。

=== 包容与统一 ===

=== 包容与统一 Subsumption and unification===

约束建模理论关注由偏序 partial order关联的有向图族。在这些应用中，图是按特异性排序的，这意味着更具体并因此包含更多信息的约束图被更一般的图所包含。 图之间的运算包括计算两个图（如果有的话）之间包容关系的方向，以及计算图的统一性。两个参数图的统一定义为与输入一致（即包含所有信息）的最一般的图（或其计算）（如果存在的话）；有效的统一算法是已知的。

约束建模理论关注由偏序 partial order关联的有向图族。在这些应用中，图是按特异性排序的，这意味着更具体并因此包含更多信息的约束图被更一般的图所包含。 图之间的运算包括计算两个图（如果有的话）之间包容关系的方向，以及计算图的统一性。两个参数图的统一定义为与输入一致（即包含所有信息）的最一般的图（或其计算）（如果存在的话）；有效的统一算法是已知的。

=== 路径问题 ===

=== 路径问题 Route problems===

[[File:seven_bridge.jpeg|300px|thumb|right|柯尼斯堡七桥问题：在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？]]

[[File:seven_bridge.jpeg|300px|thumb|right|柯尼斯堡七桥问题：在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？]]

* 柯尼斯堡七桥问题 Seven bridges of Königsberg

* 柯尼斯堡七桥问题 Seven bridges of Königsberg

=== 网络流与匹配 ===

=== 网络流 network flow===

* 最大流最小割定理  

* 最大流最小割定理  

* 最小费用最大流问题

* 最小费用最大流问题

=== 可见性问题 ===

=== 可见性问题 Visibility problems===

* 博物馆保安问题 Museum guard problem

* 博物馆保安问题 Museum guard problem

=== 覆盖问题 ===

=== 覆盖问题 Covering problems ===

图的覆盖问题 Covering problems可能涉及到顶点/子图子集上的各种集合覆盖问题  set cover problem(SCP)。

图的覆盖问题可能涉及到顶点/子图子集上的各种集合覆盖问题  set cover problem(SCP)。

* 控制集 Dominating set问题是集合覆盖问题的特例，其中集是封闭邻域 neighborhoods

* 控制集 Dominating set问题是集合覆盖问题的特例，其中集是封闭邻域 neighborhoods

* 顶点覆盖问题 Vertex cover problem是集合覆盖问题的特例

* 顶点覆盖问题 Vertex cover problem是集合覆盖问题的特例

=== 分解问题 ===

=== 分解问题 Decomposition problems===

分解 Decomposition，被定义为对图的边集进行划分（在划分的每个部分的边上有必要的多个顶点），有各类问题。通常，需要将图分解为与给定图同构的子图; 例如，将一个完全图 complete graph分解为哈密顿圈 Hamiltonian cycle。其他问题指定一个图族，其中一个给定的图应该被分解，例如，一个圈族，或将一个完全图<math>K_n</math>分解为分别分别有<math>1,2,3,...,n-1</math>条边的<math>n-1</math>棵指定树。

分解，被定义为对图的边集进行划分（在划分的每个部分的边上有必要的多个顶点），有各类问题。通常，需要将图分解为与给定图同构的子图; 例如，将一个完全图 complete graph分解为哈密顿圈 Hamiltonian cycle。其他问题指定一个图族，其中一个给定的图应该被分解，例如，一个圈族，或将一个完全图<math>K_n</math>分解为分别分别有<math>1,2,3,...,n-1</math>条边的<math>n-1</math>棵指定树。