圖（離散數學）

在離散數學，更具體地說，在圖理論中，圖是一個結構，構成一組對象，其中某些對像在某種意義上是“相關”的對象。對應於稱為頂點的數學抽象（也稱為節點或點），並且每個相關的頂點對都稱為邊緣（也稱為鏈接或行）。通常，圖形以圖形形式描繪為一組點或圓的頂點，並以邊緣或曲線連接。圖是離散數學研究對象之一。

邊緣可能是指向或無方向性的。例如，如果頂點代表一個聚會上的人，並且兩個人握手之間會有優勢，那麼該圖是無方向性的，因為任何人A都可以與一個人握手B ，只有當B也與A握手時。相比之下，如果從一個人a到一個人的邊緣意味著欠了b的錢，則該圖是指向該圖的，因為欠款不一定是回報的。

圖是圖理論研究的基本主題。 JJ Sylvester在1878年首次使用“圖”一詞，這是由於數學與化學結構之間的直接關係（他稱為化學圖像圖像）。

定義

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

圖形

圖（有時稱為無方向的圖表，將其與有向圖區分開，或一個簡單的圖表，以區分多數法）是一對 $g =（ v ， e ）$ ，其中 $v$ 是其元素稱為頂點的集合（singular）：vertex），並且 $E$ 是一組配對的頂點，其元素稱為邊緣（有時鏈接或行）。

邊緣 ${x ， y}$ 的頂點 $x$ 和 $y$ 稱為邊緣的端點。據說邊緣加入 $X$ 和 $Y$ ，並在 $X$ 和 $Y$ 上發生。頂點可能屬於不邊緣，在這種情況下，它不會連接到任何其他頂點。

多編碼是一種概括，允許多個邊緣具有相同的端點。在某些文本中，多編碼簡稱為圖形。

有時，允許圖形包含循環，這些循環是將頂點連接到本身的邊緣。為了允許循環，必須允許 $E$ 中的頂點對具有相同的節點兩次。從允許循環的上下文中可以清楚地清楚時，這種廣義圖稱為具有循環的圖形或簡單的圖形。

通常，一組頂點 $V$ 應該是有限的。這意味著一組邊緣也是有限的。有時會考慮無限圖，但通常被視為一種特殊的二進制關係，因為有限圖上的大多數結果都不會擴展到無限的情況，或者需要相當不同的證據。

一個空圖是一個具有一個空的頂點集（因此是一個空的邊緣）的圖。圖的順序是其頂點的數量 $| V |$ 。圖的大小是它的邊數 $| E |$ 。但是，在某些情況下，例如表達算法的計算複雜性，大小為 $| V | + | E |$ （否則，非空圖可能具有尺寸為0）。頂點的程度或價值是出現的邊緣數。對於具有循環的圖形，對循環進行了兩次計數。

在 $n$ 階的圖中，每個頂點的最大度為 $n -1$ （如果允許循環，則 $n + 1$ ，因為環的貢獻為2），最大邊數為 $n （ n -1） /2$ （或 $n （ n + 1）/2$ ，如果允許循環）。

圖的邊緣定義了頂點上的對稱關係，稱為鄰接關係。具體而言，如果 ${x ， y}$ 是邊緣，則兩個頂點 $X$ 和 $Y$ 相鄰。圖形可以由其鄰接矩陣 $A$ （即 $n \times n$ Square矩陣）完全指定，其中 $IJ$ 指定了從頂點 $i$ 到頂點 $j$ 的連接數量。對於簡單的圖， $IJ$ 是0，指示斷開連接或1表示連接；此外， $a ii = 0$ ，因為簡單圖中的邊緣不能以同一頂點啟動和結束。帶有自動的圖表的特徵是某些或全部 $A II$ 等於正整數，而多編碼（在頂點之間具有多個邊緣）的特徵將以某些或全部 $A IJ$ 等於正整數的特徵。無向圖將具有對稱鄰接矩陣（含義 $a ij = a ji$ ）。

定向圖

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

在一個術語的限制但非常常見的意義中，有向圖是一對 $g =（ v ， e ），$ 包括：

$v$ ，一組頂點（也稱為節點或點）；
$e$ ，一組邊緣（也稱為有向邊，有向鏈接，有向線，箭頭或弧線），它們是訂購的一對不同的頂點： $\text{[math]}$ 。

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

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

從允許多個邊緣的術語的另一種一般意義上，有時將有針對的圖定義為包含的有序triple $g =（ v ， e ， ϕ ）$ ：

$v$ ，一組頂點（也稱為節點或點）；
$E$ ，一組邊緣（也稱為有向邊，有向鏈路，有向線，箭頭或弧）；
$ϕ$ ，一個入射函數將每個邊緣映射到有序的一對頂點（即，一個邊緣與兩個不同的頂點相關聯）： $\text{[math]}$ 。

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

