fbpx
维基百科

图论

图论(英語:Graph theory),是组合数学分支,和其他数学分支如群论、矩阵论、拓扑学有着密切关系。

一个由6个顶点和7条边组成的图

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

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

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

历史

 
柯尼斯堡七桥问题

一般认为,欧拉于1736年出版的关于柯尼斯堡七桥问题的论文是图论领域的第一篇文章[3]。此问题被推广为著名的欧拉路问题,亦即一笔画问题。而此论文与范德蒙德英语Alexandre-Théophile Vandermonde的一篇关于骑士周游问题的文章,则是继承了莱布尼茨提出的“位置分析”的方法。欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉公式与图论有密切联系,此后又被柯西等人[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)、希伍德(Percy John Heawood)、拉姆齐Hadwige英语Hugo Hadwiger(Hugo Hadwiger)对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后,四色问题仍未解决。1969年,Heinrich Heesch英语Heinrich Heesch发表了一个用计算机解决此问题的方法。1976年,阿佩尔(Kenneth Appel)和沃夫冈·哈肯(Wolfgang Haken)借助计算机给出了一个证明,此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色。但此方法由于过于复杂,在当时未被广泛接受。

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

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

定義

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

無向圖

 
有三個邊和三個頂點的圖。

圖論中,是有序對  ,其中   是點集;  是邊集,由所有無序頂點對構成(換句話說,邊連接了頂點對)。對於一個邊  ,頂點   被稱作是邊的端點,邊則被稱為連接了此兩個點。

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

事實上可以推廣為更一般的定義:是有序三元組  ,其中   是點集;  是邊集(此時   不再如前面限定是該集合的子集);而   將每個邊映射到一個無序頂點對(於是邊連接了頂點對)。此時的定義就允許自環、重邊的出現,其中自環是兩端點相同的邊,重邊是兩個或多個連接相同端點的邊。

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

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

图论问题

图的计数

子图相关问题

子图同构问题:给定两个图  ,问 中是否存在一个子图与 同構。这是一个NP完全问题

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

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

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

  • 最大独立集问题:在给定图中寻找最大的无边的导出子图,亦即独立集(NP完全)。

平面图判定:判定给定的图是否是平面图(此问题与子图的关系,参见库拉托夫斯基定理

一个尚未解决的与子图相关的猜想,重构猜想Reconstruction conjecture):一个n阶图是否能够由其所有n-1阶导出子图唯一确定?

