图论：修订间差异

以互动方式浏览历史

←上一版本

删除的内容添加的内容

可视化wikitext

行内

2024年7月7日 (日) 10:30的最新版本

图论（英語：Graph theory），是组合数学分支，和其他数学分支如群论、矩阵论、拓扑学有着密切关系。

图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。^[1]

图论的研究对象相当于一维的单纯複形^[2]。

历史[编辑]

一般认为，欧拉于1736年出版的关于柯尼斯堡七桥问题的论文是图论领域的第一篇文章^[3]。此问题被推广为著名的欧拉路问题，亦即一笔画问题。而此论文与范德蒙的一篇关于骑士周游问题的文章，则是继承了莱布尼茨提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉公式与图论有密切联系，此后又被柯西等人^[4]^[5]进一步研究推广，成了拓扑学的起源。1857年，哈密顿发明了“環遊世界遊戲（英语：icosian game）”（icosian game），与此相关的则是另一个广为人知的图论问题“哈密顿路径问题”。

西尔维斯特于1878年发表在《自然》上的一篇论文中首次提出“图”这一名词^[6]。

欧拉的论文发表后一个多世纪，凯莱研究了在微分学中出现的一种数学分析的特殊形式，而这最终将他引向对一种特殊的被称为“树”的图的研究。由于有机化学中有许多树状结构的分子，这些研究对于理论化学有着重要意义，尤其是其中关于具有某一特定性质的图的计数问题。除凯莱的成果外，波利亚也于1935至1937年发表了一些成果，1959年，De Bruijn（英语：Nicolaas Govert de Bruijn）做了一些推广。这些研究成果奠定了图的计数理论的基础。凯莱将他关于树的研究成果与当时有关化合物的研究联系起来，而图论中有一部分术语正是来源于这种将数学与化学相联系的做法。

四色问题可谓是图论研究史上最著名也是产生成果最多的问题之一：“是否任何一幅画在平面上的地图都可以用四种颜色染色，使得任意两个相邻的区域不同色？”这一问题由法兰西斯·古德里于1852年提出，而最早的文字记载则出现在德摩根于1852年写给哈密顿的一封信上。包括凯莱、肯普（英语：Alfred Kempe）等在内的许多人都曾给出过错误的证明。泰特（英语：Peter Guthrie Tait）（Peter Guthrie Tait）、希伍德、拉姆齐和Hadwige（英语：Hugo Hadwiger）（Hugo Hadwiger）对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，Heinrich Heesch（英语：Heinrich Heesch）发表了一个用计算机解决此问题的方法。1976年，凱尼斯·阿佩爾和沃夫冈·哈肯借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色。但此方法由于过于复杂，在当时未被广泛接受。

1860年之1930年间，若当、库拉托夫斯基和惠特尼从之前独立于图论发展的拓扑学中吸取大量内容进入图论，而现代代数方法的使用更让图论与拓扑走上共同发展的道路。其中应用代数较早者如物理学家基尔霍夫于1845年发表的基尔霍夫电路定律。

图论中概率方法的引入，尤其是埃尔德什和Alfréd Rényi（英语：Alfréd Rényi）关于随机图连通的渐进概率的研究使得图论产生了新的分支随机图论。

定義[编辑]

圖論中有許多定義，以下是一些與之相關最基本的定義。

無向圖[编辑]

圖論中，圖是有序對 $G=(V,E)$ ，其中 $V$ 是點集； $E\subseteq \left\{\left\{x,y\right\}:(x,y)\in V^{2},x\neq y\right\}$ 是邊集，由所有無序頂點對構成（換句話說，邊連接了頂點對）。對於一個邊 $\left\{x,y\right\}$ ，頂點 $x,y$ 被稱作是邊的端點，邊則被稱為連接了此兩個點。

為了避免歧異，上述的定義被更精準地稱作無向簡單圖。

