万维百科

图 (数学)本文重定向自 有向图

一个有6个顶点,7条边的图

离散数学中,Graph)是用于表示物体与物体之间存在某种关系的结构。数学抽象后的“物体”称作节点顶点(英语:Vertex,node或point),节点间的相关关系则称作。在描绘一张图的时候,通常用一组点或小圆圈表示节点,其间的边则使用直线或曲线。

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

图是图论中的基本概念。1878年,詹姆斯·西尔维斯特首次使用“图”这一名词:他用图来表示数学和化学分子结构之间的关系(他称为“化学图”,英语:chemico-graphical image)。

定义

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

一张有3个节点和3条边的图

一张图(为了和有向图区分,也称无向图;为了和多重图区分,也称简单图)是一个二元组G = (V, E),其中集合V中的元素称为节点,集合E中的元素是两个节点组成的无序对,称为。集合V称为点集E称为边集

一条边上的两个节点xy称作这条边的顶点端点;也说这条边连接了节点xy,或这条边与xy关联(英语:incident)。一个节点可以不属于任何边,即它不与任何节点相连。由于是无序对,表示的是同一个元素。

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

有时,图的定义中允许自环(简称,英语:loop),即一条连接一个节点和其自身的边。允许自环的图也称为自环图

点集V一般是有限集;这意味着边集E也是有限集(不考虑多重图)。相对地,无限图英语infinite graph中的点集可以是无限的。然而,由于有限图中的结论大多不能延伸到无穷图,无穷图通常更被视为一种特殊的二元关系

一个点集为空集的图称为空图(因此边集也是空集)。图的(英语:order)是指其中节点的数量,即|V|。图的边数是指其边的数量,即|E|。图的大小size)一般也指图的边数。但在一些语境中,例如描述算法复杂度的时候,图的大小是指|V|+|E|(否则非空图的大小也有可能是0)。节点的(英语:degree或valency)是指连接到该节点的边的数量;对于允许自环的图,环要算做两条边(因为两端都连接到这个节点)。

如果一个图的阶是n,则其节点的度最大可能取n-1(对于允许自环的图则是n),而边最多可能有n(n − 1)/2条(对于允许自环的图则是n(n + 1)/2)。

在图的定义中,边的概念定义了节点上的一个对称关系,即“邻接”关系(英语:adjacency relation)。具体地说,对于两个节点xy,如果是一条边,则称它们是邻接的。一张图因此可以用其邻接矩阵A来表示,即一个的矩阵,其中每个元素Aij表示节点ij之间的边的数量。对于一个简单图,总有,分别表示“不相连”和“相连”,而(即一条边的两个顶点不能相同)。允许自环的图上的取值可以是非负整数,而多重图则允许任何的取值都是非负整数。无向图的邻接矩阵是对称阵()。

有向图

一张3个节点和4条边组成的有向图(双向箭头表示两个方向上各有一条边)

边为有方向的图称作有向图(英语:directed graphdigraph)。

有向图的一种比较严格的定义是这样的:一个二元组,其中

  • 节点的集合;
  • (也称为有向边,英语:directed edgedirected link;或,英语:arcs)的集合,其中的元素是节点的有序对。

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

在从的边 上,节点称作这条边的顶点,其中起点(英语:tail),终点。也说这条边连接了节点、这条边与节点关联。一张有向图中的节点可以不属于任何一条边。边称为边反向边

节点的出度(英语:out-degree)是指起点为该节点的边的数量;节点的入度(英语:in-degree)是指终点为该节点的边的数量。

更一般地,如果一张有向图允许多条头尾都分别相同的边,则称这样的图为有向多重图,这样的边称为多重边。一种允许多重边的的有向图定义方法如下:一个有向图是这样的三元组

  • 是节点的集合;
  • 是边的集合;
  • 是一个关联函数,将每条边映射到一个由顶点组成的有序对上(即一条边被按顺序关联到两个顶点)。

自环是指一条起点和终点相同的边。前面的两个定义都不允许自环,因为若节点上有一个自环,则边存在;但这样的边不在中。因此,如果要允许自环,则上面的定义要做修改:对于有向简单图,的定义应该修改为;对于有向多重图,的定义应该修改为。为了避免定义不清,这样的图分别称作允许自环的有向简单图允许自环的有向多重图(英语:quiver英语Quiver (mathematics))。

