您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识

图论(图论基础知识)

节点,顶点,数据图论(图论基础知识)

发布时间：2016-12-08加入收藏来源：互联网点击：2

很多朋友想了解关于图论的一些资料信息，下面是小编整理的与图论相关的内容分享给大家，一起来看看吧。

作者：Srivatsa

翻译：和中华

校对：丁楠雅

本文约6300字，建议阅读20+分钟。

本文从图的概念以及历史讲起，并介绍了一些必备的术语，随后引入了networkx库，并以一个航班信息数据集为例，带领读者完成了一些基本分析。

简介

俗话说一图胜千言。但是“图”（Graph）说的远不止于此。以图形式呈现的数据可视化能帮助我们获得见解，并基于它们做出更好的数据驱动型决策。

但要真正理解图是什么以及为什么使用它们，我们需要理解一个称为图论（Graph Theory）的概念。理解它可以使我们成为更好的程序员。

如果你曾经尝试理解这个概念，应该会遇到大量的公式和干涩的理论。这便是为什么我们要写这篇博文的原因。我们先解释概念，然后提供实例，以便你可以跟随并弄明白它的执行方式。这是一篇详细的文章，因为我们认为提供概念的正确解释要比简洁的定义更受欢迎。

在本文中，我们将了解图是什么，它们的应用以及一些历史背景。我们还将介绍一些图论概念，然后使用进行案例研究以巩固理解。

准备好了吗？我们开始吧。

目录

图及其应用图论的历史、为何使用图论必备术语图论概念熟悉Python中的图数据分析案例

图及其应用

让我们看一个简单的图（Graph）来理解这个概念。如下图所示：

假设此图代表某个城市的热门景点位置，以及游客所遵循的路径。我们把V视为景点位置，将E视为从一个地方到另一个地方的路径。

V = {v1, v2, v3, v4, v5}

E = {(v1,v2), (v2,v5), (v5, v5), (v4,v5), (v4,v4)}

边（u，v）与边（v，u）相同 - 它们是无序对。

具体而言，图（Graph）是用于研究对象和实体之间成对关系的数学结构。它是离散数学的一个分支，在计算机科学，化学，语言学，运筹学，社会学等领域有多种应用。

数据科学和分析领域也使用图来模拟各种结构和问题。作为一名数据科学家，你应该能以有效的方式解决问题，如果数据是以特定方式排列的，则图可以提供一种解决问题的机制。

形式上看，

图是一对集合。G = (V, E)，V是顶点集合，E是边集合。 E由V中的元素对组成（无序对）有向图（DiGraph）也是一对集合。D = (V, A)，V是顶点集合，A是弧集合。A由V中的元素对组成（有序对）

在有向图的情况下，（u，v）和（v，u）之间存在区别。通常在这种情况下，边被称为弧，以指示方向的概念。

R和Python中都有使用图论概念分析数据的包。在本文中，我们将简要介绍一些概念并使用Networkx Python包分析一个数据集。

from IPython.display import Image

Image('images/network.PNG')

Image('images/usecase.PNG')

从上面的例子可以清楚地看出，图在数据分析中的应用是广泛的。我们来看几个用例场景：

营销分析

图可用于找出社交网络中最有影响力的人。广告商和营销人员可以通过社交网络中最有影响力的人员传达他们的信息，从而估算最大的营销价格。

银行交易

图可用于查找有助于减少欺诈交易的异常模式。有一些例子可以通过分析银行网络的资金流动来侦测恐怖主义活动。

供应链

图有助于确定送货卡车的最佳路线以及识别仓库和交付中心的位置。

制药公司

制药公司可以使用图论优化销售人员的路线。这有助于降低成本并缩短销售人员的行程时间。

电信行业

电信公司通常使用图（Voronoi图）来了解基站的数量和位置，以确保最大的覆盖范围。

图的历史以及为何使用图

图的历史

如果想更多地了解关于图的想法是如何形成的，请继续阅读！

该理论的起源可以追溯到柯尼斯堡七桥问题（大约1730年代）。它提问是否可以在以下限制条件下遍历柯尼斯堡市的七座桥梁

每座桥只经过一次（即不重复）从哪出发，最终回到哪

小故事：欧拉于1736年研究并解决了此问题，他把问题归结为如“一笔画”问题。他的《柯尼斯堡七桥》的论文圆满解决了这一问题，同时开创了数学一个新分支---图论。