事實上可以推廣為更一般的定義：圖是有序三元組 $G=(V,E,\phi )$ ，其中 $V$ 是點集； $E$ 是邊集（此時 $E$ 不再如前面限定是該集合的子集）；而 $\phi :E\to \left\{\left\{x,y\right\}:(x,y)\in V^{2}\right\}$ 將每個邊映射到一個無序頂點對（於是邊連接了頂點對）。此時的定義就允許自環、重邊的出現，其中自環是兩端點相同的邊，重邊是兩個或多個連接相同端點的邊。

為了避免歧異，上述的定義被更精準地稱作無向圖。

$V,E$ 的元素個數通常都是有限的；並且如果個數是無限的，有許多著名的性質都发生变化，甚至不再正确。此外， $V$ 通常不被接受是空集合，而 $E$ 則被接受為空集合。以下再給出一些圖論中的定義：圖的階是其頂點個數 $|V|$ ，圖的邊數是 $|E|$ ，頂點的度所有邊的端點中此頂點出現的次數（自環會被算兩次）。

图论问题[编辑]

图的计数[编辑]

子图相关问题[编辑]

子图同构问题：给定两个图 $G$ 和 $H$ ，问 $G$ 中是否存在一个子图与 $H$ 同構。这是一个NP完全问题。

哈密顿回路问题可视为一个子图同构问题，即给定一个 $n$ 个顶点的图，问是否存在一个子图与具有 $n$ 个顶点的圈同构。

一类相关的常见问题要求在给定图中寻找符合某些条件的最大子图，其中有很多是NP完全的，如：

分团问题：在给定图中寻找最大的团（NP完全）。

类似地，有些问题要求寻找符合某些条件的最大导出子图，如：

最大独立集问题：在给定图中寻找最大的无边的导出子图，亦即独立集（NP完全）。

平面图判定：判定给定的图是否是平面图（此问题与子图的关系，参见库拉托夫斯基定理）

一个尚未解决的与子图相关的猜想，重构猜想（Reconstruction conjecture）：一个n阶图是否能够由其所有n-1阶导出子图唯一确定？

染色[编辑]

点色数（Chromatic number）
边色数（Chromatic index）
色多项式

许多问题与将图以特定方式染色有关，如：

四色问题
完美图问题（strong perfect graph theorem）
列表染色问题，列表边染色问题
曲面染色

路径问题[编辑]

网络流与匹配[编辑]

覆盖问题[编辑]

最大团
最大独立集
最小覆盖集
最小支配集

重要的算法[编辑]

参见[编辑]

注释[编辑]

^ 卜月华; 吴建专; 顾国华; 殷翔, 《图论及其应用》第一版, 东南大学出版社: 1-2, 2007
^ Alexander Grigor’yan, Yuri Muranov, Shing-Tung Yau, Graphs associated with simplicial complexes (PDF), 2012年9月 [2018-05-24], （原始内容 (PDF)存档于2022-06-13）
^ Biggs, N.; Lloyd, E.; Wilson, R., Graph Theory, 1736–1936, Oxford University Press, 1986
^ Cauchy, A. L., Recherche sur les polyèdres - premier mémoire, Journal de l'École polytechnique, 1813,, 9 (Cahier 16): 66–86.
^ L'Huillier, S.-A.-J., Mémoire sur la polyèdrométrie, Annales de Mathématiques, 1812–1813, 3: 169–189.
^ Sylvester, James Joseph. Chemistry and Algebra. Nature. 1878, 17: 284. doi:10.1038/017284a0.

參考文獻[编辑]