在允许自环的有向简单图中,边是一个上的齐次关系英语Binary relation#Homogeneous relation,称作上的邻接关系。 对于顶点是的边,我们说是彼此邻接的,记作

混合图

边既可以有向、也可以无向的图称作混合图混合简单图是一个多元组G = (V, E, A),而混合多重图则是多元组G = (V, E, A, ϕE, ϕA),其中VE(无向边集)、A(有向边集)、ϕEϕA的定义可以参考前面的无向图和有向图定义。在此定义下,有向图和无向图是混合图的特殊情况。

赋权图

一张有10个节点和12条边的赋权图

赋权图(英语:weighted graph,也称加权图网络(英语:network))是指每条边都对应有一个数字(即“权重”,weight)的图。根据具体问题,权重可以表示诸如费用、长度或容量等意义。这样的图会出现在最短路径问题旅行商问题等问题中。

基本术语

  • 子图subgraph):对于图和图,若,则称的子图。
  • 生成子图spanning subgraph):指满足条件的子图
  • (chain或walk)、轨迹(trail)、路径(path):链是顶点和边交替出现的序列称作一个长度为k的链,其中为其端点,其余顶点为内部点。所有边都不相同的链称为轨迹(简称迹)。所有顶点都不相同的轨迹称为路径(简称路)。在有向图中,若链(迹、路)的方向和其中每条边的方向一致,则称其为有向链(迹、路)。
  • 两端点相同的链和迹分别称为闭链(或环,cycle)、闭迹(或回路,circuit)。
  • 距离(Distance): 从顶点出发到顶点的最短路径若存在,则此路径的长度称作从的距离。

特殊的图

正则图

正则图是指每个节点的邻居(英语:neighbor)数量都相同的图,即每个节点的度都相同的图。节点的度为k的正则图也称作k-正则图。

完全图

一张有5个节点和10条边的完全图,其中每个节点都和所有其它节点相连。

完全图(英语:complete graph)是指每对节点之间都有一条边相连的图。一张完全图包含简单图所有可能出现的边。

有限图

有限图(英语:finite graph)是指点集和边集是有限集的图。否则,则称为无限图。在不加说明的情况下,图论中讨论的图大多是有限图。

连通图

在无向图中,如果存在xy之间的路径,则称此两节点的无序对连通的;否则,则称此两点是非联通的。

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

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

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

对于一张图,若不存在大小为k − 1的点集或边集,使得从图中移除该集合后,图就变为非连通图,则称该图是k-点连通图英语k-vertex-connected graphk-边连通图英语k-edge-connected graphk-点连通图通常也简称k-连通图。

二分图

二分图(英语:bipartite graph)是指这样的简单图:其点集可以被划分称两个集合WX,其中W中的任意两个节点之间没有边相连,X中的任意两个节点之间也没有边相连。二分图是点着色色数为2的图。

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

平面图

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

循环图

阶为n≥3循环图(英语:cycle graph)或环形图(英语:circular graph)是指其节点可以列为v1, v2, …, vn,使得图中的边为,其中i=1, 2, …, n − 1,以及。循环图的另一种定义是所有点的度都为2的连通图。如果循环图是另一个图的子图,则它是那个图中的一个

树和森林

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

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

其它特殊的图

一些进阶的特殊图包括:

例子

一张6个节点和7条边的图
  • 右边的图示是一个点集为、边集为的图。
  • 计算机科学中,有向图可以用于表示概念图有限状态自动机,以及其它许多数据结构。
  • 任意集合X上的二元关系R都可定义一个有向图。X中的元素xy有一条边,当且仅当xRy
  • 有向图可以用于表示信息网络。例如,在推特上,用户之间的关注关系可以用有向图表示。

图运算

图上可以进行一些运算或变换,使一个图变为另一个图:

图的推广

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

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

图可以看作是一种拟阵

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

计算生物学中,幂图英语power graph analysis推广了无向图的定义。

地理信息系统中,为了进行道路网络或电网的时空分析而提出的几何网络英语geometric networks的定义参考了图,并借用了许多图论的概念。

