圖理論

本文是關於邊緣連接的一組頂點。有關數學函數的圖，請參見函數的圖。有關其他用途，請參見圖（歧義） 。
圖的圖。

在數學中，圖理論是圖形的研究，這些研究是用於建模對象之間成對關係的數學結構。在此上下文中的圖是由通過邊緣連接（也稱為鏈接或行）連接的頂點（也稱為節點或點）組成的。在無向圖之間進行了區分，其中邊緣對稱地鏈接兩個頂點，並在其中邊緣不對稱地鏈接兩個頂點。圖是離散數學研究的主要對象之一。

定義

更多信息：圖理論詞彙表

圖理論中的定義各不相同。以下是定義圖和相關數學結構的一些更基本的方法。

圖形

一個具有三個頂點和三個邊緣的圖形。

在一個術語的限制但非常常見的意義中，圖是一個有序對，其中包括：

  • ，一組頂點（也稱為節點或點）；
  • ，一組邊緣（也稱為鏈接或線路），它們是未排序的頂點對（即，一個邊緣與兩個不同的頂點相關聯）。

為了避免歧義，這種類型的對象可以精確地稱為無方向的簡單圖。

在邊緣，頂點稱為邊緣的端點。據說邊緣會加入並不斷發生。頂點可能存在於圖中，而不屬於邊緣。在此定義下，不允許兩個或多個邊緣連接相同頂點的多個邊緣。

從一個允許多個邊緣的術語的一般意義上，圖是一個有序的三重組成：

  • ，一組頂點（也稱為節點或點）；
  • ，一組邊緣（也稱為鏈接或行）；
  • ，將每個邊緣映射到無序的頂點（即，一個邊緣與兩個不同的頂點相關聯）的發射函數。

為了避免歧義，這種類型的對象可以準確地稱為無方向性的多編碼。

循環是將頂點與自身相連的邊緣。上面兩個定義中定義的圖形不能具有循環，因為將頂點連接到本身的循環是邊緣（對於無方向的簡單圖），或者在不在（無方向的多式圖）上入射。為了允許循環，必須擴展定義。對於無方向的簡單圖，應將定義修改為。對於無方向的多編碼，應將其定義修改為。為了避免歧義，這些類型的對象可以被稱為無方向的簡單圖，允許循環和無方向的循環（有時也是無方向的偽掃描）。

通常被認為是有限的，許多眾所周知的結果對於無限圖並不正確（或相當不同），因為許多參數在無限情況下都失敗了。而且，通常認為通常是非空的，但被允許為空集。圖的順序為，其頂點數。圖的大小為，其邊緣數。頂點的程度或價值是入射的邊緣數量，其中循環被計數兩次。圖的程度是其頂點的最大程度。

在無方向性n的無方向圖中，每個頂點的最大程度為n -1 ，圖的最大尺寸為n （ n -1） / 2 。

無向圖的邊緣允許迴路在其頂點上引起對稱均質關係，稱為鄰接關係。具體而言，對於每個邊緣，其終點，據說彼此相鄰，表示為。

定向圖

主要文章：定向圖
有針對三個頂點和四個有向邊緣的有向圖（雙箭頭代表每個方向的邊緣）。

有向圖或DIGRAPH是邊緣具有方向的圖。

在一個術語的一個受限但非常常見的意義上，有向圖是一個有序的對，其中包括：

  • ，一組頂點（也稱為節點或點）；
  • ，一組邊緣（也稱為定向邊緣，有向鏈接，有向線，箭頭或弧形），它們是對頂點的訂購對（即，一個邊緣與兩個不同的頂點相關聯）。

為了避免歧義，這種類型的對象可以精確地稱為有向的簡單圖。在集合理論和圖理論中，表示其中元素的n個元素集，是不一定不同的元素序列的有序序列。

在從到達的邊緣中，頂點稱為邊緣的端點，邊緣的尾巴和邊緣的頭。據說邊緣會加入並不斷發生。頂點可能存在於圖中，而不屬於邊緣。邊緣稱為倒邊緣。上面定義不允許的多個邊緣是兩個或多個邊緣，具有相同的尾巴和相同的頭部。

從一個允許多個邊緣的術語的一般意義上，有向圖是一個有序的三重組成：

  • ，一組頂點（也稱為節點或點）；
  • ，一組邊緣（也稱為定向邊緣，定向鏈接，有向線，箭頭或弧）；
  • ，將每個邊緣映射到有序的頂點（即，一個邊緣與兩個不同的頂點相關聯）的發射函數。