Berge, Claude, Théorie des graphes et ses applications, Collection Universitaire de Mathématiques II, Paris: Dunod, 1958 . English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.
Biggs, N.; Lloyd, E.; Wilson, R., Graph Theory, 1736–1936, Oxford University Press, 1986 .
Bondy, J.A.; Murty, U.S.R., Graph Theory, Springer, 2008, ISBN 978-1-84628-969-9 .
Bondy, Riordan, O.M, Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003 .
Chartrand, Gary, Introductory Graph Theory, Dover, 1985, ISBN 0-486-24775-9 .
Gibbons, Alan, Algorithmic Graph Theory, Cambridge University Press, 1985 .
Reuven Cohen, Shlomo Havlin, Complex Networks: Structure, Robustness and Function, Cambridge University Press, 2010
Golumbic, Martin, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980 .
Harary, Frank, Graph Theory, Reading, MA: Addison-Wesley, 1969 .
Harary, Frank; Palmer, Edgar M., Graphical Enumeration, New York, NY: Academic Press, 1973 .
Mahadev, N.V.R.; Peled, Uri N., Threshold Graphs and Related Topics, North-Holland, 1995 .
Mark Newman, Networks: An Introduction, Oxford University Press, 2010 .

外部連結[编辑]

線上圖書資料[编辑]

Graph Theory with Applications (1976) by Bondy and Murty
Phase Transitions in Combinatorial Optimization Problems, Section 3: Introduction to Graphs (2006) by Hartmann and Weigt
Digraphs: Theory Algorithms and Applications（页面存档备份，存于互联网档案馆） 2007 by Jorgen Bang-Jensen and Gregory Gutin
Graph Theory, by Reinhard Diestel（页面存档备份，存于互联网档案馆）

其他相關資料[编辑]

Hazewinkel, Michiel (编), Graph theory, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
Graph theory tutorial（页面存档备份，存于互联网档案馆）
A searchable database of small connected graphs
Image gallery: graphs
Concise, annotated list of graph theory resources for researchers
rocs（页面存档备份，存于互联网档案馆） — a graph theory IDE
Graph Theory Software（页面存档备份，存于互联网档案馆）

[1] 卜月华; 吴建专; 顾国华; 殷翔, 《图论及其应用》第一版, 东南大学出版社: 1-2, 2007

[2] Alexander Grigor’yan, Yuri Muranov, Shing-Tung Yau, Graphs associated with simplicial complexes (PDF), 2012年9月 [2018-05-24], （原始内容 (PDF)存档于2022-06-13）

[Biggs-3] Biggs, N.; Lloyd, E.; Wilson, R., Graph Theory, 1736–1936, Oxford University Press, 1986

[Cauchy-4] Cauchy, A. L., Recherche sur les polyèdres - premier mémoire, Journal de l'École polytechnique, 1813,, 9 (Cahier 16): 66–86.

[5] L'Huillier, S.-A.-J., Mémoire sur la polyèdrométrie, Annales de Mathématiques, 1812–1813, 3: 169–189.

[Sylvester-6] Sylvester, James Joseph. Chemistry and Algebra. Nature. 1878, 17: 284. doi:10.1038/017284a0.

[1]

[2]

[3]

[4]

[5]

[6]

@@ 第1行： / 第1行： @@
+{{expand language|en|es|time = 2024-05-05}}
 [[File:6n-graf.svg|thumb|250px|一个由6个顶点和7条边组成的图]]
