图 (数学)

在离散数学中，图（Template:Lang-en）是用于表示物体与物体之间存在某种关系的结构。数学抽象后的“物体”称作节点或顶点（Template:Lang），节点间的相关关系则称作边。^[1]在描绘一张图的时候，通常用一组点或小圆圈表示节点，其间的边则使用直线或曲线。

图中的边可以是有方向或没有方向的。例如在一张图中，如果节点表示聚会上的人，而边表示两人曾经握手，则该图就是没有方向的，因为甲和乙握过手也意味着乙一定和甲握过手。相反，如果一条从甲到乙的边表示甲欠乙的钱，则该图就是有方向的，因为“曾经欠钱”这个关系不一定是双向的。前一种图称为无向图，后一种称为有向图。

图是图论中的基本概念。1878年，詹姆斯·西尔维斯特首次使用“图”这一名词：他用图来表示数学和化学分子结构之间的关系（他称为“化学图”，Template:Lang-en）。^[2]^[3]

定义

在图论中，图的定义有很多。下面是一些比较基本的定义方式以及与它们相关的数学结构。

Template:Anchor 图

一张图（为了和有向图区分，也称无向图；为了和多重图区分，也称简单图）Template:Sfn^[4]是一个二元组 Template:Math，其中集合Template:Mvar中的元素称为节点，集合Template:Mvar中的元素是两个节点组成的无序对，称为边。集合Template:Mvar称为点集，Template:Mvar称为边集。

一条边 ${x, y}$ 上的两个节点Template:Math和Template:Math称作这条边的顶点或端点；也说这条边连接了节点Template:Math和Template:Math，或这条边与Template:Math和Template:Math关联（Template:Lang-en）。一个节点可以不属于任何边，即它不与任何节点相连。由于 ${x, y}$ 是无序对， ${x, y}$ 和 ${y, x}$ 表示的是同一个元素。

更一般地，多重图的定义中允许同一对节点之间存在多条不同的边。在特定语境中，多重图也可以直接称作图。Template:Sfn^[5]此时，在上面的定义中，集合E应该为多重集。

有时，图的定义中允许自环（简称环，Template:Lang-en），即一条连接一个节点和其自身的边。允许自环的图也称为自环图。

点集V一般是有限集；这意味着边集E也是有限集（不考虑多重图）。相对地，Template:Tsl中的点集可以是无限的。然而，由于有限图中的结论大多不能延伸到无穷图，无穷图通常更被视为一种特殊的二元关系。

一个点集为空集的图称为空图（因此边集也是空集）。图的阶（Template:Lang-en）是指其中节点的数量，即Template:Math。图的边数是指其边的数量，即Template:Math。图的大小（Template:Lang）一般也指图的边数。但在一些语境中，例如描述算法复杂度的时候，图的大小是指Template:Math（否则非空图的大小也有可能是0）。节点的度（Template:Lang-en）是指连接到该节点的边的数量；对于允许自环的图，环要算做两条边（因为两端都连接到这个节点）。

