网络分析|GIS网络分析( 二 )

图的历史
如果想更多地了解关于图的想法是如何形成的，请继续阅读！
该理论的起源可以追溯到柯尼斯堡七桥问题（大约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年， Ramse百思特网y致力于着色问题，这产生了另一个图论的分支 - 极值图论（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 。
具有共同顶点的边是相邻的。具有共同边的顶点是相邻的。