图

在数学中，更具体地说，在图论 中，图 Graph是一组对象的结构，其中一些对象组在某种意义上是“相关的”。这些对象在数学上对应地称为顶点 Vertex（也称为节点 Node或点 Point），顶点对间的关系称为边 Edge（也称为链 Link或线 Line）。通常，图 Graph以图解 Diagram的形式表示，一组点或圆圈表示顶点，由表示边的直线或曲线连接。图是离散数学的研究对象之一。

边可以是有向的或无向的。例如，如果用顶点表示参加某次聚会的人，两个人握手即在两顶点间建立一条边，那么我们得到的图是无向的，因为A和B握手当且仅当B也和A握手。与之相对，如果从A到B的连边表示A欠B的钱，那么我们得到的图就是有向的，因为欠钱这个关系不一定是互换的。前者称为无向图 Undirected graph，后者称为有向图 Directed graph。

图是图论研究的基本课题。 1878年，詹姆斯·约瑟夫·西尔维斯特 James Joseph Sylvester首次在这个意义上使用了“graph”一词。 

定义

图论中的定义各不相同。下面是定义图和相关数学结构的一些较基本的方法。

无向图

文件:Undirected.svg.png

有三个顶点和三条边的图

图（有时称为无向图以区别于有向图，或简单图 Simple graph以区别于多重图 Multigraph）是一个有序对 [math]\displaystyle{ G(V,E) }[/math]，其中 [math]\displaystyle{ V }[/math] 是顶点集， [math]\displaystyle{ E }[/math] 是边集。

边 [math]\displaystyle{ (x,y) }[/math] 的顶点 [math]\displaystyle{ x }[/math] 和 [math]\displaystyle{ y }[/math] 称为边的端点 Endpoint。边称为连接 Join/incident on [math]\displaystyle{ x }[/math] 和 [math]\displaystyle{ y }[/math]。某顶点可能不属于任意一条边。

多重图是允许多条边连接同一对顶点的图。一些文献将多重图简单地称为图。

有时，图可以包含自环 loop，即把一个顶点与自身连接的边。为允许自环，上述定义必须将边改定义为两个顶点的多重集 Multiset。这种广义图被称为带自环的图 Graphs with loops；从上下文易看出允许自环时，也可简单称为图。

一般来说，顶点集[math]\displaystyle{ V }[/math]是有限的；这意味着边集也是有限的。 无限图 Infinite graph有时被认为是一种特殊的二元关系 Binary relation，因为有限图的大多数结论不能推广到无限情形，或者需要一个迥异的证明。

空图 Empty graph是顶点集为空集 Empty set（因而边集也为空）的图。 图的阶 Order是其顶点数 [math]\displaystyle{ |V| }[/math]，图的尺寸 Size为其边数 [math]\displaystyle{ |E| }[/math]；然而，在某些情形下，例如为了表示算法的计算复杂性 Computational complexity，尺寸 Size大小为 [math]\displaystyle{ |V|+ | E | }[/math]（否则，非空图的尺寸可能为0）。顶点的度 Degree/valency是关联于该顶点的边的数目；对带自环的图，自环会被算两次。

在 [math]\displaystyle{ n }[/math] 阶图中，每个顶点的最大度为 [math]\displaystyle{ n-1 }[/math]（允许自环时为 [math]\displaystyle{ n-1 }[/math]），图的最大边数为 [math]\displaystyle{ n (n-1) / 2 }[/math]（允许自环时为 [math]\displaystyle{ n (n+1) / 2 }[/math]）。

图的边在顶点上定义一个对称关系 Symmetric relation，称为邻接关系 Adjacency relation。 具体来说，如果 [math]\displaystyle{ (x,y) }[/math] 是边，两个顶点 [math]\displaystyle{ x }[/math] 和 [math]\displaystyle{ y }[/math] 是邻接的 Adjacent。

有向图

有三个顶点和四条有向边的有向图（双箭头表示双指向）

有向图 Directed graph /digraph是边有方向的图。通常定义为一个有序对 Ordered pair [math]\displaystyle{ G=(V,E) }[/math]，其中

• [math]\displaystyle{ V }[/math] 是顶点 Vertex/Node/Point的集合；
• [math]\displaystyle{ E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\} }[/math] 是边/弧 Edge/Directed edge/Directed link/Directed line/Arrow/Arc的集合，边由所有不同顶点的有序对 Ordered pair构成（换句话说，边连接了顶点对）。

为避免歧义，上面定义的对象可被更精准地称作有向简单图 Directed simple graph。