為了避免歧義，這種類型的對象可以準確地稱為有針對性的多編碼。

循環是將頂點與自身相連的邊緣。上述兩個定義中定義的有向圖不能具有循環，因為將頂點與自身的循環自身是邊緣（對於有向簡單的圖形），或者在不在（有向的多機上）出現（用於有向的多機）。因此，要允許循環，必須擴展定義。對於定向的簡單圖，應將其定義修改為。對於定向的多編碼，應將其定義修改為。為了避免歧義，這些類型的對象可以精確地稱為有向的簡單圖，允許循環和有向的多機允許循環（或箭話）。

有向簡單圖的邊緣允許循環是一個均勻的關係〜在其頂點上稱為鄰接關係。具體而言，對於每個邊緣，其終點，據說彼此相鄰，表示為〜。

申請

Wikipedia編輯（邊緣）在2013年夏季一個月內為不同的Wikipedia語言版本（頂點）貢獻的網絡圖。

圖表可用於建模物理，生物學，社會和信息系統中的多種類型的關係和過程。許多實際問題可以用圖表表示。強調其在現實世界系統中的應用，有時將術語網絡定義為表示屬性（例如名稱）與頂點和邊緣關聯的圖，以及表達和理解現實世界系統作為網絡的主題被稱為網絡科學。

計算機科學

在計算機科學中，因果關係和非因果關係結構是用於表示通信，數據組織，計算設備，計算流等網絡的圖表。圖表，其中頂點表示網頁和定向邊緣表示從一個頁面到另一頁的鏈接。在社交媒體，旅行，生物學，計算機芯片設計，映射神經脫生疾病的進展以及許多其他領域的問題中，也可以採用類似的方法。因此，要處理圖形的算法的開發對計算機科學具有重大興趣。圖形的轉換通常由圖形重寫系統形式化並表示。互補的圖形轉換系統重點是基於規則的圖表中的內存操作，是針對事務- 安全，持續存儲和查詢圖形結構化數據的圖形數據庫。

語言學

事實證明，以各種形式的圖形理論方法在語言學中特別有用，因為自然語言通常可以很好地適合離散結構。傳統上，語法和構圖語義遵循基於樹的結構，其表現力在於構圖原理，以層次圖為基礎。使用類型的特徵結構，諸如頭部驅動的短語結構語法語法諸如自然語法的語法諸如類型的特徵結構，這些詞語是定向的無環圖。在詞彙語義中，尤其是應用於計算機的語義，當從相關單詞中理解給定單詞時，對單詞含義進行建模更容易。因此，語義網絡在計算語言學中很重要。儘管如此，語音學的其他方法（例如，使用晶格圖的最佳理論）和形態（例如使用有限態傳感器的有限狀態形態）在語言作為圖作為圖的分析中很常見。的確，該數學領域對語言學的有用性具有諸如文本圖和各種“網絡”項目（例如WordNet ， Merbnet等）等組織。

物理和化學

圖理論還用於研究化學和物理學的分子。在冷凝物理物理學中，可以通過收集與原子拓撲相關的圖理論特性的統計數據來定量研究複雜的模擬原子結構的三維結構。另外，“ Feynman的圖和計算規則以與人們想要理解的實驗數字密切接觸的形式總結了量子場理論。”在化學中，圖是一個分子的天然模型，其中頂點代表原子和邊緣鍵。這種方法特別用於分子結構的計算機處理，從化學編輯器到數據庫搜索。在統計物理學中，圖可以代表系統的交互部分之間的局部連接以及此類系統上物理過程的動力學。同樣，在計算中，神經科學圖可以用來表示相互作用的大腦區域之間的功能連接，以引起各種認知過程，其中頂點代表大腦的不同區域，而邊緣代表這些區域之間的連接。圖理論在電網的電氣建模中起重要作用，在這裡，權重與電線段的電阻相關，以獲得網絡結構的電性能。圖還用於表示多孔介質的微尺度通道，其中頂點代表孔，邊緣代表連接孔的較小通道。化學圖理論使用分子圖作為建模分子的一種手段。圖和網絡是研究和了解相變和關鍵現象的出色模型。去除節點或邊緣會導致關鍵過渡，其中網絡分解為小簇，該簇被研究為相變。通過滲透理論研究了這種分解。

社會科學

社會學中的圖理論：莫雷諾社會圖（1953）。