这等价于询问4个节点和7个边的多图（multigraph）是否具有欧拉环（欧拉环是在同一个顶点上开始和结束的欧拉路径。而欧拉路径是指在图中仅仅遍历每个边一次的路径。更多术语后文中给出）。这个问题引出了欧拉图的概念。柯尼斯堡七桥问题的答案是否定的，它最早由欧拉解答。

译者注：在图论中，多图（相对于简单图）是指图中允许出现多边（也叫平行边），即两个顶点可以有多条边连接，如下图中的红色就是多边，所以该图属于多图。

1840年，A.F Mobius提出了完全图（complete graph）和二分图（bipartite graph）的概念，Kuratowski通过趣味谜题证明它们是平面的。树的概念（没有环的连通图）由Gustav Kirchhoff于1845年提出，他在计算电网或电路中的电流时使用了图论思想。

1852年，Thomas Gutherie发现了著名的四色问题。然后在1856年，Thomas P. Kirkman和William R.Hamilton研究了多面体的循环，并通过研究仅访问某些地点一次的旅行，发明了称为哈密顿图的概念。1913年，H.Dudeney提到了一个难题。尽管发明了四色问题，但Kenneth Appel和Wolfgang Haken在一个世纪后才解决了这个问题。这一次被认为是图论真正的诞生。

Caley研究了微分学的特定分析形式来研究树。这在理论化学中有许多含义。这也导致了枚举图论（enumerative graph theory）的发明。不管怎么说，“图”这个术语是由Sylvester在1878年引入的，他在“量子不变量”与代数和分子图的协变量之间进行了类比。

1941年，Ramsey致力于着色问题，这产生了另一个图论的分支 - 极值图论（Extremal graph theory）。1969年，Heinrich使用计算机解决了四色问题。对渐近图连通的研究产生了随机图论。图论和拓扑学的历史也密切相关，它们有许多共同的概念和定理。

Image('images/Konigsberg.PNG', width = 800)

为何使用图？

以下几点可以激励你在日常数据科学问题中使用图：

图提供了一种处理关系和交互等抽象概念的更好的方法。它还提供了直观的视觉方式来思考这些概念。图很自然地成了分析社会关系的基础。图数据库已成为一种常用的计算工具，并且是SQL和NoSQL数据库的替代方案。图用于以DAG（定向非循环图）的形式建模分析工作流。一些神经网络框架还使用DAG来模拟不同层中的各种操作。图理论用于研究和模拟社交网络，欺诈模式，功耗模式，社交媒体的病毒和影响力。社交网络分析（SNA）可能是图理论在数据科学中最著名的应用。它用于聚类算法 - 特别是K-Means。系统动力学也使用一些图理论 - 特别是循环。路径优化是优化问题的一个子集，它也使用图的概念。从计算机科学的角度来看，图提供了计算效率。某些算法的Big O复杂度对于以图形式排列的数据更好（与表格数据相比）。

必备术语

在进一步阅读本文之前，建议你熟悉这些术语。

顶点u和v称为边（u，v）的末端顶点。如果两条边具有相同的末端顶点，则它们是平行的。形式为（v，v）的边是循环。如果图没有平行边和循环，则图被称为简单图。如果图没有边，则称其为Empty，即E是空的。如果图没有顶点，则称其为Null，即V和E是空的。只有1个顶点的图是一个Trivial graph。具有共同顶点的边是相邻的。具有共同边的顶点是相邻的。顶点v的度，写作d（v），是指以v作为末端顶点的边数。按照惯例，我们把一个循环计作两次，并且平行边缘分别贡献一个度。孤立顶点是度数为1的顶点。d（1）顶点是孤立的。如果图的边集合包含了所有顶点之间的所有可能边，则图是完备的。图G =（V，E）中的步行（Walk）是指由图中顶点和边组成的一个形如ViEiViEi的有限交替序列。如果初始顶点和最终顶点不同，则Walk是开放的（Open）。如果初始顶点和最终顶点相同，则Walk是关闭的（Closed）。如果任何边缘最多遍历一次，则步行是一条Trail。如果任何顶点最多遍历一次，则Trail是一条路径Path（除了一个封闭的步行）。封闭路径（Closed Path）是一条回路Circuit，类似于电路。

 1/4    1 2 3 4 下一页 尾页