在从 [math]\displaystyle{ x }[/math] 指向 [math]\displaystyle{ y }[/math] 的边 [math]\displaystyle{ (x,y) }[/math] 中，顶点 [math]\displaystyle{ x }[/math] 和 [math]\displaystyle{ y }[/math] 称为边的端点 Endpoints，[math]\displaystyle{ x }[/math] 为边的尾部 Tail ，[math]\displaystyle{ y }[/math] 为边的头部 Head。 边 [math]\displaystyle{ (y,x) }[/math] 称为 [math]\displaystyle{ (x,y) }[/math] 的Inverted edge。边称为连接 Join/Incident on [math]\displaystyle{ x }[/math] 和 [math]\displaystyle{ y }[/math]。 图中的某顶点可能不属于任意一条边。自环 Loop是连接顶点与自身的边。重边 Multiple edges是连接同一对顶点的两条或多条边。

允许重边时，上述定义可以推广：有向图是有序三元组 Ordered triple [math]\displaystyle{ G=(V,E,\phi) }[/math]，其中

• [math]\displaystyle{ V }[/math] 是点集；
• [math]\displaystyle{ E }[/math] 是边集；
• [math]\displaystyle{ \phi:E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\} }[/math] 是一个将每条边映射到不同顶点的一个有序对的关联函数 Incidence function（于是边连接了顶点对）。

为避免歧义，上面定义的对象可被更精准地称作有向多重图 Directed multigraph。

上述两个定义中的图不能有自环。为了允许自环，需要扩展定义。对于有向简单图，[math]\displaystyle{ E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\} }[/math] 应为 [math]\displaystyle{ E\subseteq\left\{\left\{x,y\right\}:(x,y)\in V^2 \right\} }[/math]。对于有向多重图，[math]\displaystyle{ E\to\left\{\left\{x,y\right\}:(x,y)\in V^2,x\neq y\right\} }[/math] 应为 [math]\displaystyle{ E\to\left\{\left\{x,y\right\}:(x,y)\in V^2\right\} }[/math]。为避免歧义，这些类型的对象可以分别称为带自环的有向简单图 Undirected simple graph permitting loops和带自环的有向多重图 Undirected multigraph permitting loops/箭图 Quiver。

带自环的有向简单图 [math]\displaystyle{ G }[/math] 在其顶点上诱导出一个对称齐次关系 Homogeneous relation，称为 [math]\displaystyle{ G }[/math] 的邻接关系 Adjacency relation。具体来说，对每条边 [math]\displaystyle{ (x,y) }[/math]，端点[math]\displaystyle{ x }[/math] 和 [math]\displaystyle{ y }[/math] 称为彼此邻接 Adjacent ，表示为 [math]\displaystyle{ x\sim y }[/math]。

混合图

混合图 Mixed graph是可能既有有向边又有无向边的图。混合简单图 Mixed simple graph为有序三元组 [math]\displaystyle{ G=(V,E,A) }[/math]；混合多重图 Mixed multigraph为 [math]\displaystyle{ G=(V,E,A,\phi_E,\phi_A) }[/math]，其中[math]\displaystyle{ V,E }[/math]（无向边），[math]\displaystyle{ A }[/math]（有向边），[math]\displaystyle{ \phi_E,\phi_A }[/math] 定义如上。有向图和无向图是其特殊情形。

加权图

文件:Weighted graph.png

有十个顶点和十二条边的加权图

加权图 Weighted graph或网络 Network是每条边都分配有一个数字（权重）的图。这种权重可能代表成本、长度或容量，这取决于要解决的问题。加权图应用广泛，如最短路径问题 Shortest path problem（举例：旅行推销员问题 Traveling salesman problem）。

类型

定向图

定向图 Oriented graph是一个边 [math]\displaystyle{ (x,y) }[/math] 和 [math]\displaystyle{ (y,x) }[/math] 中至多有一个是其边的有向图。也就是说，它可以由给无向图的每条边取定方向 Orientation而得来。不过，有些人用oriented graph来表示与directed graph相同的意思。

正则图

正则图 Regular graph是所有顶点的度皆相等的图。具有 [math]\displaystyle{ k }[/math] 度顶点的正则图称为k正则图 K‑regular graph/regular graph of degree k。

完全图

有五个顶点和十条边的完全图。任一顶点到其余每个顶点都有一条边

完全图 Complete graph是每一对不同顶点间都有边相连的的图。一个完全图包含所有可能的边。

有限图

有限图 Finite graph是顶点集和边集都是有限集 Finite set的图，否则称为无限图 Infinite graph。

图论中一般认为所讨论的图都是有限的。如果图是无限的，通常会特别说明。

连通图

在无向图中，如果顶点的无序对 [math]\displaystyle{ (x,y) }[/math] 间有路径相连，则称其为连通的 Connected，否则称其不连通 Disconnected。

如果无向图中任意顶点对都是连通的，则称其为连通图 Connected graph，否则称为非连通图 Disconnected graph。

