高级算法 (Fall 2023)/Problem Set 2

• 每道题目的解答都要有完整的解题过程，中英文不限。

• 我们推荐大家使用LaTeX, markdown等对作业进行排版。

Problem 1 (Adjacency matrix)

Let [math]\displaystyle{ A }[/math] be the adjacency matrix of an undirected connected graph [math]\displaystyle{ G }[/math], and [math]\displaystyle{ \alpha_1 }[/math] be its largest eigenvalue.

• [Lowerbounding [math]\displaystyle{ \alpha_1 }[/math]] We proved [math]\displaystyle{ \alpha_1 \le d_{\mathrm{max}} }[/math] in class. Show that [math]\displaystyle{ \alpha_1 \ge d_{\mathrm{avg}} }[/math] where [math]\displaystyle{ d_{\mathrm{avg}}:=\frac{2|E|}{|V|} }[/math] is the average degree of the graph.