图论 - 图的类型
根据顶点数、边数、互连性及其整体结构，图有多种类型。本章中，我们将仅讨论几种重要的图类型。
空图
没有边的图称为空图。
示例
在上图中，有三个顶点，分别名为"a"、"b"和"c"，但它们之间没有边。因此它是一个空图。
简单图
只有一个顶点的图称为简单图。
示例
在上面显示的图中，只有一个顶点"a"，没有其他边。因此，它是一个简单图。
无向图
无向图包含边，但这些边不是有向边。
示例
在此图中，"a"、"b"、"c"、"d"、"e"、"f"、"g"是顶点，"ab"、"bc"、"cd"、"da"、"ag"、"gf"、"ef"是图的边。由于它是一个无向图，所以边"ab"和"ba"相同。类似地，其他边也以同样的方式考虑。
有向图
在有向图中，每条边都有一个方向。
示例
在上图中，我们有七个顶点"a"、"b"、"c"、"d"、"e"、"f"和"g"，以及八条边"ab"、"cb"、"dc"、"ad"、"ec"、"fe"、"gf"和"ga"。由于它是一个有向图，因此每条边都有一个箭头标记来显示其方向。请注意，在有向图中，"ab"与"ba"不同。
简单图
没有循环且没有平行边的图称为简单图。
具有'n'个顶点的单个图中可能的最大边数为nC2，其中nC2 = n(n – 1)/2。
具有'n'个顶点的简单图的数量 = 2nc2 = 2n(n-1)/2。
示例
在下图中，有 3 个顶点和 3 条边，这是除平行边和环路之外的最大值。这可以通过使用上述公式来证明。
n=3 个顶点的最大边数 −
n=3 个顶点的简单图的最大数量 −
这 8 个图如下所示 −
连通图
如果图 G 中每对顶点之间都有一条路径，则称该图为连通图。图中的每个顶点至少应有一条边。这样我们就可以说它与边另一侧的其他顶点相连。
示例
在下图中，每个顶点都有自己的边与其他边相连。因此，它是一个连通图。
不连通图
如果图 G 不包含至少两个连通顶点，则该图为不连通图。
示例 1
下图是一个不连通图的示例，其中有两个组件，一个具有"a"、"b"、"c"、"d"顶点，另一个具有"e"、"f"、"g"、"h"顶点。
这两个组件是独立的，彼此不连通。因此它被称为不连通图。
示例 2
在此示例中，有两个独立分量 a-b-f-e 和 c-d，它们彼此不相连。因此，这是一个不连通图。
正则图
如果图 G 的所有顶点都具有相同的度数，则称其为正则图。在图中，如果每个顶点的度数为"k"，则该图称为"k-正则图"。
示例
在以下图中，所有顶点都具有相同的度数。因此，这些图称为正则图。
在这两个图中，所有顶点的度数均为 2。它们被称为 2-正则图。
完全图
具有'n'个共同顶点的简单图称为完全图，用'K
换句话说，如果一个顶点与图中的所有其他顶点相连，那么它被称为一个完全图。
示例
在以下图中，图中的每个顶点都与图中除自身之外的所有剩余顶点相连。
在图 I 中，
| a | b | c | |
|---|---|---|---|
| a | Not Connected | Connected | Connected |
| b | Connected | Not Connected | Connected |
| c | Connected | Connected | Not Connected |
In graph II,
| p | q | r | s | |
|---|---|---|---|---|
| p | Not Connected | Connected | Connected | Connected |
| q | Connected | Not Connected | Connected | Connected |
| r | Connected | Connected | Not Connected | Connected |
| s | Connected | Connected | Connected | Not Connected |
循环图
如果一个简单图有'n'个顶点（n >= 3）和'n'条边，且所有边都形成一个长度为'n'的循环，则该简单图称为循环图。
如果图中每个顶点的度数为 2，则该图称为循环图。
符号 − Cn
示例
查看以下图表 −
图 I 有 3 个顶点和 3 条边，形成一个循环"ab-bc-ca"。
图 II 有 4 个顶点和 4 条边，形成一个循环"pq-qs-sr-rp"。
图 III 有 5 个顶点和 5 条边，形成一个循环"ik-km-ml-lj-ji"。
因此，所有给定的图表都是循环图。
轮图
通过添加新顶点，可以从循环图 Cn-1 中获得轮状图。该新顶点称为 Hub，它连接到 Cn 的所有顶点。
符号 − Wn
Wn 中的边数 = 从中心到所有其他顶点的边数 +
没有中心的循环图中所有其他节点的边数。
= (n–1) + (n–1)
= 2(n–1)
示例
查看以下图表。它们都是轮图。
在图I中，它是从C3通过在中间添加一个顶点'd'而得到的。它被表示为W4。
W4中的边数 = 2(n-1) = 2(3) = 6
在图II中，它是从C4通过在中间添加一个顶点't'而得到的。它被表示为W5。
W5中的边数 = 2(n-1) = 2(4) = 8
在图III中，它是从C6通过在中间添加一个顶点'o'而得到的。它被表示为 W7。
W4 中的边数 = 2(n-1) = 2(6) = 12
循环图
具有至少一个循环的图称为循环图。
示例
在上面的示例图中，我们有两个循环 a-b-c-d-a 和 c-f-g-e-c。因此它被称为循环图。
非循环图
没有循环的图称为非循环图。
示例
在上面的示例图中，我们没有任何循环。因此它是一个非循环图。
二分图
如果一个简单图 G = (V, E) 的顶点划分为 V = {V1, V2}，则该图称为二分图 如果 E 的每条边都将 V1 中的顶点连接到 V2 中的顶点。
一般来说，二分图有两组顶点，比如 V1 和 V2，如果绘制一条边，它应该将集合 V1 中的任何顶点连接到集合 V2 中的任何顶点。
示例
在此图中，您可以观察到两组顶点 - V1 和 V2。这里，两个名为"ae"和"bd"的边连接两个集合 V1 和 V2 的顶点。
完全二分图
如果二分图"G"，G = (V, E) 且分区 V = {V1, V2}，则称其为完全二分图，如果 V1 中的每个顶点都连接到 V2 的每个顶点。
通常，完全二分图将集合 V1 中的每个顶点连接到集合 V2 中的每个顶点。
示例
下图是完全二分图，因为它有连接集合 V1 中每个顶点和集合 V2 中每个顶点的边。
如果 |V1| = m 且 |V2| = n，则完全二分图用 K
- K
- 如果 m=n，则 K
一般而言，完全二分图不是完全图。
如果 m=n=1，则 K
具有 n 个顶点的二分图中的最大边数为 −
[n2/4]
If n=10, k5, 5= [n2/4] = [102/4] = 25.
Similarly, K6, 4=24
K7, 3=21
K8, 2=16
K9, 1=9
If n=9, k5, 4 = [n2/4] = [92/4] = 20
Similarly, K6, 3=18
K7, 2=14
K8, 1=8
如果"G"没有奇数长度的循环，则"G"是二分图。二分图的一个特殊情况是星形图。
星形图
形式为 K1, n-1 的完全二分图是具有 n 个顶点的星形图。如果单个顶点属于一个集合，而所有剩余顶点属于另一个集合，则星形图是完全二分图。
示例
在上面的图中，在"n"个顶点中，所有"n-1"个顶点都连接到单个顶点。因此，它的形式为 K1, n-1，它们是星形图。
图的补集
假设 'G−' 是一个简单的图，它有一些顶点，与 'G' 的顶点相同，并且如果边 {U, V} 不存在于 G 中，则该边存在于 'G−' 中。这意味着，如果两个顶点在 G 中不相邻，则这两个顶点在 'G−' 中相邻。
如果图 I 中存在的边不存在于另一个图 II 中，并且图 I 和图 II 组合在一起形成一个完全图，则图 I 和图 II 称为彼此的补图。
示例
在以下示例中，图 I 有两个边"cd"和"bd"。其补图图 II 有四个边。
请注意，图 I 中的边不存在于图 II 中，反之亦然。因此，两个图的组合给出了一个具有"n"个顶点的完整图。
注意 − 两个互补图的组合给出了一个完整图。
如果"G"是任何简单图，则
|E(G)| + |E('G-')| = |E(Kn)|，其中 n = 图中顶点的数量。
示例
假设"G"是一个具有九个顶点和十二条边的简单图，求出"G-"中的边数。
您有，|E(G)| + |E('G-')| = |E(Kn)|
12 + |E('G-')| =
9(9-1) / 2 = 9C2
12 + |E('G-')| = 36
|E('G-')| = 24
"G" 是一个有 40 条边的简单图，其补图"G−"有 38 条边。求图 G 或"G−"中的顶点数。
设图中的顶点数为"n"。
我们有，|E(G)| + |E('G-')| = |E(Kn)|
40 + 38 = n(n-1)/2
156 = n(n-1)
13(12) = n(n-1)
n = 13
