GraphQL 学习指南 (14):图论 2.2

阅读数:2 2019 年 12 月 15 日 19:25

GraphQL学习指南(14):图论 2.2

(图论的历史)

内容简介
为什么 GraphQL 是 Ajax 诞生以来具创新性的数据获取技术?GraphQL 通过为 API 提供查询语言和用以完成查询的运行状态,提供了对 REST 和特定页面服务架构的替代方案。借助这《GraphQL 学习指南》,Alex Banks 和 Eve Porcello 为希望开始使用 GraphQL 的前端 Web 开发人员、后端工程师以及项目或产品经理提供了一条清晰的学习路径。你将先后探索图论、图数据结构和 GraphQL 类型,之后在实际项目中学习如何为照片共享应用构建 schema。
《GraphQL 学习指南》还将向你介绍 Apollo Client,可用来将 GraphQL 连接到你的用户界面。

对图论的研究可追溯到 1735 年的普鲁士柯尼斯堡(现俄罗斯加里宁格勒州首府)。该镇位于普雷格尔河(Pregel River)上,是一个航运枢纽,有两个大岛通过七座桥连接了四块主要陆地,如图 2-10 所示。

柯尼斯堡(Konigsberg)是一座美丽的小镇,镇上的人们喜欢在桥上散步欢度周末。一直以来,镇上的居民纠结于怎样才能在不经过同一座桥的情况下,依次跨越七座桥。他们走遍小镇试图走过每个岛屿,想尽一切办法不重复经过任一座桥梁,可每次都失败了。万般无奈之下,他们拜访了莱昂哈德·欧拉(Leonhard Euler)。大名鼎鼎的欧拉是一位多产的瑞士数学家,他一生出版和发表了 500 多部书籍和论文。

天才很忙,欧拉并不关心那些看起来微不足道的问题。但在多想了一会儿之后,他发现这个问题并不简单,随即也和镇上的居民一样对它产生了兴趣并想要真正搞清楚。欧拉没有写下所有可能的路径,而是决定查看陆地之间的 7 座桥梁,如图 2-11 所示。

GraphQL学习指南(14):图论 2.2

图 2-10:柯尼斯堡七桥问题

GraphQL学习指南(14):图论 2.2

图 2-11:将桥梁和陆地分别编号

接下来他将其简化,把桥梁和陆地绘制成后来被称为图的图形,如图 2-12 所示。

根据图 2-12,A 和 B 是由一条边相连接的相邻节点。通过这些边,我们可以计算出每个节点的度数(degree)。节点的度数等于连接该节点的边的数量。如果我们查看七桥问题中的节点,就会发现每个节点的度数都是奇数。

GraphQL学习指南(14):图论 2.2

图 2-12:柯尼斯堡七桥问题图

A 有 5 条边连接相邻节点(奇数),B、C、D 各有 3 条边连接相邻节点(奇数)。

因为每个节点的度数都是奇数,欧拉发现不重复经过每座桥是不可能的。一言以蔽之:如果你通过一座桥去一个岛,那么就必须通过另一座桥离开。你说你不想重复经过同一座桥,抱歉,不存在的。

如今,我们把每条边只能访问一次的图称为欧拉路径(Eulerian path)。通过证明,无向图拥有两个奇数度的节点,或者所有节点都是偶数度。我们来看看两个奇数度节点的情况(见图 2-13)。

GraphQL学习指南(14):图论 2.2

图 2-13:欧拉路径

另一个与欧拉相关的概念是环路或欧拉循环(Eulerian cycle)。这种情况是,起始点和结束点相同。每条边只经过一次,但起始点又是结束点(见图 2-14)。

GraphQL学习指南(14):图论 2.2

图 2-14:欧拉循环

柯尼斯堡七桥问题成为图论的第一个定理。欧拉不仅被尊为图论的鼻祖,而且创造了常数 e 和虚数单位 i,甚至变量 x 之于函数 f 的数学函数语法 f(x) 也可以追溯到他。1

1 更多相关内容参见 http://www.storyofmathematics.com/18th_euler.html

柯尼斯堡七桥问题是因同一座桥不可以通过超过一次这条规则而产生,但却并未规定必须在何处开始或结束。这就意味着若你试图解决这个问题,那就跳不出无向图这个框。倘若化繁为简,只从特定点开始又会怎样呢?

如果你生活在 B 岛上,那么你每次走过各个桥就都得从 B 岛开始。这种情况就是一个有向图,通常称为(tree)。

GraphQL学习指南(14):图论 2.2

购书地址 https://item.jd.com/12639300.html?dist=jd

评论

发布