圖理論也被廣泛用於社會學，例如，以衡量參與者的聲望或探索謠言傳播的方式，特別是通過使用社交網絡分析軟件。在社交網絡的保護下是許多不同類型的圖形。熟人和友誼圖描述了人們是否彼此認識。影響圖模型某些人是否可以影響他人的行為。最後，協作圖表模特了兩個人是否以特定方式共同努力，例如一起在電影中表演。

生物學

同樣，圖理論在生物學和保護工作中也很有用，在生物學和保護工作中，頂點可以代表存在某些物種（或居住）的區域，並且邊緣代表區域之間的遷移路徑或運動。當研究繁殖模式或跟踪疾病，寄生蟲的傳播或運動變化如何影響其他物種時，此信息很重要。

圖也通常用於分子生物學和基因組學中，用於建模和分析具有復雜關係的數據集。例如，在單細胞轉錄組分析中，基於圖的方法通常用於將細胞一起“聚集”細胞類型。另一個用途是在途徑中對基因或蛋白質進行建模並研究它們之間的關係，例如代謝途徑和基因調節網絡。基因表達模式的進化樹，生態網絡和分層聚類也表示為圖結構。

圖理論也用於連接組學；神經系統可以看作是圖形，其中節點是神經元，邊緣是它們之間的連接。

數學

在數學中，圖在幾何形狀和拓撲的某些部分（例如結理論）中很有用。代數圖理論與群體理論有密切的聯繫。代數圖理論已應用於許多領域，包括動態系統和復雜性。

其他主題

可以通過將重量分配給圖形的每個邊緣來擴展圖形結構。具有權重或加權圖的圖表用於表示成對連接具有一些數值的結構。例如，如果圖代表道路網絡，則權重可以代表每條道路的長度。每個邊緣可能有幾個權重，包括距離（如上一個示例），旅行時間或貨幣成本。這種加權圖通常用於編程GPS，以及比較飛行時間和成本的旅行計劃搜索引擎。

歷史

Königsberg橋樑問題

萊昂哈德·歐拉（Leonhard Euler）在科尼格斯伯格（Königsberg）的七個橋樑上撰寫的論文並於1736年發表，被認為是圖理論史上的第一篇論文。本文以及范德曼德（Vandermonde）在《騎士問題》中撰寫的一篇論文，繼續由萊布尼茲（ Leibniz）發起的分析站點進行。 Cauchy and L'Huilier研究了Euler的配方，該公式與凸多面體的邊緣，頂點和麵的數量進行了研究，並代表了被稱為拓撲的數學分支的開始。

在歐拉（Euler）關於科尼格斯伯格（ Königsberg）橋樑的論文以及列表介紹拓撲概念的一個多世紀之後，凱利（Cayley）是由對特定分析形式的興趣領導的，該分析形式是從差分計算引起的，以研究特定的圖形圖，即樹木。這項研究對理論化學有許多影響。他使用的技術主要涉及具有特定特性的圖表的枚舉。然後，列舉圖理論源於Cayley的結果以及Pólya在1935年至1937年之間發表的基本結果。這些結果在1959年被De Bruijn推廣。Cayley將其結果與當代化學成分研究聯繫起來。數學中的思想與化學的思想融合開始了，這已成為圖理論標準術語的一部分。

特別是，西爾維斯特（Sylvester）在1878年發表的一篇論文中介紹了“圖”一詞，在那裡他在代數的“ quantic nofforniants”和“共同變化”和分子圖中進行了類比：

“ […]因此，每個不變和共變體都可以通過與kekuléan圖或化學掃描完全相同的圖表來表達。或給出單獨圖的共同變化。[…]”（斜體如原始圖）。

關於圖理論的第一本教科書是由DénesKőnig撰寫的，並於1936年出版。弗蘭克·哈里（ Frank Harary ）的另一本書於1969年出版，“被認為是這個主題的權威教科書”，並啟用了數學家，化學家，電氣，電氣，電氣工程師和社會科學家互相交談。 Harary捐贈了所有特許權使用費來資助Pólya獎。

圖理論中最著名和最令人興奮的問題之一是四個顏色問題：“確實，在飛機上繪製的任何地圖都可能具有四種顏色的區域，以使任何兩個具有共同邊界區域的區域都有不同的顏色？”這個問題首先是弗朗西斯·古斯里（Francis Guthrie）於1852年提出的，其第一張書面記錄是在同年De Morgan致漢密爾頓的一封信中。已經提出了許多不正確的證據，包括Cayley， Kempe等人的證據。 Tait ， Heawood ， Ramsey和Hadwiger對這一問題的研究和概括導致研究了嵌入具有任意屬的表面上的圖形的顏色。泰特（Tait）的重新印象產生了新的問題，即彼得森（Petersen ）和卡尼格（ Kőnig）研究的分解問題。拉姆齊（Ramsey）在色彩上的作品，更特別地是圖蘭（Turán）在1941年獲得的結果，是圖理論的另一個分支極限圖理論的起源。

