图（离散数学）

在离散数学，更具体地说，在图理论中，图是一个结构，构成一组对象，其中某些对像在某种意义上是“相关”的对象。对应于称为顶点的数学抽象（也称为节点或点），并且每个相关的顶点对都称为边缘（也称为链接或行）。通常，图形以图形形式描绘为一组点或圆的顶点，并以边缘或曲线连接。图是离散数学研究对象之一。

边缘可能是指向或无方向性的。例如，如果顶点代表一个聚会上的人，并且两个人握手之间会有优势，那么该图是无方向性的，因为任何人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个简化（顶点）组成的简单复合物。因此，复合物是图形的概括，因为它们允许更高维度的简单。

每个图都会产生矩形。

在模型理论中，图只是一个结构。但是在那种情况下，边缘数量没有限制：它可以是任何基数，请参见连续图。

在计算生物学中，功率图分析将功率图引入了无向图的替代表示。

在地理信息系统中，几何网络是在图表后密切建模的，并从图理论借用许多概念来对道路网络或实用程序网格进行空间分析。