图 - 版本历史

薄荷：/* 编辑推荐 */

2021-12-30T12:34:39Z

编辑推荐

薄荷：/* 推广 */

2021-12-30T12:33:22Z

推广

2021年12月30日 (四) 12:32 薄荷

2021-12-30T12:32:14Z

Thingamabob：创建页面，内容为“在数学中，更具体地说，在'''图论 Graph theory'''中，'''图 Graph'''是一组对象的结构，其中一些对象组在某种意义上是“相关…”

2020-10-14T13:00:04Z

创建页面，内容为“在数学中，更具体地说，在'''图论 Graph theory'''中，'''图 Graph'''是一组对象的结构，其中一些对象组在某种意义上是“相关…”

新页面

在数学中，更具体地说，在'''[[图论]] Graph theory'''中，'''图 Graph'''是一组对象的结构，其中一些对象组在某种意义上是“相关的”。这些对象在数学上对应地称为'''顶点 Vertex'''（也称为'''节点 Node'''或'''点 Point'''），顶点对间的关系称为'''边 Edge'''（也称为'''链 Link'''或'''线 Line'''）。通常，图 Graph以图解 Diagram的形式表示，一组点或圆圈表示顶点，由表示边的直线或曲线连接。图是离散数学的研究对象之一。

边可以是有向的或无向的。例如，如果用顶点表示参加某次聚会的人，两个人握手即在两顶点间建立一条边，那么我们得到的图是无向的，因为A和B握手当且仅当B也和A握手。与之相对，如果从A到B的连边表示A欠B的钱，那么我们得到的图就是有向的，因为欠钱这个关系不一定是互换的。前者称为'''无向图 Undirected graph'''，后者称为'''有向图 Directed graph'''。

图是[[图论]]研究的基本课题。 1878年，'''詹姆斯·约瑟夫·西尔维斯特 James Joseph Sylvester'''首次在这个意义上使用了“graph”一词。

==定义==
[[图论]]中的定义各不相同。下面是定义图和相关数学结构的一些较基本的方法。

===无向图===
[[File:Undirected.svg.png|缩略图|有三个顶点和三条边的图]]
图（有时称为无向图以区别于有向图，或'''简单图 Simple graph'''以区别于'''多重图 Multigraph'''）是一个有序对 <math>G(V,E)</math>，其中 <math>V</math> 是顶点集， <math>E</math> 是边集。

边 <math>(x,y)</math> 的顶点 <math>x</math> 和 <math>y</math> 称为边的'''端点 Endpoint'''。边称为连接 Join/incident on <math> x </math> 和 <math> y </math>。某顶点可能不属于任意一条边。

多重图是允许多条边连接同一对顶点的图。一些文献将多重图简单地称为图。

有时，图可以包含'''自环 loop'''，即把一个顶点与自身连接的边。为允许自环，上述定义必须将边改定义为两个顶点的'''多重集 Multiset'''。这种广义图被称为'''带自环的图 Graphs with loops'''；从上下文易看出允许自环时，也可简单称为图。

一般来说，顶点集<math>V</math>是有限的；这意味着边集也是有限的。 '''无限图 Infinite graph'''有时被认为是一种特殊的'''二元关系 Binary relation'''，因为有限图的大多数结论不能推广到无限情形，或者需要一个迥异的证明。

'''空图 Empty graph'''是顶点集为'''空集 Empty set'''（因而边集也为空）的图。图的'''阶 Order'''是其顶点数 <math>|V|</math>，图的尺寸 Size为其边数 <math>|E|</math>；然而，在某些情形下，例如为了表示算法的'''计算复杂性 Computational complexity'''，尺寸 Size大小为 <math>|V|+ | E |</math>（否则，非空图的尺寸可能为0）。顶点的'''度 Degree/valency'''是关联于该顶点的边的数目；对带自环的图，自环会被算两次。

