查看“︁图 (数学)”︁的源代码

{{about|圖論中的基本研究對象|數學函數的圖|函数图形|抽象数据类型|图 (数据结构)|其他主題|图}}

[[File:6n-graf.svg|thumb|一個有6個頂點，7条邊的圖]]

在[[离散数学]]中，'''图'''（{{lang-en|graph}}）是用于表示物体与物体之间存在某种关系的结构。数学抽象后的“物体”称作'''节点'''或'''顶点'''（{{lang|en|vertex, node, point}}），节点间的相关关系则称作'''[[边 (图论)|边]]'''。<ref name=":0">{{cite book|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory|year=1993|publisher=Dover Pub.|location=New York|isbn=978-0-486-67870-2|pages=19|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|access-date=8 August 2012|quote=A graph is an object consisting of two sets called its ''vertex set'' and its ''edge set''.|archive-date=2019-05-05|archive-url=https://web.archive.org/web/20190505192352/http://store.doverpublications.com/0486678709.html|dead-url=no}}</ref>在[[图解|描绘]]一张图的时候，通常用一组点或小圆圈表示节点，其间的边则使用直线或曲线。

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

图是[[图论]]中的基本概念。1878年，[[詹姆斯·约瑟夫·西尔维斯特|詹姆斯·西尔维斯特]]首次使用“图”这一名词：他用图来表示数学和化学[[分子结构]]之间的关系（他称为“化学图”，{{lang-en|chemico-graphical image}}）。<ref>See:
* J. J. Sylvester (February 7, 1878) [https://books.google.com/books?id=KcoKAAAAYAAJ&vq=Sylvester&pg=PA284#v=onepage&q&f=false "Chemistry and algebra,"] {{Wayback|url=https://books.google.com/books?id=KcoKAAAAYAAJ&vq=Sylvester&pg=PA284#v=onepage&q&f=false |date=20200605015604 }} ''Nature'', ''17'' : 284. {{doi|10.1038/017284a0}}. 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) [https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64#v=onepage&q&f=false "On an application of the new atomic theory to the graphical representation of the invariants and covariants of binary quantics, – with three appendices,"] {{Wayback|url=https://books.google.com/books?id=1q0EAAAAYAAJ&pg=PA64#v=onepage&q&f=false |date=20200605002854 }} ''American Journal of Mathematics, Pure and Applied'', ''1'' (1) : 64–90. {{doi|10.2307/2369436}}. {{JSTOR|2369436}}. The term "graph" first appears in this paper on page 65.</ref><ref>{{Cite book
 | title = Handbook of graph theory
 | first1 = Jonathan L.
 | last1 = Gross
 | first2 = Jay
 | last2 = Yellen
 | publisher = [[CRC Press]]
 | year = 2004
 | page = [https://books.google.com/books?id=mKkIGIea_BkC&pg=PA35&lpg=PA35 35]
 | isbn = 978-1-58488-090-5
 | url = https://books.google.com/books?id=mKkIGIea_BkC
 | access-date = 2021-08-14
 | archive-date = 2021-08-14
 | archive-url = https://web.archive.org/web/20210814001706/https://books.google.com/books?id=mKkIGIea_BkC
 | dead-url = no
 }}</ref>

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

=== {{anchor|无向图}} 图===
[[File:Undirected.svg|thumb|一张有3个节点和3条边的图]]
一张图（为了和[[#有向图|'''有向图''']]区分，也称'''无向图'''；为了和[[多重图]]区分，也称'''简单图'''）{{sfn|Bender|Williamson|2010|p=148}}<ref>参见 Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.</ref>是一个[[有序对|二元组]]{{math|1=''G'' = (''V'', ''E'')}}，其中集合{{mvar|V}}中的元素称为'''节点'''，集合{{mvar|E}}中的元素是两个节点组成的无序对，称为'''边'''。集合{{mvar|V}}称为'''点集'''，{{mvar|E}}称为'''边集'''。

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

更一般地，[[多重图]]的定义中允许同一对节点之间存在多条不同的边。在特定语境中，多重图也可以直接称作图。{{sfn|Bender|Williamson|2010|p=149}}<ref>Graham et al., p. 5.</ref>此时，在上面的定义中，集合''E''应该为[[多重集]]。

有时，图的定义中允许'''自环'''（简称'''环'''，{{lang-en|{{tsl|en|loop (graph theory)|loop}}}}），即一条连接一个节点和其自身的边。允许自环的图也称为'''自环图'''。

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

一个点集为[[空集]]的图称为[[空图]]（因此边集也是空集）。图的'''阶'''（{{lang-en|order}}）是指其中节点的数量，即{{math|{{abs|''V''}}}}。图的'''边数'''是指其边的数量，即{{math|{{abs|''E''}}}}。图的'''大小'''（{{lang|en|size}}）一般也指图的边数。但在一些语境中，例如描述[[计算复杂性理论|算法复杂度]]的时候，图的大小是指{{math|{{abs|''V''}}+{{abs|''E''}}}}（否则非空图的大小也有可能是0）。节点的'''度'''（{{lang-en|degree或valency}}）是指连接到该节点的边的数量；对于允许自环的图，环要算做两条边（因为两端都连接到这个节点）。

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

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

=== 有向图 ===
{{main|有向图}}
[[File:Directed.svg|thumb|一张3个节点和4条边组成的有向图（双向箭头表示两个方向上各有一条边）]]

边为有方向的图称作'''有向图'''（{{lang-en|'''directed graph'''或'''digraph'''}}）。

有向图的一种比较严格的定义{{sfn|Bender|Williamson|2010|p=161}}是这样的：一个二元组<math>G=(V,E)</math>，其中
* <math>V</math>是'''节点'''的集合；
* <math>E \subseteq \{(x,y) \mid (x,y) \in V^2 \wedge x \neq y \}</math>是'''边'''（也称为''有向边''，{{lang-en|'''directed edge'''或'''directed link'''}}；或'''弧'''，{{lang-en|'''arcs'''}}）的集合，其中的元素是节点的有序对。
为了和多重图区分，这样的有向图也称为'''有向简单图'''。

在从<math>x</math>到<math>y</math>的边<math>(x,y)</math> 上，节点<math>x</math>和<math>y</math>称作这条边的'''顶点'''，其中<math>x</math>是'''起点'''或'''尾'''（{{lang-en|tail}}），<math>y</math>是'''终点'''或'''头'''。{{sfn|徐|2004|p=1}}也说这条边'''连接'''了节点<math>x</math>和<math>y</math>、这条边与节点<math>x</math>和<math>y</math>'''关联'''。一张有向图中的节点可以不属于任何一条边。边<math>(y,x)</math>称为边<math>(x,y)</math>的'''反向边'''。

节点的'''出度'''（{{lang-en|out-degree}}）是指起点为该节点的边的数量；节点的'''入度'''（{{lang-en|in-degree}}）是指终点为该节点的边的数量。

更一般地，如果一张有向图允许多条头尾都分别相同的边，则称这样的图为'''有向多重图'''，这样的边称为'''[[多重边]]'''。一种允许多重边的有向图定义方法如下{{sfn|Bender|Williamson|2010|p=161}}：一个'''有向图'''是这样的[[多元组|三元组]]<math>G=(V,E,\phi)</math>：
* <math>V</math>是节点的集合；
* <math>E</math>是边的集合；
* <math>\phi : E \to \{(x,y) \mid (x,y) \in V^2 \wedge x \neq y \}</math>是一个'''关联函数'''，将每条边映射到一个由顶点组成的有序对上（即一条边被按顺序关联到两个顶点）。

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

在允许自环的有向简单图<math>G</math>中，边是<math>V</math>上的一个{{tsl|en|Binary relation#Homogeneous relation|homogeneous relation|齐次关系}}<math>\sim</math>，称作<math>G</math>上的'''邻接关系'''。 
对于顶点是<math>x</math>和<math>y</math>的边<math>(x,y)</math>，我们说<math>x</math>和<math>y</math>是彼此'''邻接'''的，记作<math>x\sim y</math>。

===混合图===
{{main|混合图}}
边既可以有向、也可以无向的图称作'''混合图'''。'''混合简单图'''是一个多元组{{nowrap|1=''G'' = (''V'', ''E'', ''A'')}}，而'''混合多重图'''则是多元组{{nowrap|1=''G'' = (''V'', ''E'', ''A'', ''ϕ''<sub>''E''</sub>, ''ϕ''<sub>''A''</sub>)}}，其中''V''、''E''（无向边集）、''A''（有向边集）、''ϕ''<sub>''E''</sub>、''ϕ''<sub>''A''</sub>的定义可以参考前面的无向图和有向图定义。在此定义下，有向图和无向图是混合图的特殊情况。

===赋权图===
[[File:Weighted_network.png|thumb|一张有10个节点和12条边的赋权图]]

'''赋权图'''（{{lang-en|weighted graph}}，也称'''加权图'''、'''网络'''（{{lang-en|network}}））<ref>{{Citation | last=Strang | first=Gilbert | title=Linear Algebra and Its Applications | publisher=Brooks Cole | edition=4th | year=2005 | isbn=978-0-03-010567-8 | url=https://books.google.com/books?vid=ISBN0030105676 | accessdate=2021-08-14 | archive-date=2020-09-20 | archive-url=https://web.archive.org/web/20200920205035/https://books.google.com/books?vid=ISBN0030105676 | dead-url=no }}</ref><ref>{{Citation | last=Lewis | first=John | title=Java Software Structures | publisher=Pearson | edition=4th | year=2013 | isbn=978-0133250121 | page=405 }}</ref>是指每条边都对应有一个数字（即“权重”，{{lang|en|weight}}）的图。<ref>{{cite book|last1=Fletcher|first1=Peter|last2=Hoyle|first2=Hughes|last3=Patty|first3=C. Wayne|title=Foundations of Discrete Mathematics|url=https://archive.org/details/foundationsofdis0000flet|year=1991|publisher=PWS-KENT Pub. Co.| location=Boston| isbn=978-0-53492-373-0| pages=[https://archive.org/details/foundationsofdis0000flet/page/463 463] | edition=International student|quote=A ''weighted graph'' is a graph in which a number ''w(e)'', called its ''weight'', is assigned to each edge ''e''.}}</ref>根据具体问题，权重可以表示诸如费用、长度或容量等意义。这样的图会出现在[[最短路径问题]]和[[旅行商问题]]等问题中。

==基本术语==
{{Main|图论术语}}

* '''子图'''（{{lang|en|subgraph}}）：对于圖<math>G</math>和图<math>G'</math>，若<math>V(G')\subseteq V(G)</math>且<math>E(G')\subseteq E(G)</math>，则称<math>G'</math>是<math>G</math>的子图。
* '''生成子图'''（{{lang|en|spanning subgraph}}）：指满足条件<math>V(G')=V(G)</math>的<math>G</math>的子图<math>G'</math>。
* '''链'''({{lang|en|chain或walk}})、'''轨迹'''({{lang|en|trail}})、'''路径'''({{lang|en|path}})：链是顶点<math>v_i</math>和边<math>e_i</math>交替出现的序列<math>W=v_{i_0}e_{i_0}v_{i_1}...e_{i_k}v_{i_k}</math>称作一个长度为''k''的链，其中<math>v_{i_0}</math>和<math>v_{i_k}</math>为其端点，其余顶点为内部点。所有边都不相同的链称为轨迹（简称迹）。所有顶点都不相同的轨迹称为路径（简称路）。在有向图中，若链（迹、路）的方向和其中每条边的方向一致，则称其为有向链（迹、路）。{{sfn|徐|2004|p=20-21}}
* 两端点相同的链和迹分别称为闭链（或环，{{lang|en|cycle}}）、闭迹（或回路，{{lang|en|circuit}}）。
* '''距離'''（Distance）： 从頂點<math>u</math>出發到頂點<math>v</math>的最短路徑若存在，則此路徑的長度稱作從<math>u</math>到<math>v</math>的距離。

==特殊的图==
=== 正则图 ===
{{main|正则图}}
'''正则图'''是指每个节点的'''邻居'''（{{lang-en|neighbor}}）数量都相同的图，即每个节点的度都相同的图。节点的度为''k''的正则图也称作''k''-正则图。

=== 完全图 ===
{{main|完全图}}
[[File:Complete graph K5.svg|thumb|125px|一张有5个节点和10条边的完全图，其中每个节点都和所有其它节点相连。]]

'''完全图'''（{{lang-en|complete graph}}）是指每对节点之间都有一条边相连的图。一张完全图包含简单图所有可能出现的边。

=== 有限图 ===
'''有限图'''（{{lang-en|finite graph}}）是指点集和边集是[[有限集]]的图。否则，则称为'''无限图'''。在不加说明的情况下，图论中讨论的图大多是有限图。

=== 连通图 ===
{{main|连通图|{{tsl|en|Connectivity (graph theory)|连通度}}}}
在无向图中，如果存在''x''和''y''之间的[[道路 (图论)|路径]]，则称此两节点的无序对<math>\{x, y\}</math>是'''连通'''的；否则，则称此两点是'''非联通'''的。

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

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

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

对于一张图，若不存在大小为{{nowrap|''k'' − 1}}的点集或边集，使得从图中移除该集合后，图就变为非连通图，则称该图是'''{{tsl|en|k-vertex-connected graph|k-点连通图|''k''-点连通图}}'''或'''{{tsl|en|k-edge-connected graph|k-边连通图|''k''-边连通图}}'''。''k''-点连通图通常也简称''k''-连通图。

=== 二分图 ===
{{main|二分图}}
'''二分图'''（{{lang-en|bipartite graph}}）是指这样的简单图：其点集可以被[[集合划分|划分]]称两个集合''W''和''X''，其中''W''中的任意两个节点之间没有边相连，''X''中的任意两个节点之间也没有边相连。二分图是[[图着色问题|点着色]]色数为2的图。

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

=== 平面图 ===
{{main|平面图 (图论)}}
'''平面图'''是指可以将其节点和边画在平面上，而没有两边相交的图。

=== 循环图 ===
{{main|循环图}}
阶为{{nowrap|''n''≥3}}的'''循环图'''（{{lang-en|cycle graph}}）或'''环形图'''（{{lang-en|circular graph}}）是指其节点可以列为''v''<sub>1</sub>, ''v''<sub>2</sub>, …, ''v''<sub>''n''</sub>，使得图中的边为<math>\{v_i, v_{i+1}\}</math>，其中''i''=1, 2, …, ''n'' − 1，以及<math>\{v_n, v_1\}</math>。循环图的另一种定义是所有点的度都为2的连通图。如果循环图是另一个图的子图，则它是那个图中的一个[[環 (圖論)|环]]。

=== 树和森林 ===
{{main|树 (图论)}}
'''树'''是指任意两点之间都有且仅有一条路径的无向图。等价地，'''树'''是一个连通[[環 (圖論)|无环]]无向图。

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

===其它特殊的图===
一些进阶的特殊图包括：
* [[佩特森圖]]；
* {{tsl|en|perfect graph|完美图}}；
* [[弦图]]；
* {{tsl|en|strongly regular graph|强正则图}}。

== 例子 ==
[[File:6n-graf.svg|thumb|一张6个节点和7条边的图]]

* 右边的图示是一个点集为<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>的图。
* 在[[计算机科学]]中，有向图可以用于表示{{tsl|en|conceptual graph|概念图}}、[[有限状态自动机]]，以及其它许多数据结构。
* 任意集合''X''上的[[二元关系]]''R''都可定义一个有向图。''X''中的元素''x''到''y''有一条边，当且仅当''xRy''。
* 有向图可以用于表示信息网络。例如，在[[推特]]上，用户之间的关注关系可以用有向图表示。<ref name="snatwitter">{{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://serval.unil.ch/resource/serval:BIB_81C2C68B1DF5.P001/REF| doi-access = free| access-date = 2021-08-14| archive-date = 2021-03-02| archive-url = https://web.archive.org/web/20210302190117/https://serval.unil.ch/resource/serval:BIB_81C2C68B1DF5.P001/REF| dead-url = no}}</ref><ref name="twitterwtf">Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh [http://dl.acm.org/citation.cfm?id=2488433 WTF: The who-to-follow system at Twitter] {{Wayback|url=http://dl.acm.org/citation.cfm?id=2488433 |date=20190712002903 }}, ''Proceedings of the 22nd international conference on World Wide Web''. {{doi|10.1145/2488388.2488433}}.</ref>

== 图运算 ==
{{main|图运算}}
图上可以进行一些运算或变换，使一个图变为另一个图：
* '''一元运算'''，将一个图变换为另一个图，例如：
** [[边收缩]]，
** [[线图]]，
** [[对偶图]]，
** [[补图]]；
* '''二元运算'''，结合两个图为一个新图，例如：
** {{tsl|en|disjoint union of graphs|图的无交并}}，
** [[图乘积]]，包括{{tsl|en|cartesian product of graphs|图的笛卡尔乘积}}、{{tsl|en|tensor product of graphs|图的张量积}}、{{tsl|en|strong product of graphs|图的强乘积}}、[[图的字典积]]等，
** {{tsl|en|series–parallel graph|图的串并联}}等。

== 图的推广 ==
在[[超图]]中，允许一条边连接多于两个节点。

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

图可以看作是一种[[拟阵]]。

在[[模型论]]中，图是一个[[结构 (数理逻辑)|结构]]。这样一来，边的数量可以是任意[[基数 (数学)|基数]]。参见[[图极限]]。

在[[计算生物学]]中，{{tsl|en|power graph analysis|幂图}}推广了无向图的定义。

在[[地理信息系统]]中，为了进行道路网络或电网的时空分析而提出的{{tsl|en|geometric networks|几何网络}}的定义参考了图，并借用了许多图论的概念。

== 参见 ==
* {{tsl|en|conceptual graph|概念图}}
* [[图 (数据结构)]]
* [[图论]]
* [[图数据库]]
* [[网络理论]]

== 参考资料 ==
=== 脚注 ===
{{Reflist|45em}}

=== 文献 ===
* ''Introduction To Graph Theory'', by Gary Chartrand and Ping Zhang, McGraw Hill
* {{cite book |last1=徐 |first1=俊明 |title=图论及其应用 |date=2004 |publisher=中国科学技术大学出版社 |location=合肥 |isbn=7-312-00979-4 |edition=第二版}}
* {{cite book |last=Balakrishnan |first=V. K. |date=1997 |title=Graph Theory|url=https://archive.org/details/schaumsoutlineof0000bala |publisher=McGraw-Hill |edition=1st|isbn=978-0-07-005489-9}}
* {{cite book |last1=Bang-Jensen |first1=J. |last2=Gutin |first2=G. |date=2000 |title=Digraphs: Theory, Algorithms and Applications |url=http://www.cs.rhul.ac.uk/books/dbook/ |publisher=Springer |access-date=2021-08-14 |archive-date=2011-08-26 |archive-url=https://web.archive.org/web/20110826005638/http://www.cs.rhul.ac.uk/books/dbook/ |dead-url=no }}
* {{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.com/books?id=vaXv_yhefG8C |access-date=2021-08-14 |archive-date=2021-08-17 |archive-url=https://web.archive.org/web/20210817184751/https://books.google.com/books?id=vaXv_yhefG8C |dead-url=no }}
* {{cite book |last=Berge |first=Claude |date=1958 |title=Théorie des graphes et ses applications |language=fr |location=Paris |publisher=Dunod }}
* {{cite book |last=Biggs |first=Norman |date=1993 |title=Algebraic Graph Theory |edition=2nd |publisher=Cambridge University Press |isbn=978-0-521-45897-9 }}
* {{cite book |last=Bollobás |first=Béla |date=2002 |title=Modern Graph Theory |edition=1st |publisher=Springer |isbn=978-0-387-98488-9 }}
* {{cite book |last=Diestel |first=Reinhard |date=2005 |title=Graph Theory |url=http://diestel-graph-theory.com/GrTh.html |edition=3rd |location=Berlin, New York |publisher=Springer-Verlag |isbn=978-3-540-26183-4 |access-date=2021-08-14 |archive-date=2019-12-16 |archive-url=https://web.archive.org/web/20191216100521/http://diestel-graph-theory.com/GrTh.html |dead-url=no }}
* {{cite book |last1=Graham |first1=R.L. |last2=Grötschel |first2=M. |last3=Lovász |first3=L. |date=1995 |title=Handbook of Combinatorics |publisher=MIT Press |isbn=978-0-262-07169-7 }}
* {{cite book |last1=Gross |first1=Jonathan L. |last2=Yellen |first2=Jay |date=1998 |title=Graph Theory and Its Applications |publisher=CRC Press |isbn=978-0-8493-3982-0 }}
* {{cite book |last1=Gross |first1=Jonathan L. |last2=Yellen |first2=Jay |date=2003 |title=Handbook of Graph Theory |publisher=CRC |isbn=978-1-58488-090-5 }}
* {{cite book |last=Harary |first=Frank |date=1995 |title=Graph Theory |publisher=Addison Wesley Publishing Company |isbn=978-0-201-41033-4 }}
* {{cite book |last1=Iyanaga |first1=Shôkichi |last2=Kawada |first2=Yukiyosi |date=1977 |title=Encyclopedic Dictionary of Mathematics |url=https://archive.org/details/encyclopedicdict0000niho |publisher=MIT Press |isbn=978-0-262-09016-2}}
* {{cite book |last=Zwillinger |first=Daniel |date=2002 |title=CRC Standard Mathematical Tables and Formulae |edition=31st |publisher=Chapman & Hall/CRC |isbn=978-1-58488-291-6 }}
* {{cite book|last=Trudeau|first=Richard J.|title=Introduction to Graph Theory|year=1993|publisher=Dover Publications|location=New York|isbn=978-0-486-67870-2|url=http://store.doverpublications.com/0486678709.html|edition=Corrected, enlarged republication.|access-date=8 August 2012|archive-date=2019-05-05|archive-url=https://web.archive.org/web/20190505192352/http://store.doverpublications.com/0486678709.html|dead-url=no}}

== 外部链接 ==
*{{Cite web
|title=Graph Theory
|url=http://diestel-graph-theory.com/index.html
|date=2016
|accessdate=2019-07-22
|author=Springer-Verlag, Heidelberg
|archive-date=2012-02-08
|archive-url=https://web.archive.org/web/20120208160447/http://diestel-graph-theory.com/index.html
|dead-url=no
}}
* {{Commonscatinline|Graph (discrete mathematics)|图}}
* {{MathWorld | urlname=Graph | title = Graph}}

{{Portal box|数学}}

{{-}}
{{图论}}
[[category:离散数学|T]]