如果一个图的阶是Template:Math，则其节点的度最大可能取Template:Math（对于允许自环的图则是Template:Math），而边最多可能有Template:Math条(对于允许自环的图则是Template:Math）。

在图的定义中，边的概念定义了节点上的一个对称关系，即“邻接”关系（Template:Lang-en）。具体地说，对于两个节点Template:Math和Template:Math，如果 ${x, y}$ 是一条边，则称它们是邻接的。一张图因此可以用其邻接矩阵A来表示，即一个 $n \times n$ 的矩阵，其中每个元素A_ij表示节点i和j之间的边的数量。对于一个简单图，总有 $A_{i j} \in {0, 1}$ ，分别表示“不相连”和“相连”，而 $A_{i i} = 0$ （即一条边的两个顶点不能相同）。允许自环的图上 $A_{i i}$ 的取值可以是非负整数，而多重图则允许任何 $A_{i j}$ 的取值都是非负整数。无向图的邻接矩阵是对称阵（ $A_{i j} = A_{j i}$ ）。

有向图

Template:Main

边为有方向的图称作有向图（Template:Lang-en）。

有向图的一种比较严格的定义Template:Sfn是这样的：一个二元组 $G = (V, E)$ ，其中

$V$ 是节点的集合；
$E \subseteq {(x, y) ∣ (x, y) \in V^{2} \land x \neq y}$ 是边（也称为有向边，Template:Lang-en；或弧，Template:Lang-en）的集合，其中的元素是节点的有序对。

为了和多重图区分，这样的有向图也称为有向简单图。

在从 $x$ 到 $y$ 的边 $(x, y)$ 上，节点 $x$ 和 $y$ 称作这条边的顶点，其中 $x$ 是起点或尾（Template:Lang-en）， $y$ 是终点或头。Template:Sfn也说这条边连接了节点 $x$ 和 $y$ 、这条边与节点 $x$ 和 $y$ 关联。一张有向图中的节点可以不属于任何一条边。边 $(y, x)$ 称为边 $(x, y)$ 的反向边。

节点的出度（Template:Lang-en）是指起点为该节点的边的数量；节点的入度（Template:Lang-en）是指终点为该节点的边的数量。

更一般地，如果一张有向图允许多条头尾都分别相同的边，则称这样的图为有向多重图，这样的边称为多重边。一种允许多重边的有向图定义方法如下Template:Sfn：一个有向图是这样的三元组 $G = (V, E, ϕ)$ ：

$V$ 是节点的集合；
$E$ 是边的集合；
$ϕ : E \to {(x, y) ∣ (x, y) \in V^{2} \land x \neq y}$ 是一个关联函数，将每条边映射到一个由顶点组成的有序对上（即一条边被按顺序关联到两个顶点）。

自环是指一条起点和终点相同的边。前面的两个定义都不允许自环，因为若节点 $x$ 上有一个自环，则边 $(x, x)$ 存在；但这样的边不在 ${(x, y) ∣ (x, y) \in V^{2} \land x \neq y}$ 中。因此，如果要允许自环，则上面的定义要做修改：对于有向简单图， $E$ 的定义应该修改为 $E \subseteq {(x, y) ∣ (x, y) \in V^{2}}$ ；对于有向多重图， $ϕ$ 的定义应该修改为 $ϕ : E \to {(x, y) ∣ (x, y) \in V^{2}}$ 。为了避免定义不清，这样的图分别称作允许自环的有向简单图或允许自环的有向多重图（Template:Lang-en）。

在允许自环的有向简单图 $G$ 中，边是 $V$ 上的一个Template:Tsl $\sim$ ，称作 $G$ 上的邻接关系。对于顶点是 $x$ 和 $y$ 的边 $(x, y)$ ，我们说 $x$ 和 $y$ 是彼此邻接的，记作 $x \sim y$ 。

混合图

Template:Main 边既可以有向、也可以无向的图称作混合图。混合简单图是一个多元组Template:Nowrap，而混合多重图则是多元组Template:Nowrap，其中V、E（无向边集）、A（有向边集）、ϕ_E、ϕ_A的定义可以参考前面的无向图和有向图定义。在此定义下，有向图和无向图是混合图的特殊情况。

赋权图

赋权图（Template:Lang-en，也称加权图、网络（Template:Lang-en））^[6]^[7]是指每条边都对应有一个数字（即“权重”，Template:Lang）的图。^[8]根据具体问题，权重可以表示诸如费用、长度或容量等意义。这样的图会出现在最短路径问题和旅行商问题等问题中。

基本术语

Template:Main

子图（Template:Lang）：对于圖 $G$ 和图 $G^{'}$ ，若 $V (G^{'}) \subseteq V (G)$ 且 $E (G^{'}) \subseteq E (G)$ ，则称 $G^{'}$ 是 $G$ 的子图。
生成子图（Template:Lang）：指满足条件 $V (G^{'}) = V (G)$ 的 $G$ 的子图 $G^{'}$ 。
链(Template:Lang)、轨迹(Template:Lang)、路径(Template:Lang)：链是顶点 $v_{i}$ 和边 $e_{i}$ 交替出现的序列 $W = v_{i_{0}} e_{i_{0}} v_{i_{1}} . . . e_{i_{k}} v_{i_{k}}$ 称作一个长度为k的链，其中 $v_{i_{0}}$ 和 $v_{i_{k}}$ 为其端点，其余顶点为内部点。所有边都不相同的链称为轨迹（简称迹）。所有顶点都不相同的轨迹称为路径（简称路）。在有向图中，若链（迹、路）的方向和其中每条边的方向一致，则称其为有向链（迹、路）。Template:Sfn
两端点相同的链和迹分别称为闭链（或环，Template:Lang）、闭迹（或回路，Template:Lang）。
距離（Distance）：从頂點 $u$ 出發到頂點 $v$ 的最短路徑若存在，則此路徑的長度稱作從 $u$ 到 $v$ 的距離。

特殊的图

正则图

Template:Main 正则图是指每个节点的邻居（Template:Lang-en）数量都相同的图，即每个节点的度都相同的图。节点的度为k的正则图也称作k-正则图。

完全图

Template:Main

完全图（Template:Lang-en）是指每对节点之间都有一条边相连的图。一张完全图包含简单图所有可能出现的边。

有限图

有限图（Template:Lang-en）是指点集和边集是有限集的图。否则，则称为无限图。在不加说明的情况下，图论中讨论的图大多是有限图。

连通图

Template:Main 在无向图中，如果存在x和y之间的路径，则称此两节点的无序对 ${x, y}$ 是连通的；否则，则称此两点是非联通的。

连通图是指每对节点都连通的无向图。否则，则称图是非连通图。

在有向图中，如果存在x和y之间的有向路径，则称此两节点的有序对 ${x, y}$ 是强连通的。此外，若将图中的所有边都换为无向边，得到的无向图中存在x和y之间的路径，则称此两节点是弱连通的。否则，则称此两点是非联通的。

强连通图是指每对节点都强连通的有向图。此外，弱连通图是指每对节点都弱联通的有向图。否则，则称图是非连通图。

对于一张图，若不存在大小为Template:Nowrap的点集或边集，使得从图中移除该集合后，图就变为非连通图，则称该图是Template:Tsl或Template:Tsl。k-点连通图通常也简称k-连通图。

二分图

Template:Main 二分图（Template:Lang-en）是指这样的简单图：其点集可以被划分称两个集合W和X，其中W中的任意两个节点之间没有边相连，X中的任意两个节点之间也没有边相连。二分图是点着色色数为2的图。

若一张图的点集是两个集合W和X的无交并，使得W中的任意节点都和X中的所有节点邻接，且W或X之内没有边，则称此图是完全二分图。

平面图

Template:Main 平面图是指可以将其节点和边画在平面上，而没有两边相交的图。

循环图

Template:Main 阶为Template:Nowrap的循环图（Template:Lang-en）或环形图（Template:Lang-en）是指其节点可以列为v₁, v₂, …, v_n，使得图中的边为 ${v_{i}, v_{i + 1}}$ ，其中i=1, 2, …, n − 1，以及 ${v_{n}, v_{1}}$ 。循环图的另一种定义是所有点的度都为2的连通图。如果循环图是另一个图的子图，则它是那个图中的一个环。

树和森林

Template:Main 树是指任意两点之间都有且仅有一条路径的无向图。等价地，树是一个连通无环无向图。

森林是指任意两点之间至多仅有一条路径的无向图。等价地，森林是一个无环无向图，或一组树的无交并。

其它特殊的图

一些进阶的特殊图包括：

例子

右边的图示是一个点集为 $V = {1, 2, 3, 4, 5, 6}$ 、边集为 $E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {4, 5}, {4, 6}}$ 的图。
在计算机科学中，有向图可以用于表示Template:Tsl、有限状态自动机，以及其它许多数据结构。
任意集合X上的二元关系R都可定义一个有向图。X中的元素x到y有一条边，当且仅当xRy。
有向图可以用于表示信息网络。例如，在推特上，用户之间的关注关系可以用有向图表示。^[9]^[10]

图运算

Template:Main 图上可以进行一些运算或变换，使一个图变为另一个图：

一元运算，将一个图变换为另一个图，例如：
- 边收缩，
- 线图，
- 对偶图，
- 补图；
二元运算，结合两个图为一个新图，例如：
- Template:Tsl，
- 图乘积，包括Template:Tsl、Template:Tsl、Template:Tsl、图的字典积等，
- Template:Tsl等。

图的推广

在超图中，允许一条边连接多于两个节点。

无向图可以看作是由1-单纯形（边）和0-单纯形（节点）组成的单纯复形。由此，复形成为图的推广，其中允许维度更高的单纯形。

图可以看作是一种拟阵。

在模型论中，图是一个结构。这样一来，边的数量可以是任意基数。参见图极限。

在计算生物学中，Template:Tsl推广了无向图的定义。

在地理信息系统中，为了进行道路网络或电网的时空分析而提出的Template:Tsl的定义参考了图，并借用了许多图论的概念。

参见

参考资料

脚注

Template:Reflist

文献

Introduction To Graph Theory, by Gary Chartrand and Ping Zhang, McGraw Hill
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book
Template:Cite book

外部链接

Template:Portal box

Template:- Template:图论

↑ Template:Cite book
↑
See:
- J. J. Sylvester (February 7, 1878) "Chemistry and algebra," Template:Wayback Nature, 17 : 284. Template:Doi. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."
- J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices," Template:Wayback American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. Template:Doi. Template:JSTOR. The term "graph" first appears in this paper on page 65.
↑ Template:Cite book
↑ 参见 Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
↑ Graham et al., p. 5.
↑ Template:Citation
↑ Template:Citation
↑ Template:Cite book
↑ Template:Cite journal
↑ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter Template:Wayback, Proceedings of the 22nd international conference on World Wide Web. Template:Doi.

[:0-1] Template:Cite book

[2] See:
J. J. Sylvester (February 7, 1878) "Chemistry and algebra," Template:Wayback Nature, 17 : 284. Template:Doi. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."

J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices," Template:Wayback American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. Template:Doi. Template:JSTOR. The term "graph" first appears in this paper on page 65.

[3] J. J. Sylvester (February 7, 1878) "Chemistry and algebra," Template:Wayback Nature, 17 : 284. Template:Doi. From page 284: "Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph."

[4] J. J. Sylvester (1878) "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices," Template:Wayback American Journal of Mathematics, Pure and Applied, 1 (1) : 64–90. Template:Doi. Template:JSTOR. The term "graph" first appears in this paper on page 65.

[3] Template:Cite book

[4] 参见 Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.

[5] Graham et al., p. 5.

[6] Template:Citation

[7] Template:Citation

[8] Template:Cite book

[snatwitter-9] Template:Cite journal

[twitterwtf-10] Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter Template:Wayback, Proceedings of the 22nd international conference on World Wide Web. Template:Doi.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

图 (数学)

目录

定义

Template:Anchor 图

有向图

混合图

赋权图

基本术语

特殊的图

正则图

完全图

有限图

连通图

二分图

平面图

循环图

树和森林

其它特殊的图

例子

图运算

图的推广

参见

参考资料

脚注

文献

外部链接

导航菜单

图 (数学)

定义

Template:Anchor 图

有向图

混合图

赋权图

基本术语

特殊的图

正则图

完全图

有限图

连通图

二分图

平面图

循环图

树和森林

其它特殊的图

例子

图运算

图的推广

参见

参考资料

脚注

文献

外部链接

导航菜单

搜索