图论 - 图的类型

根据顶点数量、边数量、互连性及其整体结构，图有多种类型。本章中我们将仅讨论某些重要的图表类型。

空图

没有边的图称为空图。

例子

在上图中，有三个名为“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 _{ⁿ c ₂} = 2 ^n(n-1)/2。

例子

在下图中，有 3 个顶点和 3 条边，这是最大的，不包括平行边和环。这可以用上面的公式来证明。

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

ⁿ C ₂ = n(n–1)/2

= 3(3–1)/2

= 6/2

= 3 条边

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

2 _{ⁿ C ₂} = 2 ^n(n-1)/2

= 2 ^3(3-1)/2

= 2 ³

这 8 个图表如下所示 -

连通图

如果每对顶点之间都存在路径，则称图 G 是连通的。图中的每个顶点都应该至少有一条边。这样我们就可以说它连接到边另一侧的某个其他顶点。

例子

在下图中，每个顶点都有自己的边连接到其他边。因此它是一个连通图。

断开的图

如果图 G 不包含至少两个连接的顶点，则该图 G 是断开连接的。

实施例1

下图是断开图的示例，其中有两个组件，一个具有“a”、“b”、“c”、“d”顶点，另一个具有“e”、“f”、“g”， 'h' 顶点。

这两个组件是独立的并且彼此不连接。因此它被称为断开图。

实施例2

在此示例中，有两个独立的组件 abfe 和 cd，它们彼此不相连。因此这是一个断开连接的图。

正则图

如果图 G 的所有顶点都具有相同的度数，则称图 G 是正则图。在图中，如果每个顶点的度为“k”，则该图称为“k-正则图”。

例子

在下图中，所有顶点都具有相同的度数。所以这些图称为正则图。

在这两个图中，所有顶点的度数都是 2。它们被称为 2-正则图。

完整图

具有“n”个相互顶点的简单图称为完全图，用“K _n ”表示。图中，一个顶点与其他所有顶点都应该有边，则称为完全图。

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

例子

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

在图一中，

	A	乙	C
A	未连接	连接的	连接的
乙	连接的	未连接	连接的
C	连接的	连接的	未连接

在图二中，

	p	q	r	s
p	未连接	连接的	连接的	连接的
q	连接的	未连接	连接的	连接的
r	连接的	连接的	未连接	连接的
s	连接的	连接的	连接的	未连接

循环图

具有“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}通过添加新的顶点得到轮图。该新顶点称为Hub ，它连接到 C _n的所有顶点。

符号 - W _n

W 中的边数_n = 从中心到所有其他顶点的边数 +

循环图中没有中心的所有其他节点的边数。

= (n–1) + (n–1)

= 2(n–1)

例子

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

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

W4 中的边数 = 2(n-1) = 2(3) = 6

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

W5 中的边数 = 2(n-1) = 2(4) = 8

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

W4 中的边数 = 2(n-1) = 2(6) = 12

循环图

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

例子

在上面的示例图中，我们有两个循环 abcda 和 cfgec。因此它被称为循环图。

非循环图

没有环的图称为无环图。

例子

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

二分图

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

一般来说，Bipertite 图有两组顶点，比如说 V1 和 V2，如果绘制一条边，它应该将集合 V 1 中的任何顶点连接到集合_V 2 中的任何_顶点。

例子

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

完全二分图

_{如果 V 1}中的每个顶点都连接到 V 2 中的每个顶点，则具有分区 V = {V 1 , V 2 } 的_二_部图_' G'，G = (V, E)被称为完全二部图。

一般来说，完整的二部图将集合 V _{1中的每个顶点连接到集合 V}₂中的每个顶点。

例子

_{下图是完全二分图，因为它具有将集合 V 1}中的每个顶点连接到集合 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 ² /4]

如果n=10，k5,5=[n2/4]=[10 ² /4]=25。

同理，K6,4=24

K7、3=21

K8，2=16

K9，1=9

如果 n=9, k5, 4 = [n2/4] = [92/4] = 20

同理，K6,3=18

K7、2=14

K8，1=8

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

星图

K1, n-1 形式的完全二部图是具有 n 个顶点的星图。如果单个顶点属于一个集合并且所有剩余顶点属于另一个集合，则星图是完全二部图。

例子

在上图中，在“n”个顶点中，所有“n–1”个顶点都连接到单个顶点。因此它的形式为K ¹ , ^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 = ⁹ C ₂

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