循環是將頂點與自身相連的邊緣。上面兩個定義中定義的定向圖不能具有循環，因為一個循環連接了頂點 $\text{[math]}$ 本身就是邊緣（對於有向簡單的圖）或出現在（針對有向的多編碼）上 $\text{[math]}$ 不在 $\text{[math]}$ 。因此，要允許循環，必須擴展定義。對於定向的簡單圖，的定義 $\text{[math]}$ 應修改為 $\text{[math]}$ 。對於定向的多編碼，定義 $\text{[math]}$ 應修改為 $\text{[math]}$ 。為了避免歧義，這些類型的對象可以精確地稱為有向的簡單圖，允許循環和有向的多機允許循環（或箭話）。

允許循環 $g$ 的有向簡單圖 $的$ 邊緣是 $G$ 的G。具體而言，對於每個邊緣 $（ x ， y ）$ ，其端點 $x$ 和 $y$ 彼此相鄰，表示 $為 x〜y$ 。

混合圖

混合圖是一個圖形，其中一些邊緣可能被指向，有些邊緣可能是無方向性的。對於混合的簡單圖，它是一個有序的三重 $g =（ v ， e ， a ），$ $g =（ v ， e ， a ， ϕ e ， ϕ a ）$ ，用於 $v$ ， $e$ （無方向的邊緣）， $a$ （定向的邊緣）， $ϕ e$ 和 $ϕ a$ 定義如上上述。定向和無向圖是特殊情況。

加權圖

加權圖或網絡是一個圖形，其中一個數字（權重）分配給每個邊緣。此類權重可能代表例如成本，長度或能力，具體取決於手頭的問題。這些圖在許多情況下都出現，例如在最短的路徑問題中，例如旅行推銷員問題。

圖的類型

定向圖

面向圖的一個定義是它是一個有向圖，其中（ x ， y ）和（ y ， x ）最多可以是圖形的邊緣。也就是說，它是一個有向圖，可以作為無向（簡單）圖的方向形成。

一些作者使用“定向圖”表示與“有向圖”相同。一些作者使用“定向圖”來表示給定的無向圖或多編碼的任何方向。

常規圖

常規圖是一個圖形，其中每個頂點具有相同數量的鄰居，即每個頂點具有相同的度。具有k的頂點的常規圖稱為k-常規圖或度量k的常規圖。

完整的圖

完整的圖是一個圖形，其中每對頂點與邊緣連接在一起。完整的圖包含所有可能的邊緣。

有限圖

有限圖是一個圖形，其中頂點集和邊緣集為有限集。否則，它被稱為無限圖。

在圖理論中最常見的是，所討論的圖是有限的。如果圖形是無限的，通常是特定說明的。

連接的圖

在一個無方向的圖中，如果路徑從x到y ，則稱為無序的頂點{ x ， y } 。否則，無序對被稱為斷開連接。

連接的圖是一個無方向的圖形，其中每個無序的頂點都連接了。否則，稱為斷開的圖。

在有向圖中，如果有向路徑從x到y ，則有序的一對頂點（ x ， y ）被稱為強烈連接。否則，如果無方向的路徑從x到y，則有序對被稱為弱連接。否則，有序對被稱為斷開連接。

強烈連接的圖是一個有向圖，其中圖中的每個有序的對頂點都可以強烈連接。否則，如果圖中的每個有序的頂點均弱連接，則稱為弱連接的圖。否則，它被稱為斷開圖。

k-vertex連接的圖或K邊緣連接的圖是一個圖，其中不存在一組k -1個頂點（分別是邊緣），當刪除時，將其斷開圖形。 k vertex相互連接的圖通常稱為k連接圖。

兩部分圖

兩部分圖是一個簡單的圖形，可以將頂點集分為兩個集合W和X ，因此W中沒有兩個頂點共享一個共同的邊緣和X中的兩個頂點共享一個共同的邊緣。或者，它是一個具有2個色數為2的圖形。

在完整的兩部分圖中，頂點集是兩個不相交的W和X的聯合，因此W中的每個頂點都與X中的每個頂點相鄰，但是W或X中沒有邊緣。

路徑圖

路徑圖或線性n≥2的線性圖是一個圖形，可以在該圖中列出頂點v ₁ ， v ₂ ，…， v _n ，使邊緣為{ v _i ， v _{i +1} }，其中i = 1 ，2，…， n - 1.路徑圖可以表徵為連接圖的圖形，其中兩個頂點的全部程度為2，兩個剩下的頂點的程度為1。如果路徑圖作為子圖表出現在另一個圖中，它是該圖的路徑。