在有向图中，如果有序的顶点对 [math]\displaystyle{ (x,y) }[/math] 间有一条从 [math]\displaystyle{ x }[/math] 到 [math]\displaystyle{ y }[/math] 的有向路径，则称其为强连通的 Strongly connected。如果将其全部有向边替换为无向边，顶点对间有一条从 [math]\displaystyle{ x }[/math] 到 [math]\displaystyle{ y }[/math] 的无向路径，则称其为弱连通的 Weakly connected。 否则，称为非连通的 Disconnected。 如果一个有向图每个有序顶点对都是强连通的，则称其为强连通图 Strongly connected graph。如果其中每个有序顶点对都是弱连通的，则称之为弱连通图 Weakly connected graph。否则，称其为非连通图 Disconnected graph。

如果图中找不到任意一个含 [math]\displaystyle{ k-1 }[/math] 个顶点或边的集合，使其在移除该集合后变为非连通的，则称其为k-顶点连通图 K-vertex-connected graph或k-边连通图 K-edge-connected graph。k-vertex-connected graph通常被简称为k-connected graph。

二部图

如果一个简单图的顶点集可以划分 Partition为两个集合 [math]\displaystyle{ W }[/math] 和 [math]\displaystyle{ X }[/math]，使得 [math]\displaystyle{ W }[/math] 中的任意两个顶点间无连边，[math]\displaystyle{ X }[/math] 中的任意两个顶点间无连边，则称其为二部图 Bipartite graph或着色数 chromatic number为2的图。

在完全二分图 Complete bipartite graph中，顶点集是两个不相交集 [math]\displaystyle{ W }[/math] 和 [math]\displaystyle{ X }[/math] 的并集，因此 [math]\displaystyle{ W }[/math] 中的每个顶点都与 [math]\displaystyle{ X }[/math] 中的每个顶点邻接，但 [math]\displaystyle{ W }[/math] 和 [math]\displaystyle{ X }[/math] 中没有边。

平面图

平面图 Planar graph是顶点和边可以画在一个平面上并且使得任意两边可以互不交叠的图。

路图

如果一个图的阶数大于等于2，其顶点可以以 [math]\displaystyle{ v_1,v_2,...,v_n }[/math] 的顺序列出，边为 [math]\displaystyle{ \{v_i,v_{i+1}\},i=1,2,...n-1 }[/math]，则称其为路图 Path graph或线性图 Linear graph。路图是连通图，其中除两个顶点的度为1外，其余顶点的度为2。如果路图作为另一个图的子图 Subgraph，则为该图的一条路径 Path。

圈图

如果一个图的阶数大于等于3，其顶点可以以 [math]\displaystyle{ v_1,v_2,...,v_n }[/math] 的顺序列出，边为 [math]\displaystyle{ \{v_i,v_{i+1}\},i=1,2,...n-1 }[/math]及[math]\displaystyle{ \{v_n,v_i\} }[/math]，则称其为圈图 Cycle graph或循环图 Circular graph。圈图是所有顶点的度均为2的连通图。如果圈图作为另一个图的子图，则为该图的一个圈 Cycle或回路 Circuit。

树

树 Tree是任意两个顶点恰由一条路径连接的无向图，即连通无圈无向图。

森林 Forest是任意两个顶点至多由一条路径连接的无向图，即无圈无向图，可等价为树的不交并 Disjoint union。

多重树

多重树 Polytree/Directed tree/Oriented tree/Singly connected network是底层无向图为树的有向无环图 Directed acyclic graph(DAG)。

多重森林 Polyforest/Directed forest/Oriented forest是底层无向图为森林的有向无环图。

更多

• 佩特森图 Petersen graph及其推广
• 完美图 Perfect graph
• 余图 Cograph
• 弦图 Chordal graph
• 点传递 Vertex-transitive、弧传递 Arc-transitive和距离传递图 Distance-transitive graph
• 强正则图 Strongly regular graph及距离正则图 Distance-regular graph

性质

如果图的两条边连接一个公共顶点，则称其邻接 Adjacent；有向图中，如果一条边的头是另一条边的尾，则称其连续 Consectuive。类似地，如果两个顶点共享一条公共边，则称其adjacent；如果第一个顶点是边尾，另一个顶点是边头，则称其consectuive ，此时公共边称为连接 Join两个顶点。边和边上的一个顶点称为关联 Incident。

只有一个顶点且没有边的图称为平凡图 Trivial graph。只有顶点没有边的图称为无边图 Edgeless graph。没有顶点和边的图有时被称为零图 Null graph或空图 Empty graph，但术语不一致，且并非所有的数学家都允许该对象。

