0%

Basics for Graphs

写在前面

这篇博客仅包含了图论中比较基础的部分,如果需要较为全面的学习图论,建议购买一本《离散数学》的参考书进行学习。

柯尼斯堡七桥问题(Seven Bridges of Königsberg)

当时东普鲁士柯尼斯堡(今日俄罗斯加里宁格勒)市区跨普列戈利亚河两岸,河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下,如何才能把这个地方所有的桥都走遍?

在完成对七桥问题的抽象化后,能够知道

其实七桥问题就是一个一笔画问题,能不能一次走完,等于能不能在第三个图里面完成一笔画

首先,对点进行分类,分为起点终点,以及其他点

对于其他点来说,与它们相连的边的个数不能为奇数个

举个例子,我每次回老家,我都会坐飞机从大连出发,到达武汉,再坐火车回荆州

那么武汉就是中间点,我来武汉之后一定会走,不然我一定会停留在武汉

同样的道理,除了起点终点之外的其他点,如果相连的边是奇数个,那这个图一定不能一笔画

近而,得出结论

如果一个图能够一笔画,那么它里面与奇数条边相连的点的个数一定不超过2

但是,如果这句话反说,就不对了

如果一个图里面与奇数条边相连的点个数不超过2,那这个图一定能够一笔画

因为图有可能是断开的

再把上面的话改一下

如果一个连通图里面与奇数条边相连的点个数不超过2,那这个图一定能够一笔画

图的定义

可以说,一个图里面重要的有2点,有哪几个点,有哪几条边,至于点在什么位置,边的长度是多少,这些都不重要

在图中,边可以被分为无向边和有向边,有向边是单方向的,而无向边是双向的

简单图

首先来说,简单图有三个要求

  1. 没有有向边
  2. 没有形成环
  3. 两点之间仅能有一条边

那么,如果一个图是简单图,那么它的边可以被表示为以两端点为元素的集合

如图

一个有n个点的简单图,能够形成多少种不同的边?

首先,由于简单图里面是无向边,而且简单图没有环,所以这是一个排序问题,相当于从有n个球的箱子里取出两个

一个有n个点的简单图,一共有多少种不同的图?

一个图由边和点构成,点有n个已经确定,所以能组成多少种图,与边有多少种有很大的关系,根据上一问,可以得到不同边的集合的子集有

有向图

有向图只有一个要求

所有的边都是有向边

环和多重边,有向图都允许

一个有n个点的有向图,能够形成多少种不同的边?

有向图跟简单图相比,无非是多了一个方向问题,那这题不就简单了吗?

但是,我们常常会忽视的一点是,有向图能够有环,所以,一个点自己形成一条边的可能是有的,所以正解应该是

一个有n个点的简单图,一共有多少种不同的图?

这个就很简单了,跟之前的问题类似

度的定义

顶点度计算的是在放大镜下看时似乎伸出的边数

比如有这样一个图,图中标为2的点的度数是多少?

想象一下,如果拿一个放大镜去看2,会得到一张什么样的图像

这个点的度数是7

从这个问题,可以知道,一个点上环的度数不算1,而算2

入度和出度

如果是一张有向图呢,度该如何计算?

入度(in-degree):指向点的边的个数

出度(out-degree):从点指出的边的个数

下图中,所有的点的入度之和出度之和分别是多少?

很简单,只需要把每个点的入度和出度算出来,然后再分别加到一起

可以得到

入度:7

出度:7

一个图中,入度和出度一定是相等的

很简单,一个有向边,一定代表一个点指向一个点,代表一个点入度加一点同时会有一个点的出度加一,环很特殊,严格来说,环既可以算有向边又可以算无向边,但是无论是有向边还是无向边,都不会影响这个结论成立

度的作用

一个概念的引出,一定有其作用,度的作用就是可以用度来求边的个数

一个图的总边数,等于一个图的点的度数只和

但是,在有向图中,总度数被入度和出度平分了,所以,有可以推导出

有向图的总边数等于所有点的入度之和或者是出度之和

度数在实际问题中的应用

朋友问题:

选取五个人,有没有可能,这五个人只认识其中的另外三个人?

如果学习了度的知识的话,这个问题就迎刃而解

想象一个5个人作为顶点的简单图,边是表示朋友关系的无向边。每个人拥有的朋友数量就是这个人的度数。

根据题设条件,每个人仅仅有三个朋友,所以每个点的度数就是3,这个图的总度数就是15,很显然,度只能是偶数(必须能整除),图才可能存在,所以,这个问题是不可能成立的

结语

对于图论来说,这篇博客只能说是垫脚石,简单介绍了一下单个的图,并没有涉及图与图之间的关系,11月份学校考试较多,关于图与图之间的关系,等我有空一定完成,感兴趣的话,可以收藏我的博客网站哦🌝

-------------本文结束感谢您的阅读-------------