图及其组成部分

想象一些点。让我们给这些点起个名字——顶点。再想象一些线，每条线连接一个点到另一个点。我们把这些线称为边。我们在脑海中构建的这个结构就是我们想要理解的图的一个例子。

• 顶点 是 “vertices” 的单数形式。
• 边 是 “edges” 的单数形式。

当然，我们需要一个更精确的定义，以便明确知道什么构成图，什么不构成图。

一个图 $G$ 由一个非空集合 $V$ 和一个集合 $E$ 构成，其中 $V$ 的元素称为顶点，$E$ 的元素称为边，且每条边都与一个或两个顶点相关联，这些顶点被称为它的端点。

我们用记号 $G = (V, E)$ 来强调 $V$ 是图 $G$ 的顶点集，$E$ 是边集。

一个顶点也可以称为一个节点。只连接一个顶点的边称为环或自环。

简单图

某些图的应用允许同一对顶点之间存在多条边，而另一些则允许环。没有环，并且任意一对顶点之间最多只有一条边的图称为简单图。不是简单图的图称为非简单图。

约定：当省略“简单”或“非简单”这一修饰词时，通常默认该图是简单的。

顶点和边的表示法

• 我们用小写字母表示顶点，例如 $u$、$v$ 或 $w$。当顶点较多时，我们倾向于用下标编号的方式命名，如 $v_1, v_2, \ldots, v_n$。

• 同样地，我们可以用小写字母如 $e$ 或 $e_1, e_2, \ldots, e_m$ 表示边。

  但对于简单图，我们通常通过将边的两个端点名称组合起来表示一条边，顺序无关。例如，$(u,v)$ 表示以 $u$ 和 $v$ 为端点的边。显然，$(u,v)$ 与 $(v,u)$ 表示的是同一条边。

相邻、关联与度

在下面的例子中，可以看到顶点 $u$ 和 $v$ 是相邻的——因为有一条边直接连接它们。这样的顶点对被称为相邻。

相邻顶点 是指由一条边直接连接的顶点。

再补充一点使用上的说明：

如果一条边的一个端点是某个顶点，则称这条边与该顶点关联。

例如，边 $(u,v)$ 与顶点 $u$ 关联，也与顶点 $v$ 关联。

一个顶点的度是指与其关联的边的数量，但每个环要计算两次。

之所以将环计为两次，是因为我们希望顶点的度能准确反映从该顶点“伸出”的边的端点数量。

在下面的例子中，点击一个顶点即可查看其度：

图不是几何图形

我们之前看到的所有图像可能让人误以为边是直线段，且彼此之间有特定的角度。但实际上并非如此！回想一下定义，图的画法只是图结构的一种可视化表示。

事实上，对于一个给定的图的画法，我们可以随意移动顶点、调整边的位置，甚至改变边的弯曲程度，重新绘制出同一个图。

尝试拖动顶点，看看如何用不同方式绘制同一个图：