更改

* <math>V</math> 是'''顶点 vertices/nodes/points'''的集合；

* <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/links/lines'''的集合，边由所有顶点的'''无序对 ordered pair'''构成（换句话说，边连接了顶点对）。

* <math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是'''边 edges/links/lines'''的集合，边由所有顶点的'''无序对 ordered pair'''构成（换句话说，边连接了顶点对）。

为避免歧义，上面定义的对象可被更精准地称作'''无向简单图 undirected simple graph'''。

为避免歧义，上面定义的对象可被更精准地称作'''无向简单图 undirected simple graph'''。

在边<math>{ x,y }</math>中，顶点<math>x</math>和<math>y</math>称为边的端点 endpoints，边称为连接 join/incident on<math> x </math>和<math> y </math>。图中的某顶点可能不属于任意一条边。'''重边 Multiple edges'''/'''平行边 parallel edges'''是连接同一对顶点的两条或多条边。

在边<math>{ x,y }</math>中，顶点<math>x</math>和<math>y</math>称为边的端点 endpoints，边称为连接 join/incident on<math> x </math>和<math> y </math>。图中的某顶点可能不属于任意一条边。'''重边 Multiple edges'''/'''平行边 parallel edges'''是连接同一对顶点的两条或多条边。

允许重边时，上述定义可以推广：'''图'''是'''有序三元组 ordered triple''' <math>G=(V,E,\phi)</math>，<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.149</ref><ref>See, for instance, Graham et al., p. 5.</ref> 其中  

允许重边时，上述定义可以推广：'''图'''是'''有序三元组 ordered triple''' <math>G=(V,E,\phi)</math>，<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.149</ref><ref>See, for instance, Graham et al., p. 5.</ref> 其中  

* <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> 是一个将每条边映射到一个无序顶点对的'''关联函数 incidence function'''（于是边连接了顶点对）。

为避免歧义，上面定义的对象可被更精准地称作'''无向多重图 undirected multigraph'''。

为避免歧义，上面定义的对象可被更精准地称作'''无向多重图 undirected multigraph'''。

'''自环 loop'''是连接顶点与自身的边，上述两个定义中的图不能有自环。为了允许自环，需要扩展定义。对于无向简单图，<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'''。

 

'''自环 loop'''是连接顶点与自身的边，上述两个定义中的图不能有自环。为了允许自环，需要扩展定义。对于无向简单图，<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。

（编者注：一种更常见的定义认为简单图是不含重边或自环的图，而多重图是允许重边的图；另外，'''伪图 pseudograph'''一说同'''多重图 multigraph'''，一说是允许含自环的多重图。）

（编者注：一种更常见的定义认为简单图是不含重边或自环的图，而多重图是允许重边的图；另外，'''伪图 pseudograph'''一说同'''多重图 multigraph'''，一说是允许含自环的多重图。）

<math>V,E</math> 的元素个数通常被认为是有限的；在'''无限图 infinite graphs'''中许多著名的性质都会改变或不成立。此外，<math>V</math> 通常被假定为非空集，而 <math>E</math> 允许为空集。以下再给出一些图论中的定义：图的'''阶 order'''是其顶点个数 <math>|V|</math>，图的尺寸 size为其边数 <math>|E|</math>，顶点的'''度 degree/ valency'''是关联于该顶点的边的数目（自环会被算两次）。

<math>V,E</math> 的元素个数通常被认为是有限的；在'''无限图 infinite graphs'''中许多著名的性质都会改变或不成立。此外，<math>V</math> 通常被假定为非空集，而 <math>E</math> 允许为空集。以下再给出一些图论中的定义：图的'''阶 order'''是其顶点个数 <math>|V|</math>，图的尺寸 size为其边数 <math>|E|</math>，顶点的'''度 degree/ valency'''是关联于该顶点的边的数目（自环会被算两次）。