参见

脚注

  1. ^ Trudeau, Richard J. Introduction to Graph Theory Corrected, enlarged republication. New York: Dover Pub. 1993: 19 [8 August 2012]. ISBN 978-0-486-67870-2. A graph is an object consisting of two sets called its vertex set and its edge set.
  2. ^ See:
  3. ^ Gross, Jonathan L.; Yellen, Jay. Handbook of graph theory. CRC Press. 2004: 35. ISBN 978-1-58488-090-5.
  4. ^ Bender & Williamson 2010,第148页.
  5. ^ 参见 Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
  6. ^ Bender & Williamson 2010,第149页.
  7. ^ Graham et al., p. 5.
  8. ^ 8.0 8.1 Bender & Williamson 2010,第161页.
  9. ^ 徐 2004,第1页.
  10. ^ Strang, Gilbert, Linear Algebra and Its Applications 4th, Brooks Cole, 2005, ISBN 978-0-03-010567-8
  11. ^ Lewis, John, Java Software Structures 4th, Pearson: 405, 2013, ISBN 978-0133250121
  12. ^ Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne. Foundations of Discrete Mathematics International student. Boston: PWS-KENT Pub. Co. 1991: 463. ISBN 978-0-53492-373-0. A weighted graph is a graph in which a number w(e), called its weight, is assigned to each edge e.
  13. ^ 徐 2004,第20-21页.
  14. ^ Grandjean, Martin. A social network analysis of Twitter: Mapping the digital humanities community. Cogent Arts & Humanities. 2016, 3 (1): 1171458. doi:10.1080/23311983.2016.1171458可免费使用.
  15. ^ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web. doi:10.1145/2488388.2488433.

文献

  • Introduction To Graph Theory, by Gary Chartrand and Ping Zhang, McGraw Hill
  • 徐, 俊明. 图论及其应用 第二版. 合肥: 中国科学技术大学出版社. 2004. ISBN 7-312-00979-4.
  • Balakrishnan, V. K. Graph Theory 1st. McGraw-Hill. 1997. ISBN 978-0-07-005489-9.
  • Bang-Jensen, J.; Gutin, G. Digraphs: Theory, Algorithms and Applications. Springer. 2000.
  • Bender, Edward A.; Williamson, S. Gill. Lists, Decisions and Graphs. With an Introduction to Probability. 2010.
  • Berge, Claude. Théorie des graphes et ses applications. Paris: Dunod. 1958 (法语).
  • Biggs, Norman. Algebraic Graph Theory 2nd. Cambridge University Press. 1993. ISBN 978-0-521-45897-9.
  • Bollobás, Béla. Modern Graph Theory 1st. Springer. 2002. ISBN 978-0-387-98488-9.
  • Diestel, Reinhard. Graph Theory 3rd. Berlin, New York: Springer-Verlag. 2005. ISBN 978-3-540-26183-4.
  • Graham, R.L.; Grötschel, M.; Lovász, L. Handbook of Combinatorics. MIT Press. 1995. ISBN 978-0-262-07169-7.
  • Gross, Jonathan L.; Yellen, Jay. Graph Theory and Its Applications. CRC Press. 1998. ISBN 978-0-8493-3982-0.
  • Gross, Jonathan L.; Yellen, Jay. Handbook of Graph Theory. CRC. 2003. ISBN 978-1-58488-090-5.
  • Harary, Frank. Graph Theory. Addison Wesley Publishing Company. 1995. ISBN 978-0-201-41033-4.
  • Iyanaga, Shôkichi; Kawada, Yukiyosi. Encyclopedic Dictionary of Mathematics. MIT Press. 1977. ISBN 978-0-262-09016-2. 已忽略未知参数|url-access= (帮助)
  • Zwillinger, Daniel. CRC Standard Mathematical Tables and Formulae 31st. Chapman & Hall/CRC. 2002. ISBN 978-1-58488-291-6.
  • Trudeau, Richard J. Introduction to Graph Theory Corrected, enlarged republication. New York: Dover Publications. 1993 [8 August 2012]. ISBN 978-0-486-67870-2.

外部链接


本页面最后更新于2021-08-20 11:46,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器