图论基础

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

点

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

示例

这里，这个点名为“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处形成了两个环。

Mahesh Parahar

更新于：2019年8月23日

491 次浏览

开启你的职业生涯

完成课程获得认证

开始学习