图论 - 图的类型

---

---

根据顶点数、边数、互连性和整体结构，图有多种类型。本章将仅讨论其中几种重要的图类型。

空图

没有边的图称为空图。

例子

在上图中，有三个顶点，分别命名为“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”个顶点的单个图中可能存在的最大边数为ⁿC₂，其中ⁿC₂ = n(n – 1)/2。

• 具有“n”个顶点的可能简单图的数量 = 2^nc₂ = 2^n(n-1)/2。

例子

在下图中，有3个顶点和3条边，这是排除平行边和环后的最大值。这可以通过使用上述公式来证明。

具有n=3个顶点的最大边数 -

nC2 = n(n–1)/2
   = 3(3–1)/2
   = 6/2
   = 3 edges

具有n=3个顶点的最大简单图数 -

2nC2 = 2n(n-1)/2
   = 23(3-1)/2
   = 23
   = 8

这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_n”表示。在图中，一个顶点应该与所有其他顶点都有边，然后它被称为完全图。

换句话说，如果一个顶点连接到图中的所有其他顶点，则它被称为完全图。

例子

在下图中，图中的每个顶点都与图中除自身之外的所有其他顶点连接。

在图I中，

在图II中，

环图

如果一个简单图具有“n”个顶点（n >= 3）和“n”条边，并且所有边都形成长度为“n”的环，则称为环图。

如果图中每个顶点的度数为二，则称为环图。

符号 - C_n

例子

看看下面的图 -

• 图I有3个顶点和3条边，形成一个环“ab-bc-ca”。

• 图II有4个顶点和4条边，形成一个环“pq-qs-sr-rp”。

• 图III有5个顶点和5条边，形成一个环“ik-km-ml-lj-ji”。

因此，所有给定的图都是环图。

轮图

轮图是从环图C_n-1通过添加一个新顶点获得的。该新顶点称为中心，连接到C_n的所有顶点。

符号 - W_n

No. of edges in Wn = No. of edges from hub to all other vertices +
                     No. of edges from all other nodes in cycle graph without a hub.
                     = (n–1) + (n–1)
                     = 2(n–1)

例子

看看下面的图。它们都是轮图。

在图I中，它是从C₃通过在中间添加一个名为“d”的顶点获得的。它表示为W₄。

Number of edges in W4 = 2(n-1) = 2(3) = 6

在图II中，它是从C₄通过在中间添加一个名为“t”的顶点获得的。它表示为W₅。

Number of edges in W5 = 2(n-1) = 2(4) = 8

在图III中，它是从C₆通过在中间添加一个名为“o”的顶点获得的。它表示为W₇。

Number of edges in W4 = 2(n-1) = 2(6) = 12

有环图

至少有一个环的图称为有环图。

例子

在上图示例中，我们有两个环a-b-c-d-a和c-f-g-e-c。因此它被称为有环图。

无环图

没有环的图称为无环图。

例子

在上图示例中，我们没有任何环。因此它是一个无环图。

二分图

具有顶点划分V = {V₁, V₂}的简单图G = (V, E)称为二分图，如果E的每条边都连接V₁中的一个顶点到V₂中的一个顶点。

一般来说，二分图有两组顶点，假设为V₁和V₂，如果画一条边，它应该连接集合V₁中的任何顶点到集合V₂中的任何顶点。

例子

在这个图中，您可以观察到两组顶点 - V₁和V₂。这里，两条名为“ae”和“bd”的边连接了两组V₁和V₂的顶点。

完全二分图

如果V₁中的每个顶点都连接到V₂的每个顶点，则称具有划分V = {V₁, V₂}的二分图“G”，G = (V, E)为完全二分图。

一般来说，完全二分图连接集合V₁中的每个顶点到集合V₂中的每个顶点。

例子

下图是一个完全二分图，因为它有连接集合V₁中的每个顶点到集合V₂中的每个顶点的边。

如果|V₁| = m且|V₂| = n，则完全二分图用K_{m, n}表示。

• K_m,n有(m+n)个顶点和(mn)条边。

• 如果m=n，则K_m,n是正则图。

一般来说，完全二分图不是完全图。

如果m=n=1，则K_m,n是完全图。

具有n个顶点的二分图中的最大边数为

如果n=10，k5, 5= ⌊ n² / 4 ⌋ = ⌊ 10² / 4 ⌋ = 25

类似地K6, 4=24

K7, 3=21

K8, 2=16

K9, 1=9

如果n=9，k5, 4 = ⌊ n² / 4 ⌋ = ⌊ 9² / 4 ⌋ = 20

类似地K6, 3=18

K7, 2=14

K8, 1=8

如果“G”没有奇数长度的环，则“G”是二分图。二分图的一个特例是星形图。

星形图

形式为K_{1, n-1}的完全二分图是具有n个顶点的星形图。如果一个顶点属于一个集合，而所有其余顶点属于另一个集合，则星形图是完全二分图。

例子

在上图中，“n”个顶点中的所有“n–1”个顶点都连接到一个顶点。因此它采用K_{1, n-1}的形式，它们是星形图。

图的补图

令'G−'为一个简单图，其一些顶点与“G”相同，并且如果边不存在于G中，则边{U, V}存在于'G−'中。这意味着，如果两个顶点在G中不相邻，则它们在'G−'中相邻。

如果存在于图I中的边不存在于另一个图II中，并且如果图I和图II组合在一起形成一个完全图，则图I和图II称为彼此的补图。

例子

在以下示例中，图-I有两条边“cd”和“bd”。其补图-II有四条边。

请注意，图-I中的边不存在于图-II中，反之亦然。因此，这两个图的组合给出了“n”个顶点的完全图。

注意 - 两个补图的组合给出一个完全图。

如果“G”是任何简单图，则

|E(G)| + |E('G-')| = |E(K_n)|，其中n = 图中顶点数。

例子

设“G”是一个具有九个顶点和十二条边的简单图，求'G-'中的边数。

已知， |E(G)| + |E('G-')| = |E(K_n)|

12 + |E('G-')| =

9(9-1) / 2 = ⁹C₂

12 + |E('G-')| = 36

|E('G-')| = 24

“G”是一个具有40条边的简单图，其补图'G−'有38条边。求图G或'G−'中的顶点数。

设图中的顶点数为“n”。

已知， |E(G)| + |E('G-')| = |E(K_n)|

40 + 38 = n(n-1) / 2

156 = n(n-1)

13(12) = n(n-1)

n = 13