（网工复习 考完删）第二章 网络与图

1.七桥问题

找到一个路径包含每一条边且边不重复

证明该图不存在符合条件的路径：

1. 每一个度数为奇数的节点只能是路径的起点或终点
2. 图中有四个度数为奇数的节点
3. 一条路径只能有一个起点和终点

2.图的联通性

• 联通：每一对顶点之间都存在路径
• 不联通：包含多个联通片
• 联通片：联通的孤立子图
• 最大联通片
• 强联通：一个有向图每一对顶点之间都存在路径
• 弱联通：将一个有向图的所有有向边替换为无向边所得基图是联通图，则有向图弱联通

3.邻接矩阵

用一个一维数组存放图中所有顶点数据，一个二维数组存放顶点间关系

4.文献共引与耦合网络

4.1引文网络

一个节点表示一篇文章，当节点\(i\)引用了节点\(j\)，就有一条从节点

\(i\)指向节点\(j\)的有向边

4.2共引

两篇文章的共引指同时引用这两篇文章的其他文章的数量，可构造无向的共引网络

4.3耦合

两篇文章的耦合指同时被这两篇文章引用的其他文章的数量，可构造无向的耦合网络

4.4总结要点

• 将有向网络转化为无向网络便于分析，以引文网络为例从一个有向网络得到无向网络有两种对偶方法：共引和文献耦合

• 共引程度反映了两篇文献同时被多少篇文章同时引用，耦合程度反映了两篇文章同时引用了多少篇相同的文献

• 共引和耦合都反映了文章的研究课题的相关性，但耦合网络更能体现研究的强相关性

• 共引是稀疏的，耦合是相对稠密的

• 文献耦合是文章之间相似性的一种更为一致（均匀）的指标；一篇文章的参考文献固定不变，但引用次数随时间变化