在<math> n </math>阶无向简单图中，每个顶点的最大度为 <math>n-1</math>，图的最大尺寸为 <math>n (n-1) / 2</math>。

在<math> n </math>阶无向简单图中，每个顶点的最大度为 <math>n-1</math>，图的最大尺寸为 <math>n (n-1) / 2</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>。

带自环无向简单图<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>。

[[File:Directed.png|缩略图|有三个顶点和四条有向边的有向图（双箭头表示双指向）]]

[[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>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'''是连接同一对顶点的两条或多条边。

允许重边时，上述定义可以推广：'''有向图'''是'''有序三元组 ordered triple''' <math>G=(V,E,\phi)</math>，其中  

 

允许重边时，上述定义可以推广：'''有向图'''是有序三元组 ordered triple <math>G=(V,E,\phi)</math>，其中  

* <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> 是一个将每条边映射到一个无序顶点对的关联函数 incidence function（于是边连接了顶点对）。

为避免歧义，上面定义的对象可被更精准地称作'''有向多重图''' 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>。为避免歧义，这些类型的对象可以分别称为带自环的有向简单图 undirected 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>。

=== 计算机科学 ===

=== 计算机科学 ===

在计算机科学中，图用于表示通信网络、数据组织、计算设备、计算流程等。例如，网站的链接结构可以用有向图表示，其中顶点表示网页，有向边表示从一个网页到另一个网页的链接。在社交媒体、<ref>{{Cite journal | volume = 3| issue = 1| last = Grandjean| first = Martin| title = A social network analysis of Twitter: Mapping the digital humanities community| journal =Cogent Arts & Humanities| date = 2016| pages = 1171458|doi=10.1080/23311983.2016.1171458| url = https://hal.archives-ouvertes.fr/hal-01517493/file/A%20social%20network%20analysis%20of%20Twitter%20Mapping%20the%20digital%20humanities%20community.pdf}}</ref>旅行、生物学、计算机芯片设计、神经退行性 neuro-degenerative疾病的发展图绘<ref>{{Cite Journal | volume = 11| issue = 2| last = Vecchio | first = F| title = "Small World" architecture in brain connectivity and hippocampal volume in Alzheimer's disease: a study via graph theory from EEG data| journal =Brain Imaging and Behavior| date = 2017| pages = 473–485| pmid =26960946 | doi = 10.1007/s11682-016-9528-3}}</ref><ref>{{Cite Journal | volume = 81| issue = 2| last = Vecchio | first = F| title = Brain network connectivity assessed using graph theory in frontotemporal dementia| journal = Neurology| date = 2013| pages = 134–143| doi = 10.1212/WNL.0b013e31829a33f8| pmid = 23719145}}</ref>等领域也可以采用类似的方法。因此，开发图的相关算法是计算机科学的重要领域。'''图转换 graph transformation'''通常用'''图重写 Graph rewriting'''系统来表示。图形转换系统侧重于基于规则的内存式图形操作，与之互补的是面向'''事务安全 transaction-safe'''、'''持久 persistent'''存储和图形结构数据查询的'''图形数据库 graph-structured data(GDB)'''。

在计算机科学中，图用于表示通信网络、数据组织、计算设备、计算流程等。例如，网站的链接结构可以用有向图表示，其中顶点表示网页，有向边表示从一个网页到另一个网页的链接。在社交媒体、<ref>{{Cite journal | volume = 3| issue = 1| last = Grandjean| first = Martin| title = A social network analysis of Twitter: Mapping the digital humanities community| journal =Cogent Arts & Humanities| date = 2016| pages = 1171458|doi=10.1080/23311983.2016.1171458| url = https://hal.archives-ouvertes.fr/hal-01517493/file/A%20social%20network%20analysis%20of%20Twitter%20Mapping%20the%20digital%20humanities%20community.pdf}}</ref>旅行、生物学、计算机芯片设计、神经退行性 neuro-degenerative疾病的发展图绘<ref>{{Cite Journal | volume = 11| issue = 2| last = Vecchio | first = F| title = "Small World" architecture in brain connectivity and hippocampal volume in Alzheimer's disease: a study via graph theory from EEG data| journal =Brain Imaging and Behavior| date = 2017| pages = 473–485| pmid =26960946 | doi = 10.1007/s11682-016-9528-3}}</ref><ref>{{Cite Journal | volume = 81| issue = 2| last = Vecchio | first = F| title = Brain network connectivity assessed using graph theory in frontotemporal dementia| journal = Neurology| date = 2013| pages = 134–143| doi = 10.1212/WNL.0b013e31829a33f8| pmid = 23719145}}</ref>等领域也可以采用类似的方法。因此，开发图的相关算法是计算机科学的重要领域。'''图转换 graph transformation'''通常用'''图重写 Graph rewriting'''系统来表示。图形转换系统侧重于基于规则的内存式图形操作，与之互补的是面向事务安全 transaction-safe、持久 persistent存储和图形结构数据查询的图形数据库 graph-structured data(GDB)。

=== 语言学 ===

=== 语言学 ===

现有研究通过多种途径证明了图论在'''语言学 linguistics'''研究中的作用，因为自然语言往往有适合自己的离散结构。传统上，'''语法 syntax'''和'''组合语义 compositional semantics'''遵循基于树的结构，其表达能力基于'''复合性原理 principle of compositionality'''，且是在层次图中建模的。更现代的方法，如'''中心语驱动词组结构律 head-driven phrase structure grammar(HPSG)'''，使用'''类型特征结构 typed feature structures'''——'''有向无环图 directed acyclic graphs'''对自然语言的语法建模。在尤其是应用于计算机的'''词汇语义学 lexical semantics'''中，当一个给定词可被相关的词解释时，建立词义模型变得更加容易; 因此，'''语义网络 semantic networks'''在'''计算语言学 computational linguistics'''中很重要。 不过，'''音系学 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''']等。

现有研究通过多种途径证明了图论在语言学 linguistics研究中的作用，因为自然语言往往有适合自己的离散结构。传统上，语法 syntax和组合语义 compositional semantics遵循基于树的结构，其表达能力基于复合性原理 principle of compositionality，且是在层次图中建模的。更现代的方法，如中心语驱动词组结构律 head-driven phrase structure grammar(HPSG)，使用类型特征结构 typed feature structures——有向无环图 directed acyclic graphs对自然语言的语法建模。在尤其是应用于计算机的词汇语义学 lexical semantics中，当一个给定词可被相关的词解释时，建立词义模型变得更加容易; 因此，语义网络 semantic networks在计算语言学 computational linguistics中很重要。 不过， 音系学 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]等。

=== 物理和化学 ===

=== 物理和化学 ===

图论在化学和物理学中也被用来研究分子。在'''凝聚态物理学 condensed matter physics'''中，通过收集与原子拓扑结构有关的图论性质的统计数据，可以定量地研究复杂模拟原子结构的三维结构。此外，“'''费曼图 Feynman diagram'''和计算规则以一种与人们想要理解的实验数字密切相关的形式总结了'''量子场论 quantum field theory(QFT)'''。”<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''']到数据库检索。在'''统计物理学 statistical physics'''中，图可以表示系统中相互作用的部分之间的局部联系，以及这些系统上物理过程的动态。类似地，在'''计算神经科学 computational neuroscience'''中，图可以用来表示大脑区域之间的功能联系，这些区域相互作用产生各种认知过程，顶点代表大脑的不同区域，边代表这些区域之间的联系。图论在电网络的电学建模中起着重要作用，在这里，权值与导线段的电阻联系起来，以获得网络结构的电学特性。<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> 图形也用来表示'''多孔介质 porous media'''的微尺度通道，其中顶点代表孔隙，边代表连接孔隙的较小通道。'''化学图论 Chemical graph theory'''利用'''分子图 molecular graph'''来建立分子模型。图形和网络是研究和理解'''相变 phase transitions'''和'''临界现象 critical phenomena'''的优秀模型。去除节点或边会导致了临界过渡，在此过程中网络分裂成小簇，作为相变研究。分裂过程被用'''逾渗理论 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>

图论在化学和物理学中也被用来研究分子。在凝聚态物理学 condensed matter physics中，通过收集与原子拓扑结构有关的图论性质的统计数据，可以定量地研究复杂模拟原子结构的三维结构。此外，“'''费曼图 Feynman diagram'''和计算规则以一种与人们想要理解的实验数字密切相关的形式总结了量子场论 quantum field theory(QFT)。”<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''']到数据库检索。在统计物理学 statistical physics中，图可以表示系统中相互作用的部分之间的局部联系，以及这些系统上物理过程的动态。类似地，在计算神经科学 computational neuroscience中，图可以用来表示大脑区域之间的功能联系，这些区域相互作用产生各种认知过程，顶点代表大脑的不同区域，边代表这些区域之间的联系。图论在电网络的电学建模中起着重要作用，在这里，权值与导线段的电阻联系起来，以获得网络结构的电学特性。<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> 图形也用来表示多孔介质 porous media的微尺度通道，其中顶点代表孔隙，边代表连接孔隙的较小通道。'''化学图论 Chemical graph theory'''利用分子图 molecular graph来建立分子模型。图形和网络是研究和理解相变 phase transitions和临界现象 critical phenomena的优秀模型。去除节点或边会导致了临界过渡，在此过程中网络分裂成小簇，作为相变研究。分裂过程被用逾渗理论 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>

