此頁面介紹的是圖論中的基本研究對象。關於數學函數的圖，請見「
函數圖形 」。關於抽象數據結構，請見「
圖 (數據結構) 」。關於其他主題，請見「
圖 」。
在離散數學 中，圖 （Graph ）是用於表示物體與物體之間存在某種關係的結構。數學抽象後的「物體」稱作節點 頂點 （英語：Vertex，node或point ），節點間的相關關係則稱作邊 [ 1] 描繪 一張圖的時候，通常用一組點或小圓圈表示節點，其間的邊則使用直線或曲線。
一個有6個頂點，7條邊的圖 圖中的邊可以是有方向或沒有方向的。例如在一張圖中，如果節點表示聚會上的人，而邊表示兩人曾經握手，則該圖就是沒有方向的，因為甲和乙握過手也意味着乙一定和甲握過手。相反，如果一條從甲到乙的邊表示甲欠乙的錢，則該圖就是有方向的，因為「曾經欠錢」這個關係不一定是雙向的。前一種圖稱為無向圖 有向圖
圖是圖論 中的基本概念。1878年，詹姆斯·西爾維斯特 首次使用「圖」這一名詞：他用圖來表示數學和化學分子結構 之間的關係（他稱為「化學圖」，英語：chemico-graphical image ）。[ 2] [ 3]
在圖論中，圖的定義有很多。下面是一些比較基本的定義方式以及與它們相關的數學結構 。
一張有3個節點和3條邊的圖 一張圖（為了和有向圖 無向圖 ；為了和多重圖 區分，也稱簡單圖 ）[ 5] 二元組 G = (V , E )V 節點 ，集合E 邊 。集合V 點集 ，E 邊集 。
一條邊
{
x
,
y
}
{\displaystyle \{x,y\}}
x y 頂點 或端點 ；也說這條邊連接 了節點x y x y 關聯 （英語：incident ）。一個節點可以不屬於任何邊，即它不與任何節點相連。由於
{
x
,
y
}
{\displaystyle \{x,y\}}
{
x
,
y
}
{\displaystyle \{x,y\}}
{
y
,
x
}
{\displaystyle \{y,x\}}
更一般地，多重圖 的定義中允許同一對節點之間存在多條不同的邊。在特定語境中，多重圖也可以直接稱作圖。[ 7] E 應該為多重集 。
有時，圖的定義中允許自環 （簡稱環 ，英語：loop 自環圖 。
點集V 一般是有限集；這意味着邊集E 也是有限集（不考慮多重圖）。相對地，無限圖 二元關係 。
一個點集為空集 的圖稱為空圖 （因此邊集也是空集）。圖的階 （英語：order ）是指其中節點的數量，即|V 邊數 是指其邊的數量，即|E 大小 （size ）一般也指圖的邊數。但在一些語境中，例如描述算法複雜度 的時候，圖的大小是指|V E 度 （英語：degree或valency ）是指連接到該節點的邊的數量；對於允許自環的圖，環要算做兩條邊（因為兩端都連接到這個節點）。
如果一個圖的階是n n -1n n (n − 1)/2n (n + 1)/2
在圖的定義中，邊的概念定義了節點上的一個對稱關係 ，即「鄰接」關係（英語：adjacency relation ）。具體地說，對於兩個節點x y
{
x
,
y
}
{\displaystyle \{x,y\}}
鄰接矩陣 A 來表示，即一個
n
×
n
{\displaystyle n\times n}
Aij 表示節點i 和j 之間的邊的數量。對於一個簡單圖，總有
A
i
j
∈
{
0
,
1
}
{\displaystyle A_{ij}\in \{0,1\}}
A
i
i
=
0
{\displaystyle A_{ii}=0}
A
i
i
{\displaystyle A_{ii}}
A
i
j
{\displaystyle A_{ij}}
A
i
j
=
A
j
i
{\displaystyle A_{ij}=A_{ji}}
一張3個節點和4條邊組成的有向圖（雙向箭頭表示兩個方向上各有一條邊） 邊為有方向的圖稱作有向圖 （英語：directed graph 或digraph
有向圖的一種比較嚴格的定義是這樣的：一個二元組
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
V
{\displaystyle V}
節點 的集合；
E
⊆
{
(
x
,
y
)
∣
(
x
,
y
)
∈
V
2
∧
x
≠
y
}
{\displaystyle E\subseteq \{(x,y)\mid (x,y)\in V^{2}\wedge x\neq y\}}
邊 （也稱為有向邊 ，英語：directed edge 或directed link 弧 ，英語：arcs 為了和多重圖區分，這樣的有向圖也稱為有向簡單圖 。
在從
x
{\displaystyle x}
y
{\displaystyle y}
(
x
,
y
)
{\displaystyle (x,y)}
x
{\displaystyle x}
y
{\displaystyle y}
頂點 ，其中
x
{\displaystyle x}
起點 或尾 （英語：tail ），
y
{\displaystyle y}
終點 或頭 。也說這條邊連接 了節點
x
{\displaystyle x}
y
{\displaystyle y}
x
{\displaystyle x}
y
{\displaystyle y}
關聯 。一張有向圖中的節點可以不屬於任何一條邊。邊
(
y
,
x
)
{\displaystyle (y,x)}
(
x
,
y
)
{\displaystyle (x,y)}
反向邊 。
節點的出度 （英語：out-degree ）是指起點為該節點的邊的數量；節點的入度 （英語：in-degree ）是指終點為該節點的邊的數量。
更一般地，如果一張有向圖允許多條頭尾都相同的邊，則稱這樣的圖為有向多重圖 ，這樣的邊稱為多重邊 有向圖 是這樣的三元組
G
=
(
V
,
E
,
ϕ
)
{\displaystyle G=(V,E,\phi )}
V
{\displaystyle V}
E
{\displaystyle E}
ϕ
:
E
→
{
(
x
,
y
)
∣
(
x
,
y
)
∈
V
2
∧
x
≠
y
}
{\displaystyle \phi :E\to \{(x,y)\mid (x,y)\in V^{2}\wedge x\neq y\}}
關聯函數 ，將每條邊映射到一個由頂點組成的有序對上（即一條邊被按順序關聯到兩個頂點）。自環是指一條起點和終點相同的邊。前面的兩個定義都不允許自環，因為若節點
x
{\displaystyle x}
(
x
,
x
)
{\displaystyle (x,x)}
{
(
x
,
y
)
∣
(
x
,
y
)
∈
V
2
and
x
≠
y
}
{\displaystyle \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\}}
E
{\displaystyle E}
E
⊆
{
(
x
,
y
)
∣
(
x
,
y
)
∈
V
2
}
{\displaystyle E\subseteq \{(x,y)\mid (x,y)\in V^{2}\}}
ϕ
{\displaystyle \phi }
ϕ
:
E
→
{
(
x
,
y
)
∣
(
x
,
y
)
∈
V
2
}
{\displaystyle \phi :E\to \{(x,y)\mid (x,y)\in V^{2}\}}
允許自環的有向簡單圖 或允許自環的有向多重圖 （英語：quiver
在允許自環的有向簡單圖
G
{\displaystyle G}
V
{\displaystyle V}
齊次關係
∼
{\displaystyle \sim }
G
{\displaystyle G}
鄰接關係 。
對於頂點是
x
{\displaystyle x}
y
{\displaystyle y}
(
x
,
y
)
{\displaystyle (x,y)}
x
{\displaystyle x}
y
{\displaystyle y}
鄰接 的，記作
x
∼
y
{\displaystyle x\sim y}
邊既可以有向、也可以無向的圖稱作混合圖 。混合簡單圖 是一個多元組G = (V , E , A )混合多重圖 則是多元組G = (V , E , A , ϕ E ϕ A V 、E （無向邊集）、A （有向邊集）、ϕ E ϕ A
一張有10個節點和12條邊的賦權圖 賦權圖 （英語：weighted graph ，也稱加權圖 、網絡 （英語：network ））[ 10] [ 11] weight ）的圖。[ 12] 最短路徑問題 和旅行商問題 等問題中。
子圖 （subgraph ）：對於圖
G
{\displaystyle G}
G
′
{\displaystyle G'}
V
(
G
′
)
⊆
V
(
G
)
{\displaystyle V(G')\subseteq V(G)}
E
(
G
′
)
⊆
E
(
G
)
{\displaystyle E(G')\subseteq E(G)}
G
′
{\displaystyle G'}
G
{\displaystyle G}
生成子圖 （spanning subgraph ）：指滿足條件
V
(
G
′
)
=
V
(
G
)
{\displaystyle V(G')=V(G)}
G
{\displaystyle G}
G
′
{\displaystyle G'}
鏈 (chain或walk )、軌跡 (trail )、路徑 (path )：鏈是頂點
v
i
{\displaystyle v_{i}}
e
i
{\displaystyle e_{i}}
W
=
v
i
0
e
i
0
v
i
1
.
.
.
e
i
k
v
i
k
{\displaystyle W=v_{i_{0}}e_{i_{0}}v_{i_{1}}...e_{i_{k}}v_{i_{k}}}
k 的鏈，其中
v
i
0
{\displaystyle v_{i_{0}}}
v
i
k
{\displaystyle v_{i_{k}}}
兩端點相同的鏈和跡分別稱為閉鏈（或環，cycle ）、閉跡（或迴路，circuit ）。
距離 （Distance）： 從頂點
u
{\displaystyle u}
v
{\displaystyle v}
u
{\displaystyle u}
v
{\displaystyle v}
正則圖 是指每個節點的鄰居 （英語：neighbor ）數量都相同的圖，即每個節點的度都相同的圖。節點的度為k 的正則圖也稱作k -正則圖。
一張有5個節點和10條邊的完全圖，其中每個節點都和所有其它節點相連。 完全圖 （英語：complete graph ）是指每對節點之間都有一條邊相連的圖。一張完全圖包含簡單圖所有可能出現的邊。
有限圖 （英語：finite graph ）是指點集和邊集是有限集 的圖。否則，則稱為無限圖 。在不加說明的情況下，圖論中討論的圖大多是有限圖。
在無向圖中，如果存在x 和y 之間的路徑 ，則稱此兩節點的無序對
{
x
,
y
}
{\displaystyle \{x,y\}}
連通 的；否則，則稱此兩點是非聯通 的。
連通圖 是指每對節點都連通的無向圖。否則，則稱圖是非連通圖 。
在有向圖中，如果存在x 和y 之間的有向路徑，則稱此兩節點的有序對
{
x
,
y
}
{\displaystyle \{x,y\}}
強連通 的。此外，若將圖中的所有邊都換為無向邊，得到的無向圖中存在x 和y 之間的路徑，則稱此兩節點是弱連通 的。否則，則稱此兩點是非聯通 的。
強連通圖 是指每對節點都強連通的有向圖。此外，弱連通圖 是指每對節點都弱聯通的有向圖。否則，則稱圖是非連通圖 。
對於一張圖，若不存在大小為k − 1k -點連通圖k -邊連通圖k -點連通圖通常也簡稱k -連通圖。
二分圖 （英語：bipartite graph ）是指這樣的簡單圖：其點集可以被劃分 稱兩個集合W 和X ，其中W 中的任意兩個節點之間沒有邊相連，X 中的任意兩個節點之間也沒有邊相連。二分圖是點着色 色數為2的圖。
若一張圖的點集是兩個集合W 和X 的無交並 ，使得W 中的任意節點都和X 中的所有節點鄰接，且W 或X 之內沒有邊，則稱此圖是[[[完全二分圖]]] 。
平面圖 是指可以將其節點和邊畫在平面上，而沒有兩邊相交的圖。
階為n ≥3循環圖 （英語：cycle graph ）或環形圖 （英語：circular graph ）是指其節點可以列為v 1 , v 2 , …, v n
{
v
i
,
v
i
+
1
}
{\displaystyle \{v_{i},v_{i+1}\}}
i =1, 2, …, n − 1，以及
{
v
n
,
v
1
}
{\displaystyle \{v_{n},v_{1}\}}
環 。
樹 是指任意兩點之間都有且僅有一條路徑的無向圖。等價地，樹 是一個連通無環 無向圖。
森林 是指任意兩點之間至多 僅有一條路徑的無向圖。等價地，森林 是一個無環無向圖，或一組樹的無交並 。
一張6個節點和7條邊的圖 右邊的圖示是一個點集為
V
=
{
1
,
2
,
3
,
4
,
5
,
6
}
{\displaystyle V=\{1,2,3,4,5,6\}}
E
=
{
{
1
,
2
}
,
{
1
,
5
}
,
{
2
,
3
}
,
{
2
,
5
}
,
{
3
,
4
}
,
{
4
,
5
}
,
{
4
,
6
}
}
{\displaystyle E=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}}
在計算機科學 中，有向圖可以用於表示概念圖 有限狀態自動機 ，以及其它許多數據結構。
任意集合X 上的二元關係 R 都可定義一個有向圖。X 中的元素x 到y 有一條邊，若且唯若xRy 。
有向圖可以用於表示信息網絡。例如，在推特 上，用戶之間的關注關係可以用有向圖表示。
圖上可以進行一些運算或變換，使一個圖變為另一個圖：
一元運算 ，將一個圖變換為另一個圖，例如：
二元運算 ，結合兩個圖為一個新圖，例如：
圖的無交並 圖的笛卡爾乘積 圖的張量積 圖的強乘積 圖的字典積 圖的串並聯
在超圖 中，允許一條邊連接多於兩個節點。
無向圖可以看作是由1-單純形 （邊）和0-單純形（節點）組成的單純復形 。由此，復形成為圖的推廣，其中允許維度更高的單純形。
圖可以看作是一種擬陣 。
在模型論 中，圖是一個結構 。這樣一來，邊的數量可以是任意基數 。參見圖極限 。
在計算生物學 中，冪圖
在地理信息系統 中，為了進行道路網絡或電網的時空分析而提出的幾何網絡
參見 Iyanaga and Kawada, 69 J , p. 234 or Biggs, p. 4.
Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne. Foundations of Discrete Mathematics International student. Boston: PWS-KENT Pub. Co. 1991: 463. ISBN 978-0-53492-373-0A weighted graph is a graph in which a number w(e) , called its weight , is assigned to each edge e .
Introduction To Graph Theory , by Gary Chartrand and Ping Zhang, McGraw Hill徐, 俊明. 图论及其应用 第二版. 合肥: 中國科學技術大學出版社. 2004. ISBN 7-312-00979-4 Balakrishnan, V. K. Graph Theory 1st. McGraw-Hill. 1997. ISBN 978-0-07-005489-9 Bang-Jensen, J.; Gutin, G. Digraphs: Theory, Algorithms and Applications . Springer. 2000. Bender, Edward A.; Williamson, S. Gill. Lists, Decisions and Graphs. With an Introduction to Probability . 2010. Berge, Claude. Théorie des graphes et ses applications. Paris: Dunod. 1958 （法語） . Biggs, Norman. Algebraic Graph Theory 2nd. Cambridge University Press. 1993. ISBN 978-0-521-45897-9 Bollobás, Béla. Modern Graph Theory 1st. Springer. 2002. ISBN 978-0-387-98488-9 Diestel, Reinhard. Graph Theory 3rd. Berlin, New York: Springer-Verlag. 2005. ISBN 978-3-540-26183-4 Graham, R.L.; Grötschel, M.; Lovász, L. Handbook of Combinatorics. MIT Press. 1995. ISBN 978-0-262-07169-7 Gross, Jonathan L.; Yellen, Jay. Graph Theory and Its Applications. CRC Press. 1998. ISBN 978-0-8493-3982-0 Gross, Jonathan L.; Yellen, Jay. Handbook of Graph Theory. CRC. 2003. ISBN 978-1-58488-090-5 Harary, Frank. Graph Theory. Addison Wesley Publishing Company. 1995. ISBN 978-0-201-41033-4 Iyanaga, Shôkichi; Kawada, Yukiyosi. Encyclopedic Dictionary of Mathematics ISBN 978-0-262-09016-2 Zwillinger, Daniel. CRC Standard Mathematical Tables and Formulae 31st. Chapman & Hall/CRC. 2002. ISBN 978-1-58488-291-6 Trudeau, Richard J. Introduction to Graph Theory Corrected, enlarged republication. New York: Dover Publications . 1993 [8 August 2012] . ISBN 978-0-486-67870-2 