一個多世紀以來，四種顏色問題仍未解決。 1969年，海因里希·海斯（Heinrich Heesch）發表了一種使用計算機解決該問題的方法。肯尼斯·阿佩爾（Kenneth Appel）和沃爾夫岡·哈肯（Wolfgang Haken）於1976年製作的計算機輔助證明是對Heesch開發的“出院”概念的基本利用。證明涉及通過計算機檢查1,936個配置的屬性，並且由於其複雜性而在當時未完全接受。羅伯遜，西摩，桑德斯和托馬斯僅給出了633種配置的簡單證明。

1860年和1930年從約旦，庫拉托夫斯基和惠特尼的作品回溯到拓撲的自主發展。圖理論和拓撲的共同發展的另一個重要因素來自現代代數技術的使用。這種用途的第一個例子來自物理學家古斯塔夫·基希霍夫（Gustav Kirchhoff）的工作，他於1845年出版了他的基希霍夫（Kirchhoff）巡迴法律，以計算電路中的電壓和電流。

圖理論中概率方法的引入，特別是在圖形連通性的漸近概率的ERDS和Rényi的研究中引起了另一個分支，稱為隨機圖理論，這是圖形理論結果的富有成效的來源。

表示

圖是在自然界中出現的關係的抽象。因此，它不能耦合到某個表示形式。表示的方式取決於便利程度，該表示為某個應用提供了。最常見的表示是視覺效果，其中通常由邊緣繪製和連接的頂點，而表的表行則提供了有關圖中頂點之間關係的信息。

視覺：圖形圖

主要文章：圖形圖

圖通常通過為每個頂點繪製一個點或圓而在視覺上表示，如果它們通過邊緣連接，則在兩個頂點之間繪製線。如果圖形是定向的，則通過繪製箭頭表示方向。如果圖形加權，則將重量添加在箭頭上。

圖形圖不應與圖形本身（抽象，非視覺結構）混淆，因為有幾種方法可以構建圖形圖。最重要的是，哪些頂點與其他頂點連接到其他頂點，而不是確切的佈局。實際上，通常很難確定兩個圖紙是否代表同一圖。根據問題域的不同，某些佈局可能比其他佈局更適合和更容易理解。

WT Tutte的開創性工作對圖形圖的主題非常有影響力。除其他成就外，他引入了線性代數方法獲取圖形圖。

圖形圖還可以說包括涉及交叉數字及其各種概括的問題。圖形的交叉數是平面中圖中圖的邊緣之間的交叉數量最小數量。對於平面圖，按定義，交叉數為零。還研究了除飛機以外的表面上的圖紙。

還有其他技術可以將圖形可視化遠離頂點和邊緣的圖形，包括圓形包裝，相交圖和鄰接矩陣的其他可視化。

表格：圖數據結構

主要文章：圖（摘要數據類型）

表格表示非常適合計算應用。在計算機系統中存儲圖形的方法有多種。所使用的數據結構取決於圖形結構和用於操縱圖的算法。從理論上講，人們可以區分列表和矩陣結構，但在具體應用中，最佳結構通常是兩者的組合。對於稀疏圖，通常首選列表結構，因為它們的內存要求較小。另一方面，矩陣結構為某些應用提供了更快的訪問，但可以消耗大量內存。在現代平行計算機架構上有效的稀疏基質結構的實現是當前調查的對象。

列表結構包括邊緣列表，一對頂點和鄰接列表，它們分別列出了每個頂點的鄰居：就像邊緣列表一樣，每個頂點都有一個與之相鄰的頂點的列表。

矩陣結構包括入射矩陣，0的矩陣和1的矩陣，其行表示頂點，其列代表邊緣，鄰接矩陣，其中行和列都由頂點索引。在這兩種情況下，1表示兩個相鄰對象，而0表示兩個非粘合對象。程度矩陣表示頂點程度。 Laplacian矩陣是鄰接矩陣的修改形式，該形式結合了有關頂點學位的信息，並且在某些計算中很有用，例如Kirchhoff的kirchhoff定理對圖的跨越樹的數量。距離矩陣就像鄰接矩陣一樣，具有由頂點索引的行和列，而不是在每個單元格中包含一個或1的1或1，而是包含兩個頂點之間的最短路徑的長度。

