此条目介绍的是图论中的基本研究对象。关于数学函数的图，请见“
函数图形 ”。关于抽象数据类型，请见“
图 (数据结构) ”。关于其他主题，请见“
图 ”。
在离散数学 中，图 （英语：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
∧
x
≠
y
}
{\displaystyle \{(x,y)\mid (x,y)\in V^{2}\wedge 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.
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 [2021-08-14 ] . （原始内容存档 于2011-08-26）. Bender, Edward A.; Williamson, S. Gill. Lists, Decisions and Graphs. With an Introduction to Probability . 2010 [2021-08-14 ] . （原始内容存档 于2021-08-17）. 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 [2021-08-14 ] . ISBN 978-3-540-26183-4存档 于2019-12-16）. 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 . MIT Press. 1977. 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存档 于2019-05-05）. 