+'''图论'''（{{lang-en|Graph theory}}），是[[组合数学]]分支，和其他数学分支如[[群论]]、矩阵论、[[拓扑学]]有着密切关系。
-'''图论'''（{{lang|en|Graph theory}}）是[[数学]]的一个分支，它以[[图 (数学)|图]]为研究对象，研究[[顶点]]和[[边]]组成的图形的数学理论和方法。图是区域在头脑和纸面上的反映，图论就是研究区域关系的学科。区域是一个平面，平面当然是二维的，但是，图在特殊的构造中，可以形成多维（例如大于3维空间）空间，这样的图已经超越了一般意义上的区域（例如一个有许多洞的曲面，它是多维的，[[曲面染色]]已经超出了平面概念）。
-图论中的图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用连接两顶点的边表示相应两个事物间具有这种关系。
+[[图 (数学)|图]]是图论的主要研究对象。图是由若干给定的[[顶点 (图论)|顶点]]及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
+图论起源于著名的[[柯尼斯堡七桥问题]]。该问题于1736年被[[欧拉]]解决，因此普遍认为[[欧拉]]是图论的创始人。<ref>{{citation|author1= 卜月华|author2=吴建专|author3 = 顾国华|author4 = 殷翔|title=《图论及其应用》|publisher=东南大学出版社|year=2007|edition=第一版 | page = 1-2}}</ref>
-图论起源于著名的[[柯尼斯堡七桥问题]]。
+图论的研究对象相当于一维的[[单纯複形]]<ref>{{citation | authors = Alexander Grigor’yan, Yuri Muranov, Shing-Tung Yau | title = Graphs associated with simplicial complexes | url = https://www.math.uni-bielefeld.de/~grigor/cubic.pdf | date = 2012年9月 | accessdate = 2018-05-24 | archive-date = 2022-06-13 | archive-url = https://web.archive.org/web/20220613003947/https://www.math.uni-bielefeld.de/~grigor/cubic.pdf }}</ref>。
-{{Fact|图论的研究对象相当于一维的[[拓扑学]]。|time=2014-12-03T09:48:14+00:00}}
 == 历史 ==
 [[File:Konigsberg bridges.png|thumb|200px|柯尼斯堡七桥问题]]
-一般认为，于1736年出版的[[莱昂哈德·欧拉|欧拉]]的关于[[柯尼斯堡七桥问题]]的论文是图论领域的第一篇文章<ref name = "Biggs">{{citation|last1=Biggs|first1=N.|last2=Lloyd|first2=E.|last3=Wilson|first3=R.|title=Graph Theory, 1736–1936|publisher=Oxford University Press|year=1986}}</ref>。此问题被推广为著名的欧拉路问题，亦即[[一笔画问题]]。而此论文与{{link-en|范德蒙德|Alexandre-Théophile Vandermonde|范德蒙德}}的一篇关于[[骑士巡逻|骑士周游问题]]的文章，则是继承了[[戈特弗里德·莱布尼茨|莱布尼茨]]提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的[[欧拉示性数|欧拉公式]]与图论有密切联系，此后又被[[奥古斯丁·路易·柯西|柯西]]等人<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><ref>{{Citation|author=L'Huillier, S.-A.-J.|title=Mémoire sur la polyèdrométrie|journal=Annales de Mathématiques|volume=3|year=1812–1813|pages=169–189|postscript=.}}</ref>进一步研究推广，成了[[拓扑学]]的起源。1857年，[[威廉·哈密顿|哈密顿]]发明了“{{link-en|環遊世界遊戲|icosian game|環遊世界遊戲}}”（icosian game），与此相关的则是另一个广为人知的图论问题“[[哈密顿路径问题]]”。
+一般认为，[[莱昂哈德·欧拉|欧拉]]于1736年出版的关于[[柯尼斯堡七桥问题]]的论文是图论领域的第一篇文章<ref name = "Biggs">{{citation|last1=Biggs|first1=N.|last2=Lloyd|first2=E.|last3=Wilson|first3=R.|title=Graph Theory, 1736–1936|publisher=Oxford University Press|year=1986}}</ref>。此问题被推广为著名的欧拉路问题，亦即[[一笔画问题]]。而此论文与[[亞歷山大‑泰奧菲爾·范德蒙|范德蒙]]的一篇关于[[骑士巡逻|骑士周游问题]]的文章，则是继承了[[戈特弗里德·莱布尼茨|莱布尼茨]]提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的[[欧拉示性数|欧拉公式]]与图论有密切联系，此后又被[[奥古斯丁·路易·柯西|柯西]]等人<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><ref>{{Citation|author=L'Huillier, S.-A.-J.|title=Mémoire sur la polyèdrométrie|journal=Annales de Mathématiques|volume=3|year=1812–1813|pages=169–189|postscript=.}}</ref>进一步研究推广，成了[[拓扑学]]的起源。1857年，[[威廉·哈密顿|哈密顿]]发明了“{{link-en|環遊世界遊戲|icosian game|環遊世界遊戲}}”（icosian game），与此相关的则是另一个广为人知的图论问题“[[哈密顿路径问题]]”。
-“图”这一名词是[[詹姆斯·约瑟夫·西尔维斯特|西尔维斯特]]在于1878年发表在《[[自然 (期刊)|自然]]》上的一篇论文中提出的。
+[[詹姆斯·约瑟夫·西尔维斯特|西尔维斯特]]于1878年发表在《[[自然 (期刊)|自然]]》上的一篇论文中首次提出“图”这一名词<ref name="Sylvester">{{cite journal | last1 = Sylvester | first1 = James Joseph | year = 1878 | title = Chemistry and Algebra | url = https://archive.org/stream/nature15unkngoog#page/n312/mode/1up | journal = Nature | volume = 17 | issue = | page = 284 | doi = 10.1038/017284a0 }}</ref>。
 欧拉的论文发表后一个多世纪，[[阿瑟·凯莱|凯莱]]研究了在[[微分|微分学]]中出现的一种数学分析的特殊形式，而这最终将他引向对一种特殊的被称为“[[树 (图论)|树]]”的图的研究。由于有机化学中有许多树状结构的分子，这些研究对于理论化学有着重要意义，尤其是其中关于具有某一特定性质的[[图的计数]]问题。除凯莱的成果外，[[乔治·波利亚|波利亚]]也于1935至1937年发表了一些成果，1959年，{{link-en|De Bruijn|Nicolaas Govert de Bruijn|De Bruijn}}做了一些推广。这些研究成果奠定了图的计数理论的基础。凯莱将他关于树的研究成果与当时有关化合物的研究联系起来，而图论中有一部分术语正是来源于这种将数学与化学相联系的做法。
-[[四色问题]]可谓是图论研究史上最著名也是产生成果最多的问题之一：“是否任何一幅画在平面上的地图都可以用四种颜色染色，使得任意两个相邻的区域不同色？”这一问题最早于1852年由{{link-en|Francis Guthrie|Francis Guthrie|Francis Guthrie}}提出，最早的文字记载则现于[[奥古斯塔斯·德摩根|德摩根]]于同一年写给哈密顿的信上。包括凯莱、{{tsl|en|Alfred Kempe|阿爾弗雷德·佈雷·肯普|肯普}}等在内的许多人都曾给出过错误的证明。{{link-en|Peter Guthrie Tait|Peter Guthrie Tait|泰特}}（Peter Guthrie Tait）、{{link-en|希伍德|Percy John Heawood|希伍德}}（Percy John Heawood）、[[弗兰克·普伦普顿·拉姆齐|拉姆齐]]和{{link-en|哈德维格|Hugo Hadwiger|Hadwige|哈德维格}}（Hugo Hadwiger）对此问题的研究与推广引发了对嵌入具有不同[[亏格]]的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，{{link-en|Heinrich Heesch|Heinrich Heesch|Heinrich Heesch}}发表了一个用计算机解决此问题的方法。1976年，[[Kenneth Appel|阿佩尔]]（Kenneth Appel）和[[哈肯]]（Wolfgang Haken）借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色。但此方法由于过于复杂，在当时未被广泛接受。
+[[四色问题]]可谓是图论研究史上最著名也是产生成果最多的问题之一：“是否任何一幅画在平面上的地图都可以用四种颜色染色，使得任意两个相邻的区域不同色？”这一问题由[[法兰西斯·古德里]]于1852年提出，而最早的文字记载则出现在[[奥古斯塔斯·德摩根|德摩根]]于1852年写给哈密顿的一封信上。包括[[阿瑟·凱萊|凯莱]]、{{tsl|en|Alfred Kempe|阿爾弗雷德·佈雷·肯普|肯普}}等在内的许多人都曾给出过错误的证明。{{link-en|Peter Guthrie Tait|Peter Guthrie Tait|泰特}}（Peter Guthrie Tait）、[[彭西·希伍德|希伍德]]、[[弗兰克·普伦普顿·拉姆齐|拉姆齐]]和{{link-en|哈德维格|Hugo Hadwiger|Hadwige|哈德维格}}（Hugo Hadwiger）对此问题的研究与推广引发了对嵌入具有不同[[亏格]]的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，{{link-en|Heinrich Heesch|Heinrich Heesch|Heinrich Heesch}}发表了一个用计算机解决此问题的方法。1976年，[[凱尼斯·阿佩爾]]和[[沃夫冈·哈肯]]借助计算机给出了一个证明，此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色。但此方法由于过于复杂，在当时未被广泛接受。
-年之1930年间，[[卡米尔·若尔当|若当]]、[[卡齐米日·库拉托夫斯基|库拉托夫斯基]]和[[哈斯勒·惠特尼|惠特尼]]从之前独立于图论而发展的拓扑学中吸取大量内容进入图论，而现代代数方法的使用更让图论与拓扑走上共同发展的道路。其中应用代数较早者如物理学家[[古斯塔夫·基尔霍夫|基尔霍夫]]于1845年发表的[[基尔霍夫电路定律]]。
+年之1930年间，[[卡米尔·若尔当|若当]]、[[卡齐米日·库拉托夫斯基|库拉托夫斯基]]和[[哈斯勒·惠特尼|惠特尼]]从之前独立于图论发展的拓扑学中吸取大量内容进入图论，而现代代数方法的使用更让图论与拓扑走上共同发展的道路。其中应用代数较早者如物理学家[[古斯塔夫·基尔霍夫|基尔霍夫]]于1845年发表的[[基尔霍夫电路定律]]。
 图论中概率方法的引入，尤其是[[保罗·埃尔德什|埃尔德什]]和{{link-en|Alfréd Rényi|Alfréd Rényi|Alfréd Rényi}}关于随机图连通的渐进概率的研究使得图论产生了新的分支[[随机图论]]。
+== 定義 ==
+圖論中有許多定義，以下是一些與之相關最基本的定義。
+=== 無向圖 ===
+[[File:Undirected.svg|缩略图|有三個邊和三個頂點的圖。]]
+圖論中，'''圖'''是有序對 <math>G=(V,E)</math>，其中 <math>V</math> 是點集；<math>E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\}</math> 是邊集，由所有無序頂點對構成（換句話說，邊連接了頂點對）。對於一個邊 <math>\left\{x,y\right\}</math>，頂點 <math>x,y</math> 被稱作是邊的端點，邊則被稱為連接了此兩個點。
+為了避免歧異，上述的定義被更精準地稱作無向簡單圖。
+事實上可以推廣為更一般的定義：'''圖'''是有序三元組 <math>G=(V,E,\phi)</math>，其中 <math>V</math> 是點集；<math>E</math> 是邊集（此時 <math>E</math> 不再如前面限定是該集合的子集）；而 <math>\phi:E\to\left\{\left\{x,y\right\}:(x,y)\in V^2\right\}</math> 將每個邊映射到一個無序頂點對（於是邊連接了頂點對）。此時的定義就允許自環、重邊的出現，其中自環是兩端點相同的邊，重邊是兩個或多個連接相同端點的邊。
+為了避免歧異，上述的定義被更精準地稱作無向圖。
+<math>V,E</math> 的元素個數通常都是有限的；並且如果個數是無限的，有許多著名的性質都发生变化，甚至不再正确。此外，<math>V</math> 通常不被接受是空集合，而 <math>E</math> 則被接受為空集合。以下再給出一些圖論中的定義：圖的階是其頂點個數 <math>|V|</math>，圖的邊數是 <math>|E|</math>，頂點的度所有邊的端點中此頂點出現的次數（自環會被算兩次）。
 == 图论问题 ==
@@ 第32行： / 第48行： @@
 一类相关的常见问题要求在给定图中寻找符合某些条件的最大子图，其中有很多是NP完全的，如：
-* [[最大团问题]]：在给定图中寻找最大的[[团 (图论)|团]]（NP完全）。
+*[[分团问题]]：在给定图中寻找最大的[[团 (图论)|团]]（NP完全）。
 类似地，有些问题要求寻找符合某些条件的最大导出子图，如：
 * [[最大独立集问题]]：在给定图中寻找最大的无边的导出子图，亦即[[独立集]]（NP完全）。
-[[平面图]]判定：判定给定的图是否是平面图（此问题与子图的关系，参见[[平面图 (图论)|库拉托夫斯基定理]]）
+[[平面图 (图论)|平面图]]判定：判定给定的图是否是平面图（此问题与子图的关系，参见[[平面图 (图论)|库拉托夫斯基定理]]）
 一个尚未解决的与子图相关的猜想，[[重构猜想]]（{{lang|en|Reconstruction conjecture}}）：一个''n''阶图是否能够由其所有''n-1''阶导出子图唯一确定？
@@ 第91行： / 第107行： @@
 {{mathportal}}
 * [[组合数学]]
+* [[三間小屋問題]]
 == 注释 ==
@@ 第115行： / 第132行： @@
 * [https://web.archive.org/web/20120616164929/http://www.math.jussieu.fr/~jabondy/books/gtwa/gtwa.html Graph Theory with Applications] (1976) by Bondy and Murty
 *[http://arxiv.org/pdf/cond-mat/0602129 Phase Transitions in Combinatorial Optimization Problems, Section 3: Introduction to Graphs] (2006) by Hartmann and Weigt
-*[http://www.cs.rhul.ac.uk/books/dbook/ Digraphs: Theory Algorithms and Applications] 2007 by Jorgen Bang-Jensen and Gregory Gutin
+*[http://www.cs.rhul.ac.uk/books/dbook/ Digraphs: Theory Algorithms and Applications]{{Wayback|url=http://www.cs.rhul.ac.uk/books/dbook/ |date=20110826005638 }} 2007 by Jorgen Bang-Jensen and Gregory Gutin
-*[http://diestel-graph-theory.com/index.html Graph Theory, by Reinhard Diestel]
+*[http://diestel-graph-theory.com/index.html Graph Theory, by Reinhard Diestel]{{Wayback|url=http://diestel-graph-theory.com/index.html |date=20120208160447 }}
 ===其他相關資料===
 * {{springer|title=Graph theory|id=p/g045010}}
-* [http://www.utm.edu/departments/math/graph/ Graph theory tutorial]
+* [http://www.utm.edu/departments/math/graph/ Graph theory tutorial]{{Wayback|url=http://www.utm.edu/departments/math/graph/ |date=20120116185332 }}
 * [http://www.gfredericks.com/main/sandbox/graphs A searchable database of small connected graphs]
 * [https://web.archive.org/web/20060206155001/http://www.nd.edu/~networks/gallery.htm Image gallery: graphs]
-* [http://www.babelgraph.org/links.html Concise, annotated list of graph theory resources for researchers]
+* [https://web.archive.org/web/20190713044422/http://www.babelgraph.org/links.html Concise, annotated list of graph theory resources for researchers]
-* [http://www.kde.org/applications/education/rocs/ rocs] — a graph theory IDE
+* [http://www.kde.org/applications/education/rocs/ rocs]{{Wayback|url=http://www.kde.org/applications/education/rocs/ |date=20120111113948 }} — a graph theory IDE
-* [http://graphtheorysoftware.com/ Graph Theory Software]
+* [http://graphtheorysoftware.com/ Graph Theory Software]{{Wayback|url=http://graphtheorysoftware.com/ |date=20130313205057 }}
 {{图论}}
+{{应用数学}}
 {{数学主要领域}}
@@ 第133行： / 第152行： @@
 [[Category:离散数学]]
 [[Category:图论]]
+[[分类:数学分支]]