COMP5270 Assignment 2 Problem 2(b), 生成 Kn 完全图和 Cn 环图

COMP5270 Assignment 2 Problem 2(b), 生成 Kₙ 完全图和 Cₙ 环图

中文题目

实现两个函数：输入 \(n\)，返回 (1) \(n\) 个顶点的完全图 \(K_n\)；(2) \(n\) 个顶点的环图 \(C_n\)。

原题

Implement two functions returning, on input \(n\), (1) the complete graph \(K_n\) on \(n\) vertices; (2) the cycle graph \(C_n\) on \(n\) vertices.

知识点

• 完全图（complete graph）
• 环图（cycle graph）
• 邻接表（adjacency list）
• 图的 API 设计

---

核心思路

这道题是整个 Assignment 2 的基础设施题。后续所有 MaxCut 实验都依赖这两个函数生成的图，所以理解它们的结构很重要。

完全图 \(K_n\)

完全图 \(K_n\) 是任意两个不同顶点之间都有一条边的图。对角化来说：

• 顶点：\(n\) 个，通常编号为 \(0,1,\dots,n-1\)
• 边：共 \(\binom{n}{2} = \frac{n(n-1)}{2}\) 条
• 度数：每个顶点的度数为 \(n-1\)

实现方式是两层循环：外层遍历所有顶点，内层从该顶点的下一个顶点开始，遍历到最后一个顶点，每对顶点插入一条边。

环图 \(C_n\)

环图 \(C_n\) 是 \(n\) 个顶点排成一个环，每相邻两个顶点之间有一条边，首尾顶点也相连：

• 顶点：\(n\) 个，编号 \(0,1,\dots,n-1\)
• 边：共 \(n\) 条，恰好每个顶点度数为 \(2\)
• 结构：视觉上是一个环

实现方式是连接 \((0,1), (1,2), \dots, (n-2, n-1)\)，最后 \((n-1, 0)\) 形成闭环。

---

参考实现

from graph import Graph

def complete_graph(n):
    G = Graph()
    for i in range(n):
        G.insert_vertex(i)
    for i in range(n):
        for j in range(i + 1, n):
            G.insert_edge(i, j)
    return G

def cycle_graph(n):
    G = Graph()
    for i in range(n):
        G.insert_vertex(i)
    for i in range(n):
        G.insert_edge(i, (i + 1) % n)
    return G

注意： - 完全图的双层循环中，内层从 i + 1 开始，避免重复插入同一条边（因为 Graph API 的 insert_edge 会把 \((u,v)\) 和 \((v,u)\) 当作同一条边） - 环图用 (i + 1) % n 自动处理 \(n-1\) 到 \(0\) 的回边，这是 Python 里写环结构的常用技巧

---

两种图在后续问题中的角色

图	\(K_n\) 的特点	\(C_n\) 的特点
边数	\(\Theta(n^2)\)	\(\Theta(n)\)
每个顶点度	\(n-1\)	\(2\)
MaxCut 最优值	\(\lfloor n^2/4 \rfloor\)	\(n\) 或 \(n-1\)
随机算法效果	接近最优，方差小	约 \(n/2\)，方差较大

这两个图是后续实验的基准测试用例，分别代表稠密图和稀疏图两种极端情况。

---

容易错的地方

1. 完全图循环边界：内层从 i + 1 开始，不是 0。否则会重复插入边或者漏掉某些边对。
2. 环图的首尾连接：最后一条边 (n-1, 0) 容易忘掉，用取模技巧可以自动覆盖。
3. Graph API 的语义：insert_edge(u, v) 会同时在邻接表中加入 u -> v 和 v -> u，不需要手动处理无向边的双向插入。