=== 社会科学 ===

=== 社会科学 ===

[[File:Moreno Sociogram 2nd Grade.png|缩略图|社会学中的图论：莫雷诺社会关系网图 Moreno Sociogram(1953)<ref>Grandjean, Martin (2015). [http://www.martingrandjean.ch/social-network-analysis-visualization-morenos-sociograms-revisited/ "Social network analysis and visualization: Moreno’s Sociograms revisited"]. Redesigned network strictly based on Moreno (1934), ''Who Shall Survive''.</ref>]]

[[File:Moreno Sociogram 2nd Grade.png|缩略图|社会学中的图论：莫雷诺社会关系网图 Moreno Sociogram(1953)<ref>Grandjean, Martin (2015). [http://www.martingrandjean.ch/social-network-analysis-visualization-morenos-sociograms-revisited/ "Social network analysis and visualization: Moreno’s Sociograms revisited"]. Redesigned network strictly based on Moreno (1934), ''Who Shall Survive''.</ref>]]

图论在'''社会学 sociology'''中也有广泛应用，例如，通过'''社会网络分析 social network analysis(SNA)'''软件来衡量演员的声望或研究谣言的传播。在社交网络领域有许多不同类型的图表。<ref>{{cite book|last=Rosen|first=Kenneth H.|title=Discrete mathematics and its applications|publisher=McGraw-Hill|location=New York|isbn=978-0-07-338309-5|edition=7th|date=2011-06-14}}</ref> 交往关系与友谊网图 Acquaintanceship and friendship graphs描述了人们是否认识彼此。影响图 Influence graphs表示某人是否可以影响他人的行为。 最后，协作图 collaboration graphs表示两个人是否以某种特定的方式一起工作，例如出演同一部电影。

图论在'''社会学 sociology'''中也有广泛应用，例如，通过社会网络分析 social network analysis(SNA)软件来衡量演员的声望或研究谣言的传播。在社交网络领域有许多不同类型的图表。<ref>{{cite book|last=Rosen|first=Kenneth H.|title=Discrete mathematics and its applications|publisher=McGraw-Hill|location=New York|isbn=978-0-07-338309-5|edition=7th|date=2011-06-14}}</ref> 交往关系与友谊网图 Acquaintanceship and friendship graphs描述了人们是否认识彼此。影响图 Influence graphs表示某人是否可以影响他人的行为。 最后，协作图 collaboration graphs表示两个人是否以某种特定的方式一起工作，例如出演同一部电影。

同样，图论在生物学和保护工作中也很有用，其中一个顶点可以代表某些物种存在（或栖息）的区域，而边则代表迁移路径或区域之间的移动。这些信息对于观察繁殖模式、跟踪疾病或寄生虫的传播及其对其他物种的影响都非常重要。

同样，图论在生物学和保护工作中也很有用，其中一个顶点可以代表某些物种存在（或栖息）的区域，而边则代表迁移路径或区域之间的移动。这些信息对于观察繁殖模式、跟踪疾病或寄生虫的传播及其对其他物种的影响都非常重要。

图论也用于'''连接组学 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> 神经系统可以看作一个图，其中节点是神经元，边是它们之间的连接。

 

图论也用于连接组学 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> 神经系统可以看作一个图，其中节点是神经元，边是它们之间的连接。

=== 数学 ===

=== 数学 ===

在数学中，图在几何学和拓扑学中'''纽结理论 knot theory'''等领域是有用的。'''代数图论 Algebraic graph theory'''与'''群论 group theory'''有着密切的联系。代数图论已被应用到动态系统和复杂性等许多领域。

在数学中，图在几何学和拓扑学中纽结理论 knot theory等领域是有用的。代数图论 Algebraic graph theory与群论 group theory有着密切的联系。代数图论已被应用到动态系统和复杂性等许多领域。

== 历史 ==

== 历史 ==

[[File:Konigsberg bridges.png|缩略图|柯尼斯堡七桥问题]]

[[File:Konigsberg bridges.png|缩略图|柯尼斯堡七桥问题]]

一般认为，'''欧拉 Leonhard Euler'''于1736年出版的关于'''柯尼斯堡七桥问题  Seven Bridges of Königsberg'''的论文是图论领域的第一篇文章。<ref name="Biggs">{{Citation|author1=Biggs, N. |author2=Lloyd, E. |author3=Wilson, R. |title=Graph Theory, 1736-1936|publisher=Oxford University Press|year=1986}}</ref> 此问题被推广为著名的欧拉路问题，亦即一笔画问题。而该论文与'''范德蒙德 Vandermonde'''的一篇关于骑士周游问题的文章，则是继承了'''莱布尼茨 Leibniz'''提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉公式与图论有密切联系，此后又被'''柯西 Cauchy'''<ref name="Cauchy">{{Citation|author=Cauchy, A. L.|year=1813|title=Recherche sur les polyèdres - premier mémoire|journal=[[Journal de l'École Polytechnique]]|volume= 9 (Cahier 16)|pages=66–86|postscript=.}}</ref>等人进一步研究推广，成了'''拓扑学 topology'''的起源。1857年，'''哈密顿 Hamilton'''发明了“环游世界游戏” icosian game，与此相关的则是另一个广为人知的图论问题“哈密顿路径问题”。

一般认为，欧拉 Leonhard Euler于1736年出版的关于'''柯尼斯堡七桥问题  Seven Bridges of Königsberg'''的论文是图论领域的第一篇文章。<ref name="Biggs">{{Citation|author1=Biggs, N. |author2=Lloyd, E. |author3=Wilson, R. |title=Graph Theory, 1736-1936|publisher=Oxford University Press|year=1986}}</ref> 此问题被推广为著名的欧拉路问题，亦即一笔画问题。而该论文与范德蒙德 Vandermonde的一篇关于骑士周游问题的文章，则是继承了莱布尼茨 Leibniz提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉公式与图论有密切联系，此后又被柯西 Cauchy<ref name="Cauchy">{{Citation|author=Cauchy, A. L.|year=1813|title=Recherche sur les polyèdres - premier mémoire|journal=[[Journal de l'École Polytechnique]]|volume= 9 (Cahier 16)|pages=66–86|postscript=.}}</ref>等人进一步研究推广，成了'''拓扑学 topology'''的起源。1857年，哈密顿 Hamilton发明了“环游世界游戏” icosian game，与此相关的则是另一个广为人知的图论问题“哈密顿路径问题”。

'''西尔维斯特 Sylvester'''于1878年发表在《自然》上的一篇论文中首次提出“图”这一术语。

西尔维斯特 Sylvester于1878年发表在《自然》上的一篇论文中首次提出“图”这一术语。

欧拉的论文发表后一个多世纪，'''凯莱 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> 由于有机化学中有许多树状结构的分子，这些研究对于理论化学有着重要意义，尤其是其中关于具有某一特定性质的图的计数问题。除凯莱的成果外，'''波利亚 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> 而图论中有一部分术语正是来源于这种将数学与化学相联系的做法。

'''四色问题 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年写给哈密顿的一封信上。包括凯莱、肯普 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。

== 图形绘制 ==

== 图形绘制 ==

'''杜特 W.T.Tutte'''的开创性工作对图形绘制学产生了重要影响。此外，他引入了使用线性代数方法绘制图形的方法。

杜特 W.T.Tutte的开创性工作对图形绘制学产生了重要影响。此外，他引入了使用线性代数方法绘制图形的方法。

图形绘制包含了处理'''交叉数 crossing number'''及其各种推广的问题。图的交叉数是一个图在平面上,边的交叉点的最小数目。对于'''平面图 planar graph'''，交叉数按定义为零。

图形绘制包含了处理交叉数 crossing number及其各种推广的问题。图的交叉数是一个图在平面上,边的交叉点的最小数目。对于'''平面图 planar graph'''，交叉数按定义为零。

对平面以外的其他表面上的绘图也有相关研究。

对平面以外的其他表面上的绘图也有相关研究。

== 图论数据结构 ==

== 图论数据结构 ==

矩阵结构包括'''关联矩阵 incidence matrix'''——一个由0和1组成的矩阵，其中行代表顶点，列代表边; 及'''邻接矩阵 adjacency matrix'''，其中的行和列都按顶点进行索引。在这两种情况下，1表示两个对象相邻，0表示两个对象不相邻。'''度矩阵 degree matrix'''表示顶点的度数。'''拉普拉斯矩阵 Laplacian Matrix'''是邻接矩阵的一种改进形式，它包含了关于顶点度的信息，并且在一些计算中很有用，例如基尔霍夫 Kirchhoff 关于图的'''生成树 spanning tree'''的定理。'''距离矩阵 distance matrix'''（如邻接矩阵）的行和列都由顶点索引，但每个单元格内不是0或1而是两个顶点之间'''最短路径 shortest path'''的长度。

矩阵结构包括'''关联矩阵 incidence matrix'''——一个由0和1组成的矩阵，其中行代表顶点，列代表边; 及'''邻接矩阵 adjacency matrix'''，其中的行和列都按顶点进行索引。在这两种情况下，1表示两个对象相邻，0表示两个对象不相邻。'''度矩阵 degree matrix'''表示顶点的度数。'''拉普拉斯矩阵 Laplacian Matrix'''是邻接矩阵的一种改进形式，它包含了关于顶点度的信息，并且在一些计算中很有用，例如基尔霍夫 Kirchhoff 关于图的'''生成树 spanning tree'''的定理。'''距离矩阵 distance matrix'''（如邻接矩阵）的行和列都由顶点索引，但每个单元格内不是0或1而是两个顶点之间'''最短路径 shortest path'''的长度。

== 图论问题 ==

== 图论问题 ==

=== 图枚举 ===

=== 图枚举 ===

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

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

* 寻找有效的算法来决定一个类的成员

* 寻找有效的算法来决定一个类的成员

* 查找类成员的表示形式 representation

* 查找类成员的表示形式 representation

== 参见 ==

== 参见 ==