图论 - 基础知识
图是由点和连接这些点的线组成的图表。它至少有一条线连接一组两个顶点，并且没有顶点连接自身。图论中的图的概念建立在一些基本术语之上，例如点、线、顶点、边、顶点的度数、图的性质等。在本章中，我们将介绍这些图论的基础知识。
点
点是一维、二维或三维空间中的特定位置。为了更好地理解，可以用字母表示一个点。它可以用一个点来表示。
示例
这里，点是一个名为“a”的点。
线
线是连接两点的连接。它可以用实线表示。
示例
这里，“a”和“b”是点。这两点之间的连接称为线。
顶点
顶点是多条线相交的点。它也称为节点。与点类似，顶点也用字母表示。
示例
这里，顶点用字母“a”命名。
边
边是连接两个顶点的线的数学术语。从单个顶点可以形成许多边。没有顶点，就不能形成边。边必须有一个起始顶点和一个结束顶点。
示例
这里，“a”和“b”是两个顶点，它们之间的连接称为边。
图
图“G”定义为 G = (V, E)，其中 V 是图中所有顶点的集合，E 是图中所有边的集合。
示例 1
在上例中，ab、ac、cd 和 bd 是图的边。类似地，a、b、c 和 d 是图的顶点。
示例 2
在这个图中，有四个顶点 a、b、c 和 d，以及四条边 ab、ac、ad 和 cd。
环
在图中，如果从顶点到自身画一条边，则称为环。
示例 1
在上图中，V 是一个顶点，它有一条边 (V, V) 形成一个环。
示例 2
在这个图中，顶点 a 和顶点 b 各形成两个环。
顶点的度数
它是与顶点 V 相邻的顶点数。
符号 − deg(V)。
在一个具有 n 个顶点的简单图中，任何顶点的度数为 −
deg(v) ≤ n – 1 ∀ v ∈ G
一个顶点可以与所有其他顶点形成边，但不能与自身形成边。因此，顶点的度数最多为图中顶点数减 1。这个 1 是指自身顶点，因为它不能自己形成环。如果任何顶点都有环，则它不是简单图。
顶点的度数可以考虑图的两种情况 −
无向图
有向图
无向图中顶点的度数
无向图没有有向边。考虑以下示例。
示例 1
看一下下面的图 −
在上图中，
deg(a) = 2，因为顶点“a”上有 2 条边相交。
deg(b) = 3，因为顶点“b”上有 3 条边相交。
deg(c) = 1，因为顶点“c”上形成 1 条边
所以“c”是悬挂顶点。
deg(d) = 2，因为顶点“d”上有 2 条边相交。
deg(e) = 0，因为顶点“e”上没有形成边。
所以“e”是孤立顶点。
示例 2
看一下下面的图 −
在上图中，
deg(a) = 2，deg(b) = 2，deg(c) = 2，deg(d) = 2，deg(e) = 0。
顶点“e”是孤立顶点。该图没有任何悬挂顶点。
有向图中顶点的度数
在有向图中，每个顶点都有一个入度和一个出度。
图的入度
顶点 V 的入度是进入顶点 V 的边的数量。
符号 − deg−(V)。
图的出度
顶点 V 的出度是从顶点 V 出发的边的数量。
符号 − deg+(V)。
考虑以下示例。
示例 1
看一下下面的有向图。顶点“a”有两条边，“ad”和“ab”，它们向外延伸。因此，它的出度为 2。类似地，有一条边“ga”指向顶点“a”。因此，“a”的入度为 1。
其他顶点的入度和出度如下表所示 −
| 顶点 | 入度 | 出度 |
|---|---|---|
| a | 1 | 2 |
| b | 2 | 0 |
| c | 2 | 1 |
| d | 1 | 1 |
| e | 1 | 1 |
| f | 1 | 1 |
| g | 0 | 2 |
示例 2
看一下下面的有向图。顶点“a”有一条边“ae”从顶点“a”向外延伸。因此，它的出度为 1。类似地，该图有一条边“ba”指向顶点“a”。因此，“a”的入度为 1。
其他顶点的入度和出度如下表所示 −
| 顶点 | 入度 | 出度 |
|---|---|---|
| a | 1 | 1 |
| b | 0 | 2 |
| c | 2 | 0 |
| d | 1 | 1 |
| e | 1 | 1 |
悬挂顶点
利用顶点的度数，我们有两个特殊的顶点类型。度数为一的顶点称为悬挂顶点。
示例
在这个例子中，顶点“a”和顶点“b”有一条连接边“ab”。因此，关于顶点“a”，只有一条边指向顶点“b”，类似地，关于顶点“b”，只有一条边指向顶点“a”。最后，顶点“a”和顶点“b”的度数为 1，也称为悬挂顶点。
孤立顶点
度数为零的顶点称为孤立顶点。
示例
这里，顶点“a”和顶点“b”彼此之间以及与任何其他顶点之间都没有连接。因此，顶点“a”和“b”的度数都为零。这些也称为孤立顶点。
邻接
以下是邻接的规范 −
在一个图中，如果两个顶点之间有一条边，则称这两个顶点邻接。这里，顶点的邻接由连接这两个顶点的单边来维持。
在一个图中，如果两条边之间有一个公共顶点，则称这两条边邻接。这里，边的邻接由连接两条边的单个顶点来维持。
示例 1
在上图中 −
“a”和“b”是邻接顶点，因为它们之间有一条公共边“ab”。
“a”和“d”是邻接顶点，因为它们之间有一条公共边“ad”。
“ab”和“be”是邻接边，因为它们之间有一个公共顶点“b”。
“be”和“de”是邻接边，因为它们之间有一个公共顶点“e”。
示例 2
在上图中 −
“a”和“d”是邻接顶点，因为它们之间有一条公共边“ad”。
“c”和“b”是邻接顶点，因为它们之间有一条公共边“cb”。
“ad”和“cd”是邻接边，因为它们之间有一个公共顶点“d”。
“ac”和“cd”是邻接边，因为它们之间有一个公共顶点“c”。
平行边
在一个图中，如果一对顶点由多于一条边连接，则这些边称为平行边。
在上图中，“a”和“b”是两个顶点，它们之间由两条边“ab”和“ab”连接。因此，它被称为平行边。
多重图
具有平行边的图称为多重图。
示例 1
在上图中，有五条边“ab”、“ac”、“cd”、“cd”和“bd”。由于“c”和“d”之间有两条平行边，所以它是一个多重图。
示例 2
在上图中，顶点“b”和“c”有两条边。顶点“e”和“d”之间也有两条边。因此，它是一个多重图。
图的度数序列
如果图中所有顶点的度数按降序或升序排列，则得到的序列称为图的度数序列。
示例 1
| 顶点 | A | b | c | d | e |
|---|---|---|---|---|---|
| 连接到 | b,c | a,d | a,d | c,b,e | d |
| 度数 | 2 | 2 | 2 | 3 | 1 |
在上图中，对于顶点 {d, a, b, c, e}，度数序列为 {3, 2, 2, 2, 1}。
示例 2
| 顶点 | A | b | c | d | e | f |
|---|---|---|---|---|---|---|
| 连接到 | b,e | a,c | b,d | c,e | a,d | - |
| 度数 | 2 | 2 | 2 | 2 | 2 | 0 |
在上图中，对于顶点 {a, b, c, d, e, f}，度数序列为 {2, 2, 2, 2, 2, 0}。