問題

枚舉

有關於圖形枚舉的大量文獻：計數圖形符合指定條件的問題。這項工作中有些是在Harary and Palmer（1973）中找到的。

子圖，誘導子圖和未成年人

一個常見的問題，稱為子圖同構問題，是在給定圖中找到固定的圖作為子圖。對這樣一個問題感興趣的原因之一是，許多圖形屬性是子圖的遺傳性，這意味著當且僅當所有子圖也都有時，圖形具有該屬性。不幸的是，找到某種類型的最大子圖通常是NP完整的問題。例如：

  • 找到最大的完整子圖稱為集團問題（NP完整）。

圖形同構的一種特殊情況是同構問題。它詢問兩個圖是否是同構。尚不清楚此問題是否是NP完整的，或者是否可以在多項式時間內解決。

一個類似的問題是在給定圖中找到誘導的子圖。同樣，一些重要的圖形性能是關於誘導子圖的遺傳性，這意味著當且僅當所有誘導子圖還具有它時，圖具有屬性。找到某種最大誘導的亞圖通常也是NP完整的。例如：

還有一個這樣的問題，即輔助遏制問題，是找到固定的圖作為給定圖的少數。圖的次要或亞匯集是通過取子圖並收縮一些（或沒有）邊緣獲得的任何圖。對於未成年人來說，許多圖形屬性都是遺傳性的，這意味著當且僅當所有未成年人都有它時，圖形具有屬性。例如，瓦格納（Wagner）的定理指出：

一個類似的問題，即細分遏制問題，是找到固定的圖作為給定圖的細分。圖形的細分或同構是通過細分某些（或沒有）邊緣獲得的任何圖。細分遏制與圖形屬性（例如平面度）有關。例如， Kuratowski的定理指出：

細分遏制的另一個問題是Kelmans -Seymour猜想：

另一類問題與圖形的各種物種和概括由它們的指數子圖決定的程度有關。例如：

圖形著色

主要文章：圖形著色

圖理論中的許多問題和定理與各種著色圖有關。通常，一個人有興趣對圖著色，因此沒有兩個相鄰的頂點具有相同的顏色，或者與其他相似的限制。一個人也可以考慮著色邊緣（可能是沒有兩個重合邊緣是相同的顏色）或其他變體。有關圖形著色的著名結果和猜想中有以下內容：

收集和統一

約束建模理論涉及按部分順序相關的定向圖的家族。在這些應用程序中，圖表是按特異性排序的，這意味著更具約束的圖（更具體的圖形，因此包含更多信息）由那些更一般的信息包含。圖之間的操作包括評估兩個圖（如果有）和計算圖統一之間的集合關係的方向。兩個參數圖的統一將其定義為與（IE包含所有信息中的所有信息）一致的最通用的圖（或其計算），如果存在這樣的圖形；有效的統一算法已知。

對於嚴格構圖的約束框架，圖統一是足夠的滿足性和組合功能。眾所周知的應用包括自動定理證明和建模語言結構的闡述。

路線問題

網絡流

尤其是由於應用程序與網絡中各種流量有關的應用程序出現的問題，例如：

可見性問題

涵蓋問題

覆蓋圖中的問題可能是指頂點/子圖子集的各種集合覆蓋問題。

  • 主體設置問題是設定覆蓋問題的特殊情況，集合是封閉的社區。
  • 頂點蓋問題是設置覆蓋問題的特殊情況，其中覆蓋的設置為每個邊緣。
  • 原始的設定蓋問題（也稱為擊球集）可以描述為超圖中的頂點蓋。

分解問題

分解，定義為分區圖的邊緣集（在分區每個部分的邊緣所需的必要位置上都有盡可能多的頂點），有各種各樣的問題。通常，問題是將圖分解為固定圖的子圖等構象。例如，將完整的圖分解為哈密頓週期。其他問題指定了應分解給給定圖的圖的家族，例如，一個循環家族，或將完整的圖k n分別分別為n -1個指定樹，分別為1，2，3，... ， n -1邊。

研究的一些特定分解問題包括：

圖類

許多問題涉及表徵各類圖的成員。此類問題的一些示例如下：

也可以看看

相關話題

演算法

亞洲

相關數學領域

概括

傑出的圖形理論家