1.12 课后习题

习题1 哥尼斯堡七桥问题

图1-19中哪个图可以一笔画成（要求每条线只能画一次）？并给出理由。

习题2 矩阵运算

令A表示一个无向无权无自环网络的邻接矩阵，1是一个有N个元素且每个元素都为1的列向量。换句话说，1=(1,1,…,1)T，这里的T表示矩阵转置。使用矩阵运算（数乘、行向量乘列向量、矩阵转置、矩阵的迹等，不能使用求和符号）写出如下表达式：

（1）元素是各个节点的度ki(i=1,2,…,N)的向量k。

（2）网络中链接总数L。

（3）网络中三角形个数T。三角形是指两两相连的三个节点（提示：可以使用矩阵的迹）。

（4）向量knn：第i个元素为节点i的邻居节点的度之和。

（5）向量knnn：第i个元素为节点i的二阶邻居（邻居的邻居）的度之和。

习题3 网络表示

在许多分析运算中，邻接矩阵是一种非常有用的网络表示方式。不过，在计算机中存储网络时，使用邻接表的方式可以节省存储空间。邻接表是一个大小为L×2的矩阵，每行对应一个链接，记录该链接的起始节点和终止节点。对于图1-20中的两个网络：

（1）写出其邻接矩阵；

（2）写出其邻接表；

（3）计算图1-20a所示网络的平均集聚系数；

（4）交换图1-20a中标记为5和6的节点，看看其邻接矩阵和邻接表的变化；

（5）关于网络的信息，有哪些是可以从其邻接矩阵表示中得到而无法从其邻接表表示中得到的？

（6）在网络（a）中，从节点1出发到节点3，有多少条长度为3的路径（节点和链接可以重复）？网络（b）呢？

（7）编写程序计算两个网络中长度为3的环的个数。

习题4 度、集聚系数和连通分支

（1）假如一个无向网络含有N个节点，所有节点的度都为1。那么，节点个数N需要满足什么条件？该网络的度分布如何？网络包含多少个连通分支？

（2）假如一个无向网络含有N个节点，所有节点的度都为2，集聚系数都为1。那么，该网络的拓扑结构是什么样的？节点个数N需要满足什么条件？

习题5 二分网络

对于图1-21所示的二分网络，

（1）写出其邻接矩阵，并说明其邻接矩阵为什么是分块矩阵。

（2）将该二分网络分别映射到紫色节点和绿色节点上，并分别写出两个映射网络的邻接矩阵；

（3）分别计算紫色节点和绿色节点的平均度；

（4）对于（3）中得到的两个映射网络，分别计算其节点的平均度。

习题6 一般意义的二分网络

假设二分网络的两个节点集合的大小分别是N1和N2。

（1）写出该二分网络的最大可能链接数Lmax；

（2）和大小为N1+N2的非二分网络相比，有多少个链接不能出现在该二分网络中？

（3）假如N1N2，对于该二分网络的链接密度——实际链接数和最大链接数Lmax的比值，有哪些发现？

（4）分别写出两个节点集合的平均度和，并说明二者之间的联系。