图论导论

图论是对图的研究，图是用于模拟对象之间成对关系的数学结构。

你知道吗，地球几乎所有的问题都可以转化为道路和城市的问题，并解决了吗？图论是多年前发明的，甚至在计算机发明之前。莱昂哈德欧拉写了一篇关于柯尼斯堡七桥的论文，这篇论文被认为是图论的第一篇论文。从那以后，人们逐渐认识到，如果我们能够将任何问题转化为这个城市 - 道路问题，我们可以通过图论轻松地解决它。

图论有许多应用。最常见的应用之一是找到一个城市与另一个城市之间的最短距离。我们都知道，要访问你的 PC，此网页必须从服务器传送许多路由器。Graph Theory 帮助它找出需要交叉的路由器。在战争期间，需要轰炸哪条街道以便将首都与其他城市断开，这也可以通过图论来找到。

让我们首先学习图论的一些基本定义。

图形：

比方说，我们有 6 个城市。我们将它们标记为 1,2,3,4,5,6。现在我们将彼此之间有道路的城市连接起来。

这是一个简单的图表，其中一些城市显示连接它们的道路。在图论中，我们将这些城市称为 Node 或 Vertex ，道路称为 **Edge。**图只是这些节点和边的连接。

一个节点可以代表很多东西。在一些图表中，节点代表城市，一些代表机场，一些代表棋盘中的正方形。 Edge 表示每个节点之间的关系。这种关系可以是从一个机场到另一个机场的时间，骑士从一个广场到所有其他广场的移动等。

棋枰的骑士路径

简单来说， Node 表示任何对象， Edge 表示两个对象之间的关系。

相邻节点：

如果节点 A 与节点 B 共享边缘，则认为 B 与 A 相邻。换句话说，如果两个节点直接连接，则将它们称为相邻节点。一个节点可以具有多个相邻节点。

有向图和无向图：

在有向图中，边缘在一侧具有方向标记，这意味着边缘是单向的。另一方面，无向图的边缘在两侧都有方向标记，这意味着它们是双向的。通常，无向图表示边缘两侧没有任何符号。

我们假设有一个聚会正在进行。聚会中的人是由节点代表的，如果他们握手，两个人之间就有一条优势。然后这个图表是无向的，因为任何人 A 与人 B 握手，当且仅当 B 也与 A 握手时。相反，如果从人 A 到另一个人 B 的边缘对应于 A 的欣赏 B ，那么该图是指向的，因为赞美不一定是往复的。前一种类型的图形称为无向图形，边缘称为无向边缘，而后一种类型的图形称为有向图和边被称为有向边。

加权和未加权图：

加权图是将数字（权重）分配给每个边的图。这些权重可能代表例如成本，长度或容量，这取决于手头的问题。

未加权的图表恰恰相反。我们假设，所有边缘的权重都相同（大概是 1）。

路径：

路径表示从一个节点到另一个节点的方式。它由边缘序列组成。两个节点之间可以有多条路径。

在上面的示例中，从 A 到 D 有两条路径。 A-> B，B-> C，C-> D 是一条路径。该路径的成本是 3 + 4 + 2 = 9 。此外，还有另一种路径 A-> d 。这条路的成本是 10 。成本最低的路径称为最短路径。

学位：

顶点的度数是连接到它的边的数量。如果有任何边缘连接到两端的顶点（一个循环），则计算两次。

在有向图中，节点有两种类型的度：

• In-degree：指向节点的边数。
• Out-degree：从节点指向其他节点的边数。

对于无向图，它们简称为度。

一些与图论相关的算法

• Bellman-Ford 算法
• Dijkstra 算法
• Ford-Fulkerson 算法
• Kruskal 的算法
• 最近邻算法
• Prim 的算法
• 深度优先搜索
• 广度优先搜索