一、顶点（vertex）

上图中黑色的带数字的点就是顶点，表示某个事物或对象。由于图的术语没有标准化，因此，称顶点为点、节点、结点、端点等都是可以的。叫什么无所谓，理解是什么才是关键。

二、边（edge）

上图中顶点之间蓝色的线条就是边，表示事物与事物之间的关系。需要注意的是边表示的是顶点之间的逻辑关系，粗细长短都无所谓的。包括上面的顶点也一样，表示逻辑事物或对象，画的时候大小形状都无所谓。

三、同构（Isomorphism ）

先看看下面2张图：

首先你的感觉是这2个图肯定不一样。但从图（graph）的角度出发，这2个图是一样的，即它们是同构的。前面提到顶点和边指的是事物和事物的逻辑关系，不管顶点的位置在哪，边的粗细长短如何，只要不改变顶点代表的事物本身，不改变顶点之间的逻辑关系，那么就代表这些图拥有相同的信息，是同一个图。同构的图区别仅在于画法不同。

四、有向/无向图（Directed Graph/ Undirected Graph）

最基本的图通常被定义为“无向图”，与之对应的则被称为“有向图”。两者唯一的区别在于，有向图中的边是有方向性的。下图即是一个有向图，边的方向分别是：(1->2), (1-> 3), (3-> 1), (1->5), (2->3), (3->4), (3->5), (4->5), (1->6), (4->6)。要注意，图中的边(1->3)和(3->1)是不同的。有向图和无向图的许多原理和算法是相通的。

五、权重（weight）

边的权重（或者称为权值、开销、长度等），也是一个非常核心的概念，即每条边都有与之对应的值。例如当顶点代表某些物理地点时，两个顶点间边的权重可以设置为路网中的开车距离。下图中顶点为4个城市:Beijing, Shanghai, Wuhan, Guangzhou，边的权重设置为2城市之间的开车距离。有时候为了应对特殊情况，边的权重可以是零或者负数，也别忘了“图”是用来记录关联的东西，并不是真正的地图。

六、路径/最短路径（path/shortest path）

在图上任取两顶点，分别作为起点（start vertex）和终点（end vertex），我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重复经过同一个点和同一条边的路线，就是一条“路径”。两点之间存在路径，则称这2个顶点是连通的（connected）。
还是上图的例子，北京->上海->广州，是一条路径，北京->武汉->广州，是另一条路径，北京—>武汉->上海->广州，也是一条路径。而北京->武汉->广州这条路径最短，称为最短路径。
路径也有权重。路径经过的每一条边，沿路加权重，权重总和就是路径的权重（通常只加边的权重，而不考虑顶点的权重）。在路网中，路径的权重，可以想象成路径的总长度。在有向图中，路径还必须跟随边的方向。
值得注意的是，一条路径包含了顶点和边，因此路径本身也构成了图结构，只不过是一种特殊的图结构。

七、环...

课后习题

【2019年真题】用有向无环图描述表达式(x+y)*((x+y)/x)，需要的顶点个数至少是
A. 5       B. 6        C. 8       D. 9

参考答案：A

【2017年真题】已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是（）
A.10        B.11        C.13        D.15

参考答案：B

【2010年真题】若无向图 G=（V, E）中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是（）。 
A．6         B．15         C．16         D．21 

参考答案：C
答案解析：考查图的连通性。 
要保证无向图 G 在任何情况下都是连通的，即任意变动图 G 中的边，G 始终保持连通，首先需要 G的任意六个结点构成完全连通子图 G1，需 15 条边，然后再添一条边将第 7 个结点与 G1 连接起来，共需 16 条边。 

【2009年真题】下列关于无向连通图特性的叙述中，正确的是（）。 
I. 所有顶点的度之和为偶数 
II. 边数大于顶点个数减 1 
III. 至少有一个顶点的度为 1 
A． 只有Ⅰ 
B．只有Ⅱ 
C．Ⅰ和Ⅱ 
D．Ⅰ和Ⅲ

参考答案：A
答案解析：考查无向连通图的特性。 
每条边都连接了两个结点，则在计算顶点的度之时，这条边都被计算了两次，故所有顶点的度之和为边数的两倍，显然必为偶数。而 ii 和 iii 则不一定正确，如：对顶点数 N≥1 无向完全图不存在一个顶点的度为 1，并且边数与顶点数的差要大于 1。