图论入门 | DataCamp

如何对对象之间的两两连接建模？

使用一种称为图的数学结构。这正是图论的精髓——对图的研究。

图论的基本元素是顶点（也称为节点）和边（也称为链接）。顶点表示图中的个体实体或点，边表示两个顶点之间的连接或关系。二者共同构成图的结构。根据所建模关系的具体性质，图可以是有向或无向、加权或非加权。

在计算机科学中，图论支撑着许多算法和数据结构，用于表示互联网、社交网络和通信系统等网络。它还提供了解决网络连通性、路径寻找和优化等问题的工具，并且是理解诸如树、环、平面图等各种数学结构和概念的基础。

在本文中，我们将教您入门图论所需了解的内容。

作者使用 Midjourney 创作

什么是图论？

图论是数学的一个分支，研究图的性质及其应用。图定义了一组称为顶点（或节点）的对象，由边（或链接）连接。

图论的主要目标是理解这些图的结构，并探索与连通性、路径寻找和网络优化相关的各种问题。

通过分析这些关系，图论使我们能够洞察各个领域中的众多现实问题。

图论从何而来？

图论的起源可以追溯到18世纪，源于瑞士数学家莱昂哈德·欧拉的工作。1736年，欧拉对柯尼斯堡七桥问题的解被认为是图论中的首批问题之一。该问题涉及在柯尼斯堡城中寻找一条步行路线，使其恰好一次穿过七座桥中的每一座。欧拉的方法为后来图的形式化研究奠定了基础。

在19和20世纪，图论在高斯等数学家的贡献下取得了显著发展，他们探索了多面体的性质，后来的研究者则形式化了概念并为与图相关的问题开发了算法。

20世纪中叶计算机科学的兴起进一步加速了图论的发展，使其广泛应用于计算机算法、网络分析和数据结构之中。

图论的基本概念

理解图论的基础是探索更高级主题的前提。为了帮助您起步，我们先打好一些基础…

作为有序对的图

形式上，图被定义为有序对G = (V, E)，其中：

V 是顶点（或节点）的集合，表示图中的各个实体。
E 是边（或链接）的集合，表示顶点对之间的连接。

顶点（V）与边（E）

顶点（V）：图中的基本单元或点。每个顶点表示所建模结构中的一个实体或位置。

边（E）：顶点对之间的连接或关系。每条边连接两个顶点，表示它们之间的关系或路径。

边的类型

有向边：在有向图（或称为有向图 digraph）中，边具有方向，即它们从一个顶点指向另一个特定的顶点。方向通常用箭头表示。有向边适用于建模不对称关系，例如交通流或调度中的先后约束。

无向边：在无向图中，边没有方向，仅连接两个顶点。这类图用于表示对称关系，例如互为好友或方向不重要的网络连接。

图论基础术语与概念

现在，我们来定义一些基本术语和概念：

顶点（节点）

该概念表示图结构中的个体实体或点。例如，在社交网络图中，每个人都可以用一个顶点表示。

顶点的度

顶点的度是指与其相连的边的数量。这能反映其在图中的连通性和重要性。最好的理解方式是想象社交网络中一个由顶点表示的人。如果从该顶点出发的边很多，我们会说它“度数高”，也意味着此人影响力强。如果我们在建模交通网络，度数高的节点就表示该节点是网络中的中心枢纽，能够直接连接最多的其他位置。

路径

图中的路径是一系列顶点，其中每一对相邻顶点都由一条边连接。路径可以是简单路径（不重复顶点）或一般路径（允许重复）。例如，在包含顶点 A、B、C 和 D 的图中，一条路径可以是 A → B → C → D，其中每个顶点都通过一条边连接到下一个顶点。

环

环是起点和终点为同一顶点、且不重复其他顶点或边的路径。环可以是简单的（除起终点外不重复边或顶点）或一般的。示例：在包含顶点 A、B、C 和 D 的图中，一个简单环可以是 A → B → C → D → A。

