图的类型

根据顶点的数量，边的数量，互连性及其整体结构，可以使用各种图形。在本章中，我们将仅讨论某些重要的图形类型。

空图

没有边的图称为空图。

示例

在上图中，有三个名为“ 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 ^{n c ₂} = 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

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

正则图

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

示例

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

在两个图中，所有顶点的度均为2。它们称为2正则图。

完整图

具有'n'个相互顶点的简单图称为完整图，并用'K _n '表示。在图中，一个顶点应具有所有其他顶点的边，然后称为完整图。

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

示例

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

在图一中

在图二中

循环图

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

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

表示法-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中，它是通过在中间加一个名为“ d”的顶点从C ₃获得的。记为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

循环图

的图与至少一个周期被称为一个循环图。

示例

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

非循环图

的曲线图，没有周期被称为一个非循环图。

示例

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

二部图

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

通常，Bipertite图具有两组顶点，比如说V ₁和V ₂，如果绘制了一条边，它应该将V ₁中的任何顶点连接到V _2中的任何顶点。

示例

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

完全二部图

如果将V ₁中的每个顶点都连接到V _2的每个顶点，则将划分为V = {V ₁，V ₂ }的二部图'G'（G，(V,E)）称为完整的二部图。

通常，完整的二部图将集合V ₁中的每个顶点连接到集合V _2中的每个顶点。

示例

下图是一个完整的二部图，因为它的边将集合V ₁中的每个顶点连接到集合V _2中的每个顶点。

如果| 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 =⌊  Ñ ² /4⌋=⌊  10 ² /4⌋= 25

同样，K6，4 = 24

K7，3 = 21

K8，2 = 16

K9，1 = 9

如果n = 9，K5，4 =⌊  Ñ ² /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。