在 <math> n </math> 阶图中，每个顶点的最大度为 <math>n-1</math>（允许自环时为 <math>n-1</math>），图的最大边数为 <math>n (n-1) / 2</math>（允许自环时为 <math>n (n+1) / 2</math>）。

图的边在顶点上定义一个对称关系 Symmetric relation，称为'''邻接关系 Adjacency relation'''。具体来说，如果 <math>(x,y)</math> 是边，两个顶点 <math>x</math> 和 <math>y</math> 是'''邻接的 Adjacent'''。

=== [[有向图]] ===
[[File:Directed.png|缩略图|有三个顶点和四条有向边的有向图（双箭头表示双指向）]]
'''有向图 Directed graph /digraph'''是边有方向的图。通常定义为一个'''有序对 Ordered pair''' <math>G=(V,E)</math>，其中
* <math>V</math> 是'''顶点 Vertex/Node/Point'''的集合；
* <math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是'''边/弧 Edge/Directed edge/Directed link/Directed line/Arrow/Arc'''的集合，边由所有不同顶点的'''有序对 Ordered pair'''构成（换句话说，边连接了顶点对）。

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

在从 <math> x </math> 指向 <math> y </math> 的边 <math>(x,y)</math> 中，顶点 <math> x </math> 和 <math> y </math> 称为边的端点 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>，其中
* <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> 是一个将每条边映射到不同顶点的一个有序对的关联函数 Incidence function（于是边连接了顶点对）。

为避免歧义，上面定义的对象可被更精准地称作'''有向多重图 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>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>。

===混合图===
'''混合图 Mixed graph'''是可能既有有向边又有无向边的图。'''混合简单图 Mixed simple graph'''为有序三元组 <math>G=(V,E,A)</math>；'''混合多重图 Mixed multigraph'''为 <math>G=(V,E,A,\phi_E,\phi_A)</math>，其中<math>V,E</math>（无向边），<math>A</math>（有向边），<math>\phi_E,\phi_A</math> 定义如上。有向图和无向图是其特殊情形。

===加权图===
[[File:Weighted graph.png|缩略图|有十个顶点和十二条边的加权图]]
'''加权图 Weighted graph'''或'''网络 Network'''是每条边都分配有一个数字（权重）的图。这种权重可能代表成本、长度或容量，这取决于要解决的问题。加权图应用广泛，如'''最短路径问题 Shortest path problem'''（举例：'''旅行推销员问题 Traveling salesman problem'''）。

==类型==
===定向图===
'''定向图 Oriented graph'''是一个边 <math>(x,y)</math> 和 <math>(y,x)</math> 中至多有一个是其边的有向图。也就是说，它可以由给无向图的每条边取定'''方向 Orientation'''而得来。不过，有些人用oriented graph来表示与directed graph相同的意思。

===正则图===
'''正则图 Regular graph'''是所有顶点的度皆相等的图。具有 <math>k</math> 度顶点的正则图称为'''k正则图 K‑regular graph/regular graph of degree k'''。

===完全图===
[[File:Complete graph.png|缩略图|有五个顶点和十条边的完全图。任一顶点到其余每个顶点都有一条边]]
'''完全图 Complete graph'''是每一对不同顶点间都有边相连的的图。一个完全图包含所有可能的边。

===有限图===
'''有限图 Finite graph'''是顶点集和边集都是'''有限集 Finite set'''的图，否则称为'''无限图 Infinite graph'''。

[[图论]]中一般认为所讨论的图都是有限的。如果图是无限的，通常会特别说明。

===连通图===
在无向图中，如果顶点的无序对 <math>(x,y)</math> 间有路径相连，则称其为'''连通的 Connected'''，否则称其'''不连通 Disconnected'''。

如果无向图中任意顶点对都是连通的，则称其为'''连通图 Connected graph'''，否则称为'''非连通图 Disconnected graph'''。

在有向图中，如果有序的顶点对 <math>(x,y)</math> 间有一条从 <math>x</math> 到 <math>y</math> 的有向路径，则称其为'''强连通的 Strongly connected'''。如果将其全部有向边替换为无向边，顶点对间有一条从 <math>x</math> 到 <math>y</math> 的无向路径，则称其为'''弱连通的 Weakly connected'''。否则，称为'''非连通的 Disconnected'''。
'''
如果一个有向图每个有序顶点对都是强连通的，则称其为'''强连通图 Strongly connected graph'''。如果其中每个有序顶点对都是弱连通的，则称之为'''弱连通图 Weakly connected graph'''。否则，称其为'''非连通图 Disconnected graph'''。

