图论 - 基础知识

---

图形是由点和连接到这些点的线组成的图。它至少有一条线连接一组两个顶点，没有顶点连接自身。图论中图的概念建立在一些基本术语上，例如点、线、顶点、边、顶点度、图的属性等。在本章中，我们将介绍图论的这些基础知识。

观点

点是一维、二维或三维空间中的特定位置。为了更好地理解，可以用字母表来表示点。可以用点来表示。

例子

这里，点是一个名为“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，因为有 2 条边在顶点“a”处相交。

• deg(b) = 3，因为有 3 条边在顶点“b”处相交。

• deg(c) = 1，因为在顶点“c”处形成 1 条边

• 所以'c'是一个下垂的顶点。

• deg(d) = 2，因为有 2 条边在顶点“d”处相交。

• deg(e) = 0，因为在顶点“e”处形成了 0 条边。

• 所以 '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。

其他顶点的入度和出度如下表所示 -

实施例2

看看下面的有向图。顶点“a”具有从顶点“a”向外延伸的边“ae”。因此，它的出度是 1。类似地，该图有一条边“ba”朝向顶点“a”。因此'a'的入度是1。

其他顶点的入度和出度如下表所示 -

下垂顶点

通过使用顶点的度数，我们有两种特殊类型的顶点。度数为 1 的顶点称为下垂顶点。

例子

这里，在此示例中，顶点“a”和顶点“b”具有连接的边“ab”。因此，对于顶点“a”，仅存在一条朝向顶点“b”的边，并且类似地，对于顶点“b”，仅存在朝向顶点“a”的一条边。最后，顶点'a'和顶点'b'具有相同的度数，也称为下垂顶点。

孤立的顶点

度数为零的顶点称为孤立顶点。

例子

这里，顶点“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

在上图中，对于顶点{d,a,b,c,e}，度数序列为{3,2,2,2,1}。

实施例2

在上图中，对于顶点{a,b,c,d,e,f}，度数序列为{2,2,2,2,2,0}。