平面圖

平面圖是一個圖形，其頂點和邊緣可以在平面中繪製，因此沒有兩個邊緣相交。

週期圖

n≥3順序的循環圖或圓形圖是一個圖，可以在該圖中列出頂點v ₁ ， v ₂ ，…， v _n ，使邊緣為{ v _i ， v _{i +1} }，其中i = 1，2，…， n -1，加上邊緣{ v _n ， v ₁ } 。可以將循環圖描述為所有頂點的連接圖，其中所有頂點的程度為2。如果循環圖作為另一個圖的子圖出現，則該圖是該圖中的循環或電路。

樹

樹是一個無向圖，其中任何兩個頂點都通過一個路徑連接，或等效地連接的無向圖。

森林是一個無方向的圖，其中任何兩個頂點在最多的路徑上都通過一個路徑連接，或者等效地是無向圖，或者等效地相等的樹木結合。

Polytree

Polytree （或定向的樹或定向的樹或單一連接的網絡）是有向的無環圖（DAG），其基本的無向圖是樹。

多孔（或定向森林或定向森林）是一個有向的無環圖，其基本的無向圖是森林。

高級課程

更高級的圖形是：

圖的屬性

如果圖形共享一個共同的頂點，則將兩個圖的邊緣稱為相鄰。如果第一個頭的頭是第二個尾部，則稱為有向圖的兩個邊緣被稱為連續。同樣，如果兩個頂點共享一個共同的邊緣（如果第一個是尾巴是尾巴，第二個是邊緣的頭部），則稱其為相鄰，在這種情況下，公共邊緣據說可以連接兩個頂點。邊緣上的邊緣和頂點稱為事件。

只有一個頂點且沒有邊緣的圖形稱為瑣碎圖。只有頂點和沒有邊緣的圖形被稱為無進度圖。沒有頂點且沒有邊緣的圖形有時稱為空圖或空圖，但是術語不一致，並非所有數學家都允許此對象。

通常，圖形的頂點（作為集合的元素）是可以區分的。這種圖可以稱為頂點標記。但是，對於許多問題，最好將頂點視為無法區分。（當然，頂點仍然可以通過圖形本身的屬性（例如，入射邊緣的數量）來區分。）相同的備註適用於邊緣，因此帶有標記邊緣的圖稱為邊緣標記。帶有邊緣或頂點的標籤的圖形被標記為標籤。因此，頂點無法區分且邊緣無法區分的圖稱為未標記。（在文獻中，標記的術語可能適用於其他類型的標籤，此外僅用於區分不同的頂點或邊緣。）

所有圖的類別是逗號類別集↓ d其中d ：set→set是將s s s s to s × s的函數。

例子

該圖是圖形的示意圖 $\text{[math]}$ 和邊緣 $\text{[math]}$
在計算機科學中，有針對性的圖表代表知識（例如，概念圖），有限狀態機和許多其他離散結構。
集合X上的二進制關係R定義了有向圖。 x的元素x是x的元素y的直接前身，僅當xry時。
有向圖可以建模信息網絡，例如Twitter ，一個用戶跟隨另一個用戶。
特別定期的有向圖的例子由有限生成的組的Cayley圖以及Schreier coset圖給出
在類別理論中，每個小型類別都有一個基本的定向多編碼，其頂點是類別的對象，並且其邊緣是類別的箭頭。在類別理論的語言中，有人說，從小類類別到Quivers類別有一個健忘的函數。

圖形操作

有幾種從初始圖表產生新圖表的操作，這些圖可能分為以下類別：

單一操作，從初始圖創建新圖，例如：
- 邊緣收縮，
- 線形圖，
- 雙圖，
- 補體圖，
- 圖形重寫；
二進制操作，從兩個初始圖創建一個新圖，例如：
- 圖形的不結合聯合，
- 圖形的笛卡爾產品，
- 圖形的張量產品，
- 圖形的強產物，
- 圖的詞典產物，
- 串聯 - 平行圖。

概括

在超圖中，邊緣可以連接兩個以上的頂點。

一個無向圖可以看作是由1-簡單（邊緣）和0個簡化（頂點）組成的簡單複合物。因此，複合物是圖形的概括，因為它們允許更高維度的簡單。

每個圖都會產生矩形。

在模型理論中，圖只是一個結構。但是在那種情況下，邊緣數量沒有限制：它可以是任何基數，請參見連續圖。

在計算生物學中，功率圖分析將功率圖引入了無向圖的替代表示。

在地理信息系統中，幾何網絡是在圖表後密切建模的，並從圖理論借用許多概念來對道路網絡或實用程序網格進行空間分析。