连通图

如果任意一对顶点之间都存在一条路径，则该图是连通的。换言之，在连通图中，每个顶点都可以通过某些边的序列到达其他任意顶点。一个很好的例子是社交网络图，其中任何人都可以从其他任何人处到达。

图的类型

图论包含多种类型的图，每种都适用于不同的应用与分析。在本节中，我们将探讨这些类型，讨论其基本结构，并提供其应用示例。这将帮助您理解在何种情况下使用哪种图来解决特定问题并准确建模现实场景。

简单图

简单图的可视化来源： Wikipedia

简单图是一种不包含多重边（任意一对顶点之间不超过一条边）或自环（连接顶点自身的边）的图。简单图中的每条边连接两个不同的顶点。

示例：

基本的社交网络，其中每段友谊由两人之间的一条链接表示。
由单一直接道路连接城市的地图，没有多条路线或自连接。

多重图

多重图的可视化，红色为多重边，蓝色为若干自环来源： Wikipedia

多重图允许同一对顶点之间存在多条边（平行边），也可以包含自环。这类图可以表示实体之间存在多次交互或多重连接的情形。

示例：

交通网络中，多家航空公司在同一对城市之间运营航班。
通信网络中，同一对通信节点之间有多条通道相连。

加权图

加权图的可视化来源： Hyperskill

在加权图中，每条边都带有关联的权重或成本，用于表示定量度量，如距离、时间或容量。加权图用于建模边具有不同强度或成本的问题。

应用：

在由道路连接的城市地图中，权重可以表示城市之间的距离或旅行时间。
在网络优化问题中，权重可能表示带宽或通信链路的成本。

有向图（Digraphs）

有向图的可视化来源： Wikipedia

有向图（digraph）的边具有特定方向，即每条边都从一个顶点指向另一个不同的顶点。方向通常用箭头表示，指示流向或单向关系。

用例：

工作流图，任务需要按特定顺序完成。
网页链接结构，超链接从一个页面指向另一个页面，表示单向连接。

无向图

无向图的可视化来源： Baeldung

在无向图中，边没有方向。一条边仅连接两个顶点，关系是相互的或双向的。边中顶点的顺序无关紧要。

示例：

好友网络，友谊是相互的，连接是双向的。
无向道路地图，道路在两个方向上连接城市，不指定方向。

树图论

树是一种连通且无环的图，意味着它不包含任何环。具有 $$n$$ 个顶点的树恰有 $$n−1$$ 条边。树中任意一对顶点之间都由恰好一条路径相连，从而保证任意两点之间的路径唯一。

下面快速概括一下树图的性质：

连通性。任意一对顶点之间都有路径。
无环性。不存在环，从而保证没有闭合回路。
路径唯一。任意两点之间恰有一条路径，这意味着图是最小连通的。
边的数量。具有 $$n$$ 个顶点的树有 $$n−1$$ 条边。
子树：树的任意子集（包括单个顶点）本身也是一棵树，称为子树。
叶节点。度为 1 的顶点称为叶或叶节点，是树的端点。

树图与其他图有何不同？

与一般图不同，树不包含环。这意味着任何包含环的图都不能被归类为树。

具有 $$n$$ 个顶点的树恰有 $$n−1$$ 条边，而一般图的边数可变，且可能包含多重边和自环。另一个区别是树总是连通的，而一般图可能是不连通的，由多个连通分量组成，每个分量都可能是一棵树。

此外，在树中，任意两点之间恰好一条路径，而在其他图中，尤其是包含环或多重边的图中，两个顶点之间可能存在多条路径。

应用

树在计算与数据组织的理论与实践中都至关重要。它们为许多结构性和算法性问题提供了极其高效的解决方案。例如：

数据结构