如果图中找不到任意一个含 <math>k-1</math> 个顶点或边的集合，使其在移除该集合后变为非连通的，则称其为'''k-顶点连通图 K-vertex-connected graph'''或'''k-边连通图 K-edge-connected graph'''。k-vertex-connected graph通常被简称为k-connected graph。

===二部图===
如果一个简单图的顶点集可以'''划分 Partition'''为两个集合 <math>W</math> 和 <math>X</math>，使得 <math>W</math> 中的任意两个顶点间无连边，<math>X</math> 中的任意两个顶点间无连边，则称其为'''二部图 Bipartite graph'''或'''着色数 chromatic number'''为2的图。

在'''完全二分图 Complete bipartite graph'''中，顶点集是两个不相交集 <math>W</math> 和 <math>X</math> 的并集，因此 <math>W</math> 中的每个顶点都与 <math>X</math> 中的每个顶点邻接，但 <math>W</math> 和 <math>X</math> 中没有边。

===平面图===
'''平面图 Planar graph'''是顶点和边可以画在一个平面上并且使得任意两边可以互不交叠的图。

===路图===
如果一个图的阶数大于等于2，其顶点可以以 <math>v_1,v_2,...,v_n</math> 的顺序列出，边为 <math>\{v_i,v_{i+1}\},i=1,2,...n-1</math>，则称其为'''路图 Path graph'''或'''线性图 Linear graph'''。路图是连通图，其中除两个顶点的度为1外，其余顶点的度为2。如果路图作为另一个图的'''子图 Subgraph'''，则为该图的一条'''路径 Path'''。

===圈图===
如果一个图的阶数大于等于3，其顶点可以以 <math>v_1,v_2,...,v_n</math> 的顺序列出，边为 <math>\{v_i,v_{i+1}\},i=1,2,...n-1</math>及<math>\{v_n,v_i\}</math>，则称其为'''圈图 Cycle graph'''或'''循环图 Circular graph'''。圈图是所有顶点的度均为2的连通图。如果圈图作为另一个图的子图，则为该图的一个'''圈 Cycle'''或'''回路 Circuit'''。

===树===
'''树 Tree'''是任意两个顶点恰由一条路径连接的无向图，即连通无圈无向图。

'''森林 Forest'''是任意两个顶点至多由一条路径连接的无向图，即无圈无向图，可等价为树的'''不交并 Disjoint union'''。

===多重树===
'''多重树 Polytree/Directed tree/Oriented tree/Singly connected network'''是底层无向图为树的'''有向无环图 Directed acyclic graph(DAG)'''。

'''多重森林 Polyforest/Directed forest/Oriented forest'''是底层无向图为森林的有向无环图。

===更多===
* '''佩特森图 Petersen graph'''及其推广
* '''完美图 Perfect graph'''
* '''余图 Cograph'''
* '''弦图 Chordal graph'''
* '''点传递 Vertex-transitive'''、'''弧传递 Arc-transitive'''和'''距离传递图 Distance-transitive graph'''
* '''强正则图 Strongly regular graph'''及'''距离正则图 Distance-regular graph'''

==性质==
如果图的两条边连接一个公共顶点，则称其'''邻接 Adjacent'''；有向图中，如果一条边的头是另一条边的尾，则称其'''连续 Consectuive'''。类似地，如果两个顶点共享一条公共边，则称其adjacent；如果第一个顶点是边尾，另一个顶点是边头，则称其consectuive ，此时公共边称为'''连接 Join'''两个顶点。边和边上的一个顶点称为'''关联 Incident'''。

