高级算法 (Fall 2023)/Problem Set 2: Difference between revisions
Jump to navigation
Jump to search
Zouzongrui (talk | contribs) |
Zouzongrui (talk | contribs) |
||
| Line 7: | Line 7: | ||
Let <math>A</math> be the adjacency matrix of an undirected connected graph <math>G</math>, and <math>\alpha_1</math> be its largest eigenvalue. | Let <math>A</math> be the adjacency matrix of an undirected connected graph <math>G</math>, and <math>\alpha_1</math> be its largest eigenvalue. | ||
* ['''Lowerbounding <math>\alpha_1</math>'''] We proved <math>\alpha_1 \le d_{\mathrm{max}}</math> in class. Show that <math>\alpha_1 \ge d_{\mathrm{avg}}</math> where <math>d_{\mathrm{avg}}:=\frac{2|E|}{|V|}</math> is the average degree of the graph. | * ['''Lowerbounding <math>\alpha_1</math>'''] We proved <math>\alpha_1 \le d_{\mathrm{max}}</math> in class. Show that <math>\alpha_1 \ge d_{\mathrm{avg}}</math> where <math>d_{\mathrm{avg}}:=\frac{2|E|}{|V|}</math> is the average degree of the graph. | ||
* ['''Monotonicity of the spectrum'''] Let <math>A'</math> be the adjacency matrix of any subgraph of <math>A</math> produced by deleting vertices, and let <math>\alpha_1'</math> be the largest eigenvalue of <math>A'</math>. Show that <math>\alpha'_1\leq \alpha_1</math>. | |||
* ['''Coloring number'''] The chromatic number <math>\chi(G)</math> of a graph is the smallest number of colors needed to color the vertices of <math>G</math> so that no two adjacent vertices share same color. Prove that <math>\chi(G) \le \lfloor \alpha_1 \rfloor +1</math>. | |||
Revision as of 07:26, 24 November 2023
- 每道题目的解答都要有完整的解题过程，中英文不限。
- 我们推荐大家使用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.
- [Monotonicity of the spectrum] Let [math]\displaystyle{ A' }[/math] be the adjacency matrix of any subgraph of [math]\displaystyle{ A }[/math] produced by deleting vertices, and let [math]\displaystyle{ \alpha_1' }[/math] be the largest eigenvalue of [math]\displaystyle{ A' }[/math]. Show that [math]\displaystyle{ \alpha'_1\leq \alpha_1 }[/math].
- [Coloring number] The chromatic number [math]\displaystyle{ \chi(G) }[/math] of a graph is the smallest number of colors needed to color the vertices of [math]\displaystyle{ G }[/math] so that no two adjacent vertices share same color. Prove that [math]\displaystyle{ \chi(G) \le \lfloor \alpha_1 \rfloor +1 }[/math].