通常情况下，图的顶点依据其作为集合元素的性质是可以区分的。 这种图可以称为顶点标号图 Vertex-labeled。 但是，对于许多问题，最好将顶点视为不可区分的。（当然，顶点仍然可以按照图本身的性质来区分，例如，按关联边的数目区分。）同样地，带有标记边的图称为边标号图 Edge-labeled。边或顶点附有标号的图一般称为标号图 Labeled。 因此，顶点、边无法区分的图称为无标号图 Unlabeled。（在文献中，labeled这个术语除了用于区分不同的顶点或边外还可能适用于其他类型的标记。）

例子

文件:Graphsix.png

具有六个顶点和七条边的图

• 右面是图的示意。该图中，顶点为 [math]\displaystyle{ V=\{1,2,3,4,5,6\} }[/math]，边为 [math]\displaystyle{ E=\{\{1,2\},\{1,5\}, * \{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\} }[/math]。
• 在计算机科学中，有向图是用来表示知识（如概念图 Conceptual graph）、有限状态机 Finite-state machine(FSM)，以及其他许多离散结构。
• 集合 [math]\displaystyle{ X }[/math] 中的二元关系 Binary relation [math]\displaystyle{ R }[/math] 定义了一个有向图。[math]\displaystyle{ X }[/math] 的元素 [math]\displaystyle{ x }[/math] 是元素 [math]\displaystyle{ y }[/math] 的直接前继 Predecessor当且仅当 [math]\displaystyle{ xRy }[/math]。
• 有向图可以为信息网络建模，如推特 Twitter。
• 有限生成群的凯莱图 Cayley graph和施赖埃尔陪集图 Schreier coset graph给出了有向图的特例。
• 在范畴论 Category theory中，每一个小范畴 Category都有一个基本的有向多重图，其顶点是范畴的对象，其边是范畴的弧。在范畴论的语言中，可以说从小范畴 Category of small categories到箭图的范畴有一个遗忘函子 Forgetful functor。

运算操作

有一些操作可以从最初的图中生成新图，这些图形可以分为以下几类：

一元操作：从一个初始图形中创建新图，如

• 边收缩 Edge contraction
• 线图 Line graph
• 对偶图 Dual graph
• 补图 Complement graph
• 图重写 Graph rewriting

二元操作：从两个初始图形中创建新图，如

• 图的不交并 Disjoint union of graphs
• 图的笛卡儿积 Cartesian product of graphs
• 图的张量积 Tensor product of graphs
• 图的强积 Strong product of graphs
• 图的字典积 Lexicographic product of graphs
• 系列平行图 Series-parallel graph

推广

在超图 Hypergraph中，一条边可以连接两个以上顶点。

一个无向图可以看作是由1- 单纯形 Simplex（边）和0- 单纯形（顶点）组成的单纯复形 Simplicial complex。由此可见，复形是图的推广，因为它们允许更高维的单纯形。

每个图都可以得到一个拟阵 Matroid。

在模型论 Model theory中，图仅仅是一个结构 Structure。 但是在这种情形下，边的数目是没有限制的：它可以是任意基数 Cardinal number，见Graphon。

在计算生物学 Computational biology中，幂图分析 Power graph analysis引入幂图 Power graph作为无向图的另一种表示方式。

在地理信息系统 Geographic information system(GIS)中，几何网络 Geometric network密切模仿图，并借用图论中的许多概念对道路网络或公用网络进行空间分析。

《图论导论》

Douglas B．West教授是伊利诺伊大学数学系的资深教授，长期从事图论理论和组合优化方面的研究工作，发表了100多篇论文。本书旨在介绍图论的基本概念、基本定理和算法，帮助读者理解并掌握图的结构和解决图论问题的技巧。另外，本书包含很多图论的新研究结果，并介绍了一些悬而未决的图论问题．证明与应用并举是本书的一个重要特点。

《图论及其应用》

该书籍主要介绍了图论的基本知识、相关定理等，并对于不同图，给出实际应用，如与对集有关的人员分派问题、与Hamilton图有关的旅行售货员问题等，通俗易懂。

课程推荐

漫谈图论的起源、发展与应用

网络科学研究中许多网络包含数千个甚至数百万个节点和链接。在研究小网络的基础上，还需要走的更远。对于具有很多节点和连边的网络，过于复杂，目测的方式对于理解和认识这类网络不再适用。需要适用网络科学的工具来刻画网络的拓扑，例如：度、度分布、邻接矩阵、加权网络、二分网络、路径、距离、连通性、集聚系数等。

该课程介绍了图论中的基本概念和网络科学使用的工具，可以帮助认识真实网络的关键性质。随后的章节将系统地研究这些网络性质，深入理解这些网络性质在认识复杂系统方面发挥的重要作用。

书籍领读：图论

本课程中，将讲解巴拉巴西网络科学书籍第一章图论。

本中文词条由Dorr用户参与编译，xx审校，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。