高级算法 (Fall 2023)/Problem Set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Zouzongrui (talk | contribs)
No edit summary
Zouzongrui (talk | contribs)
No edit summary
Line 14: Line 14:
* ['''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>.
* ['''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>.


== Problem 1 (Adjacency matrix) ==
== Problem 1 (Graph Laplacian) ==
* ['''Spectrum of special graphs'''] Find eigenvalues of the Laplacian matrices of the following graphs:
** The complete graph with <math>n</math> vertices.
** The star graph with <math>n</math> vertices.

Revision as of 07:29, 24 November 2023

  • 本次作业每个Problem分值10分,满分 分。
  • 每道题目的解答都要有完整的解题过程,中英文不限。
  • 我们推荐大家使用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].

Problem 1 (Graph Laplacian)

  • [Spectrum of special graphs] Find eigenvalues of the Laplacian matrices of the following graphs:
    • The complete graph with [math]\displaystyle{ n }[/math] vertices.
    • The star graph with [math]\displaystyle{ n }[/math] vertices.