COMP5313 Tutorial 04 — Graphs 详细题解

图结构勘误：Tutorial PDF 的图 3 文字描述与 Exercise 3 NetworkX 代码片段的边集不一致。以 NetworkX 代码为准，图 3 共有 10 条边，而非 9 条。具体边集见下方。

图 1 回顾

边集（无向图）：A-B, A-C, A-F, B-C, B-G, C-F, D-E, F-G, F-E（共 9 条）

graph LR
    A((A)) --- B((B))
    A --- C((C))
    A --- F((F))
    B --- C
    B --- G((G))
    C --- F
    D((D)) --- E((E))
    F --- G
    F --- E

Exercise 1：BFS

a) 网络有多少条边？

答案：9 条边

Chapter 1: Overview（概述）

教材：Networks, Crowds, and Markets: Reasoning about a Highly Connected World 作者：David Easley & Jon Kleinberg, Cambridge University Press, 2010

一、章节总览

第一章是整本书的导论，介绍了本书研究的核心问题：如何理解高度互联的现代社会中的复杂"连接性"（connectedness）。本章的核心概念是网络（network）——即一组事物之间的互连模式（a pattern of interconnections among a set of things）。网络无处不在，出现在社交关系、信息传播、技术系统、经济系统等众多领域中。

本章主要完成三项任务： 1. 介绍网络的基本概念与多样性实例 2. 提出理解网络需要的两个核心理论框架：图论（Graph Theory） 和 博弈论（Game Theory） 3. 预览全书的核心主题与章节安排

二、网络的基本概念（What is a Network?）

2.1 定义

网络（Network） 在最基本的意义上，是指一组对象（objects）的集合，其中某些对象对之间通过链接（links） 相连接。这个定义非常灵活：取决于具体场景，许多不同形式的关系或连接都可以用来定义链接。

Chapter 2: Graphs（图）

教材：Networks, Crowds, and Markets: Reasoning about a Highly Connected World 作者：David Easley & Jon Kleinberg, Cambridge University Press, 2010

一、章节总览

第二章是全书第一部分（图论与社会网络） 的开端，系统介绍了图论（Graph Theory） 的基本概念。图论为研究网络结构提供了统一的数学语言。本章从最基础的定义出发，逐步引入路径、连通性、距离、广度优先搜索等核心概念，并通过大量真实网络案例加以说明。最后概述了大规模网络数据集的主要来源。

二、基本定义（Section 2.1: Basic Definitions）

2.1 图的定义

图（Graph） 是一种描述一组事物之间关系的方式。一个图由以下两部分组成：

• 节点（Nodes）：又称顶点（vertices），代表图中的对象，通常用小圆圈表示
• 边（Edges）：又称链接（links），连接某些节点对，通常用线段表示