只有一个顶点且没有边的图称为'''平凡图 Trivial graph'''。只有顶点没有边的图称为无边图 '''Edgeless graph'''。没有顶点和边的图有时被称为'''零图 Null graph'''或'''空图 Empty graph'''，但术语不一致，且并非所有的数学家都允许该对象。

通常情况下，图的顶点依据其作为集合元素的性质是可以区分的。这种图可以称为'''顶点标号图 Vertex-labeled'''。但是，对于许多问题，最好将顶点视为不可区分的。（当然，顶点仍然可以按照图本身的性质来区分，例如，按关联边的数目区分。）同样地，带有标记边的图称为'''边标号图 Edge-labeled'''。边或顶点附有标号的图一般称为'''标号图 Labeled'''。因此，顶点、边无法区分的图称为'''无标号图 Unlabeled'''。（在文献中，labeled这个术语除了用于区分不同的顶点或边外还可能适用于其他类型的标记。）

==例子==
[[File:Graphsix.png|缩略图|具有六个顶点和七条边的图]]
* 右面是图的示意。该图中，顶点为 <math>V=\{1,2,3,4,5,6\}</math>，边为 <math>E=\{\{1,2\},\{1,5\},
* \{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}</math>。
* 在计算机科学中，有向图是用来表示知识（如'''概念图 Conceptual graph'''）、'''有限状态机 Finite-state machine(FSM)'''，以及其他许多离散结构。
* 集合 <math>X</math> 中的'''二元关系 Binary relation''' <math>R</math> 定义了一个有向图。<math>X</math> 的元素 <math>x</math> 是元素 <math>y</math> 的'''直接前继 Predecessor'''当且仅当 <math>xRy</math>。
* 有向图可以为信息网络建模，如'''推特 Twitter'''。
* 有限生成群的'''凯莱图 Cayley graph'''和'''施赖埃尔陪集图 Schreier coset graph'''给出了有向图的特例。
* 在'''范畴论 Category theory'''中，每一个小'''范畴 Category'''都有一个基本的有向多重图，其顶点是范畴的对象，其边是范畴的弧。在范畴论的语言中，可以说从'''小范畴 Category of small categories'''到箭图的范畴有一个'''遗忘函子 Forgetful functor'''。

==运算操作==
有一些操作可以从最初的图中生成新图，这些图形可以分为以下几类：

一元操作：从一个初始图形中创建新图，如
* '''边收缩 Edge contraction'''
* '''线图 Line graph'''
* '''对偶图 Dual graph'''
* '''补图 Complement graph'''
* '''图重写 Graph rewriting'''

二元操作：从两个初始图形中创建新图，如
* '''图的不交并 Disjoint union of graphs'''
* '''图的笛卡儿积 Cartesian product of graphs'''
* '''图的张量积 Tensor product of graphs'''
* '''图的强积 Strong product of graphs'''
* '''图的字典积 Lexicographic product of graphs'''
* '''系列平行图 Series-parallel graph'''

==推广==
在'''超图 Hypergraph'''中，一条边可以连接两个以上顶点。

一个无向图可以看作是由1- '''单纯形 Simplex'''（边）和0- 单纯形（顶点）组成的'''单纯复形 Simplicial complex'''。由此可见，复形是图的推广，因为它们允许更高维的单纯形。

每个图都可以得到一个'''拟阵 Matroid'''。

在'''模型论 Model theory'''中，图仅仅是一个'''结构 Structure'''。但是在这种情形下，边的数目是没有限制的：它可以是任意'''基数 Cardinal number'''，见[https://en.wikipedia.org/wiki/Graphon Graphon]。

在'''计算生物学 Computational biology'''中，'''幂图分析 Power graph analysis'''引入'''幂图 Power graph'''作为无向图的另一种表示方式。

在'''地理信息系统 Geographic information system(GIS)'''中，'''几何网络 Geometric network'''密切模仿图，并借用[[图论]]中的许多概念对道路网络或公用网络进行空间分析。

'''''本中文词条由Dorr用户参与编译，xx审校，欢迎在讨论页面留言。'''''

'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[Category:旧词条迁移]]

@@ 第173行： / 第173行： @@
 <br/>
 ====[https://vdisk.weibo.com/s/dDPmAoC9qB694  《图论及其应用》]====
 该书籍主要介绍了图论的基本知识、相关定理等，并对于不同图，给出实际应用，如与对集有关的人员分派问题、与Hamilton图有关的旅行售货员问题等，通俗易懂。
 </br>
 ===集智文章推荐===
-====集智俱乐部：[https://swarma.org/?p=1113 种群结构如何影响自然选择？ | 图论对进化生物学的启发] ====
+*集智俱乐部：[https://swarma.org/?p=1113 种群结构如何影响自然选择？ | 图论对进化生物学的启发]
+*集智斑图：[https://pattern.swarma.org/paper?id=d25fb568-16f8-11ea-91b3-0242ac1a0005 Graph theory in the information age 信息时代的图论]
+*集智斑图：[https://pattern.swarma.org/paper?id=24dc7004-2808-11ea-a1e5-0242ac1a0007 Graph Theory and Metro Traffic Modelling 图论与地铁交通模型]
 </br>
@@ 第200行： / 第193行： @@
 ====[https://campus.swarma.org/course/1790 书籍领读：图论]====
 本课程中，将讲解巴拉巴西网络科学书籍第一章图论。
 <br/>
 '''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''

@@ 第166行： / 第166行： @@
 在'''地理信息系统 Geographic information system(GIS)'''中，'''几何网络 Geometric network'''密切模仿图，并借用[[图论]]中的许多概念对道路网络或公用网络进行空间分析。
 ====《图论导论》====
 Douglas B．West教授是伊利诺伊大学数学系的资深教授，长期从事图论理论和组合优化方面的研究工作，发表了100多篇论文。本书旨在介绍图论的基本概念、基本定理和算法，帮助读者理解并掌握图的结构和解决图论问题的技巧。另外，本书包含很多图论的新研究结果，并介绍了一些悬而未决的图论问题．证明与应用并举是本书的一个重要特点。
@@ 第175行： / 第178行： @@
 </br>
 ===集智文章推荐===

@@ 第1行： / 第1行： @@
-在数学中，更具体地说，在'''[[图论]] Graph theory'''中，'''图 Graph'''是一组对象的结构，其中一些对象组在某种意义上是“相关的”。这些对象在数学上对应地称为'''顶点 Vertex'''（也称为'''节点 Node'''或'''点 Point'''），顶点对间的关系称为'''边 Edge'''（也称为'''链 Link'''或'''线 Line'''）。通常，图 Graph以图解 Diagram的形式表示，一组点或圆圈表示顶点，由表示边的直线或曲线连接。图是离散数学的研究对象之一。
+{{#seo:
 边可以是有向的或无向的。例如，如果用顶点表示参加某次聚会的人，两个人握手即在两顶点间建立一条边，那么我们得到的图是无向的，因为A和B握手当且仅当B也和A握手。与之相对，如果从A到B的连边表示A欠B的钱，那么我们得到的图就是有向的，因为欠钱这个关系不一定是互换的。前者称为'''无向图 Undirected graph'''，后者称为'''有向图 Directed graph'''。
@@ 第160行： / 第165行： @@
 在'''地理信息系统 Geographic information system(GIS)'''中，'''几何网络 Geometric network'''密切模仿图，并借用[[图论]]中的许多概念对道路网络或公用网络进行空间分析。
 '''''本中文词条由Dorr用户参与编译，xx审校，欢迎在讨论页面留言。'''''
 '''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''