染色

  • 点色数(Chromatic number
  • 边色数(Chromatic index
  • 色多项式

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

路径问题

网络流与匹配

覆盖问题

重要的算法

参见

注释

  1. ^ 卜月华; 吴建专; 顾国华; 殷翔, 《图论及其应用》 第一版, 东南大学出版社: 1-2, 2007 
  2. ^ Alexander Grigor’yan, Yuri Muranov, Shing-Tung Yau, (PDF), 2012年9月 [2018-05-24], (原始内容 (PDF)存档于2022-06-13) 
  3. ^ Biggs, N.; Lloyd, E.; Wilson, R., Graph Theory, 1736–1936, Oxford University Press, 1986 
  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. 
  6. ^ 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 .

外部連結

線上圖書資料

  • (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(页面存档备份,存于互联网档案馆

其他相關資料

图论, 此條目可参照英語維基百科和西班牙語維基百科相應條目来扩充, 2023年1月28日, 若您熟悉来源语言和主题, 请协助参考外语维基百科扩充条目, 请勿直接提交机械翻译, 也不要翻译不可靠, 低品质内容, 依版权协议, 译文需在编辑摘要注明来源, 或于讨论页顶部标记, href, template, translated, page, html, title, template, translated, page, translated, page, 标签, 英語, graph, theory, 是组合数学分支. 此條目可参照英語維基百科和西班牙語維基百科相應條目来扩充 2023年1月28日 若您熟悉来源语言和主题 请协助参考外语维基百科扩充条目 请勿直接提交机械翻译 也不要翻译不可靠 低品质内容 依版权协议 译文需在编辑摘要注明来源 或于讨论页顶部标记 a href Template Translated page html title Template Translated page Translated page a 标签 图论 英語 Graph theory 是组合数学分支 和其他数学分支如群论 矩阵论 拓扑学有着密切关系 一个由6个顶点和7条边组成的图 图是图论的主要研究对象 图是由若干给定的顶点及连接两顶点的边所构成的图形 这种图形通常用来描述某些事物之间的某种特定关系 顶点用于代表事物 连接两顶点的边则用于表示两个事物间具有这种关系 图论起源于著名的柯尼斯堡七桥问题 该问题于1736年被欧拉解决 因此普遍认为欧拉是图论的创始人 1 图论的研究对象相当于一维的单纯複形 2 目录 1 历史 2 定義 2 1 無向圖 3 图论问题 3 1 图的计数 3 2 子图相关问题 3 3 染色 3 4 路径问题 3 5 网络流与匹配 3 6 覆盖问题 4 重要的算法 5 参见 6 注释 7 參考文獻 8 外部連結 8 1 線上圖書資料 8 2 其他相關資料历史 编辑 柯尼斯堡七桥问题 一般认为 欧拉于1736年出版的关于柯尼斯堡七桥问题的论文是图论领域的第一篇文章 3 此问题被推广为著名的欧拉路问题 亦即一笔画问题 而此论文与范德蒙德 英语 Alexandre Theophile Vandermonde 的一篇关于骑士周游问题的文章 则是继承了莱布尼茨提出的 位置分析 的方法 欧拉提出的关于凸多边形顶点数 棱数及面数之间的关系的欧拉公式与图论有密切联系 此后又被柯西等人 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 希伍德 Percy John Heawood 拉姆齐和Hadwige 英语 Hugo Hadwiger Hugo Hadwiger 对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究 一百多年后 四色问题仍未解决 1969年 Heinrich Heesch 英语 Heinrich Heesch 发表了一个用计算机解决此问题的方法 1976年 阿佩尔 Kenneth Appel 和沃夫冈 哈肯 Wolfgang Haken 借助计算机给出了一个证明 此方法按某些性质将所有地图分为1936类并利用计算机一一验证了它们可以用四种颜色染色 但此方法由于过于复杂 在当时未被广泛接受 1860年之1930年间 若当 库拉托夫斯基和惠特尼从之前独立于图论发展的拓扑学中吸取大量内容进入图论 而现代代数方法的使用更让图论与拓扑走上共同发展的道路 其中应用代数较早者如物理学家基尔霍夫于1845年发表的基尔霍夫电路定律 图论中概率方法的引入 尤其是埃尔德什和Alfred Renyi 英语 Alfred Renyi 关于随机图连通的渐进概率的研究使得图论产生了新的分支随机图论 定義 编辑圖論中有許多定義 以下是一些與之相關最基本的定義 無向圖 编辑 有三個邊和三個頂點的圖 圖論中 圖是有序對 G V E displaystyle G V E 其中 V displaystyle V 是點集 E x y x y V 2 x y displaystyle E subseteq left left x y right x y in V 2 x neq y right 是邊集 由所有無序頂點對構成 換句話說 邊連接了頂點對 對於一個邊 x y displaystyle left x y right 頂點 x y displaystyle x y 被稱作是邊的端點 邊則被稱為連接了此兩個點 為了避免歧異 上述的定義被更精準地稱作無向簡單圖 事實上可以推廣為更一般的定義 圖是有序三元組 G V E ϕ displaystyle G V E phi 其中 V displaystyle V 是點集 E displaystyle E 是邊集 此時 E displaystyle E 不再如前面限定是該集合的子集 而 ϕ E x y x y V 2 displaystyle phi E to left left x y right x y in V 2 right 將每個邊映射到一個無序頂點對 於是邊連接了頂點對 此時的定義就允許自環 重邊的出現 其中自環是兩端點相同的邊 重邊是兩個或多個連接相同端點的邊 為了避免歧異 上述的定義被更精準地稱作無向圖 V E displaystyle V E 的元素個數通常都是有限的 並且如果個數是無限的 有許多著名的性質都发生变化 甚至不再正确 此外 V displaystyle V 通常不被接受是空集合 而 E displaystyle E 則被接受為空集合 以下再給出一些圖論中的定義 圖的階是其頂點個數 V displaystyle V 圖的邊數是 E displaystyle E 頂點的度所有邊的端點中此頂點出現的次數 自環會被算兩次 图论问题 编辑图的计数 编辑 子图相关问题 编辑 子图同构问题 给定两个图G displaystyle G 和H displaystyle H 问G displaystyle G 中是否存在一个子图与H displaystyle H 同構 这是一个NP完全问题 哈密顿回路问题可视为一个子图同构问题 即给定一个n displaystyle n 个顶点的图 问是否存在一个子图与具有n displaystyle n 个顶点的圈同构 一类相关的常见问题要求在给定图中寻找符合某些条件的最大子图 其中有很多是NP完全的 如 分团问题 在给定图中寻找最大的团 NP完全 类似地 有些问题要求寻找符合某些条件的最大导出子图 如 最大独立集问题 在给定图中寻找最大的无边的导出子图 亦即独立集 NP完全 平面图判定 判定给定的图是否是平面图 此问题与子图的关系 参见库拉托夫斯基定理 一个尚未解决的与子图相关的猜想 重构猜想 Reconstruction conjecture 一个n阶图是否能够由其所有n 1阶导出子图唯一确定 染色 编辑 点色数 Chromatic number 边色数 Chromatic index 色多项式许多问题与将图以特定方式染色有关 如 四色问题 完美图问题 strong perfect graph theorem 列表染色问题 列表边染色问题 曲面染色路径问题 编辑 柯尼斯堡七桥问题 哈密顿回路问题 最小生成树问题 中国邮路问题 最短路问题 斯坦纳树 旅行商问题 NP困难 网络流与匹配 编辑 最大流问题 最小割问题 最大流最小割定理 最小费用最大流问题 二分图及任意图上的最大匹配 带权二分图的最大权匹配覆盖问题 编辑 最大团 最大独立集 最小覆盖集 最小支配集重要的算法 编辑戴克斯特拉算法 D A 克鲁斯卡尔算法 K A 普里姆算法 P A 拓扑排序演算法 TSA 關鍵路徑演算法 CPA 广度优先搜索算法 BFS 深度优先搜索算法 DFS 参见 编辑 数学主题 组合数学 三間小屋問題注释 编辑 卜月华 吴建专 顾国华 殷翔 图论及其应用 第一版 东南大学出版社 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 polyedres premier memoire Journal de l Ecole polytechnique 1813 9 Cahier 16 66 86 L Huillier S A J Memoire sur la polyedrometrie Annales de Mathematiques 1812 1813 3 169 189 Sylvester James Joseph Chemistry and Algebra Nature 1878 17 284 doi 10 1038 017284a0 參考文獻 编辑Berge Claude Theorie des graphes et ses applications Collection Universitaire de Mathematiques II Paris Dunod 1958 English edition Wiley 1961 Methuen amp 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 页面存档备份 存于互联网档案馆 取自 https zh wikipedia org w index php title 图论 amp oldid 72168503, 维基百科,wiki,书籍,书籍,图书馆,

文章

,阅读,下载,免费,免费下载,mp3,视频,mp4,3gp, jpg,jpeg,gif,png,图片,音乐,歌曲,电影,书籍,游戏,游戏。