二叉树：用于以层次方式组织数据。例如二叉搜索树，可加速数据检索和排序。
堆：一种用于优先队列的二叉树，能够高效管理和检索最大或最小元素。
B-树：用于数据库和文件系统，实现高效的数据检索与存储，支持插入、删除和查询等操作。

网络设计

路由：树用于网络路由协议（如生成树）中，以确定跨网络进行数据传输的最高效路径。
广播：在网络设计中，树结构有助于高效数据广播，确保以最小冗余将数据传播到所有节点。

层次表示

文件系统：文件系统常用树结构表示目录与子目录，反映文件的层次化组织。
组织架构图：树用于建模组织层级，展示汇报关系及不同岗位之间的联系。

解析与语法分析

抽象语法树（AST）：用于编译器和解释器中表示源代码的语法结构。AST 有助于语法检查和代码优化。

图论的应用

图论在各个领域都有广泛应用。它在解决复杂问题和优化系统方面发挥关键作用。以下应用中可见其身影：

计算机科学：网络、算法与数据结构

图论是设计与分析网络系统、开发算法以及组织计算机科学中数据结构的基础。例如，网络领域高度依赖图论来建模和管理设备间的连接。具体而言，网络拓扑被表示为图，以优化数据传输与路由。

诸如Dijkstra 和 Kruskal 的算法分别用于解决最短路径和最小生成树问题。此外，图论还是邻接表和邻接矩阵等数据结构的理论基础，这些结构对于高效的数据操作与检索必不可少。

生物学：生物网络建模

图论在生物学中同样发挥着重要作用。它用于建模和分析复杂的生物网络，例如：

蛋白质—蛋白质相互作用网络
代谢通路
基因调控网络

这些网络被表示为图，其中顶点表示生物实体（如蛋白质、基因），边表示它们之间的相互作用或关系。

这种方法有助于研究者理解生物系统中的复杂关系，预测功能结果，并识别潜在的药物开发靶点。

社会科学：社会网络分析

在社会科学中，图论用于分析社会网络，个体被表示为顶点，他们的互动或关系被表示为边。

这种分析有助于理解社会结构、影响模式和群体动力。运用中心性和连通性等概念，研究者可以识别关键影响者、研究信息传播并分析社会行为。

交通运输：交通流与城市规划

大多数人并不了解，道路、路口和交通线路都是以图的形式建模的，旨在：

优化交通流
降低拥堵
改进路线规划。

基于图的算法有助于设计高效的交通网络、管理公共交通系统以及规划城市基础设施。对这些网络的分析有助于规划者做出明智决策，提升城市内部的通达性与连通性。

构建与分析简单图的分步演练

您已经掌握了基础，并理解了图论的应用。

现在，您已准备好创建并分析自己的简单图。为简单起见，我们将这份分步演练分为两部分：

构建
分析

最合乎逻辑的起点是构建——我们开始吧…

构建一个简单图

步骤 1：定义问题。

假设我们想要对一个小型社交网络中的好友关系进行建模。

我们可以使用为网络分析而生的 Python 库NetworkX来建模。

我们先创建一个图：

# Import libraries 
import networkx as nx # Network analysis
import matplotlib.pyplot as plt # Data visualization
import pydot # Python interface to Graphviz
from networkx.drawing.nx_pydot import graphviz_layout
# Create a graph
graph = nx.Graph() 
技术支持

步骤 2：确定顶点。

在我们的虚构社交网络中，有四位个体：Alice、Bob、Carol 和 Dave。这些个体将在图中表示为顶点——请记住，这表示所建模结构中的一个实体或位置。

以下是在 Python 中创建顶点的方法：

# Add the nodes 
# graph.add_node("Alice") --> Add one node per time
graph.add_nodes_from([
    "Alice","Bob", "Carol", "Dave"
]) # Add multiple nodes技术支持

步骤 3：确定边。

假设好友关系如下：

Alice 与 Bob 和 Carol 是朋友。
Bob 与 Alice 和 Dave 是朋友。
Carol 与 Alice 是朋友。
Dave 与 Bob 是朋友。

这意味着这些关系构成了边：

Alice-Bob
Alice-Carol
Bob-Dave

以下是在 Python 中定义这些边的方法：

# Add the edges
# graph.add_edge("Alice", "Bob") --> Add one edge per time
graph.add_edges_from([("Alice", "Bob"), 
                      ("Alice", "Carol"),
                      ("Bob", "Dave"),
                      ("Bob", "Alice")  # Ensuring all described edges are included
                     ]) # Add multiple edges技术支持

步骤 4：绘制图。

一旦定义了顶点和边，我们就可以绘制图来可视化这些关系。下面的代码片段将创建一个带有顶点与边标签的网络图：

# Visualize the plot
pos = graphviz_layout(graph, prog="dot")
nx.draw(graph, 
        pos, 
        with_labels=True, 
        node_size=1000, 
        node_color=["pink", "yellow", "tan", "orange"])
plt.show()技术支持

输出： 这将生成一个图，显示 Alice、Bob、Carol 和 Dave 之间的连接，如上所述。

上述代码将输出如下图：

用于建模社交网络的简单图［作者创作］

如果您想建模自己的社交网络，请复制这份DataLab 笔记本并按需修改。

分析这个简单图

步骤 1：检查连通性。

由于我们可以通过某些边的序列从任一顶点遍历到其他任一顶点，所以该图是连通的。

为更好地理解，下面是每对顶点之间的路径：

Alice 到 Bob：直接边。
Alice 到 Carol：直接边。
Alice 到 Dave：经由 Bob。
Bob 到 Carol：经由 Alice。
Bob 到 Dave：直接边。
Carol 到 Dave：经由 Alice 和 Bob。

步骤 2：确定每个顶点的度数。

回顾一下，我们将顶点的度定义为“与其相连的边的数量”。将此应用到我们的示例，我们会得到：

Alice = 度数 2（连接到 Bob 和 Carol）
Bob = 度数 2（连接到 Alice 和 Dave）
Carol = 度数 1（连接到 Alice）
Dave = 度数 1（连接到 Bob）

每个度数都是根据所给的好友关系，统计与每个顶点相关联的边的数量而得出。

步骤 3：识别路径与环。

Alice 与 Dave 之间的一条路径可以是 Alice → Bob → Dave。

该图没有环，因为不存在无需回溯就回到起点的路径。

步骤 4：寻找中心性。

Alice 和 Bob 在该网络中更居中，因为他们各自连接到三位其他顶点。Carol 和 Dave 的中心性较低，各自只连接到一个其他顶点。

结语

图论为审视和解决各领域中存在的复杂关系与结构提供了坚实框架。通过理解顶点、边以及不同类型图等核心概念，并探索其实际应用，您可以获得有关系统优化和解决现实问题的宝贵见解。

在继续探索图论时，请记住，其原理并非仅停留在理论层面——对于应对现实世界的挑战、提升连通性和提高系统效率至关重要。扎实的图论理解将增强您的问题解决能力，并为您周围的互联系统提供更深刻的视角。

要进一步提升对图论的理解，请查阅以下更进阶的资源，它们在本文所述基础上进行拓展：

图论常见问题

图论为何重要？

图论为分析和优化复杂网络提供了基础框架，有助于解决与连通性、路径寻找和系统效率相关的实际问题。

图论有哪些应用？

应用包括：网络路径优化、社交网络分析、生物系统建模、交通规划改进等。

如何入门图论？

先熟悉顶点和边等基础概念，再探索基本图类型及其性质。从简单示例入手，为更复杂的主题与应用打下坚实基础。

图论的目的是什么？

图论的目的在于研究由边连接的顶点所代表的对象之间的关系，从而能够在各个领域分析与优化复杂网络与结构。

作者

Kurtis Pykes

主题

数据可视化