Cactus graph realization of degree sequence
Degree sequence 그래프에서, Degree sequence란 undirected graph의 각 정점의 차수(degree)를 늘어놓은 수열을 말한다. Graph realization problem이란, 수열이 주어졌을 때 그 수열을 degree sequence로 갖는 그래프를 실제로 construct하는 문제를 말한다. 여기서 다루는 그래프는 self-loop나 multiedge가 존재하지 않는 simple graph이다. 어떤 Degree sequence가 주어졌을 때, 이를 만족하는 simple graph가 존재할 조건은 Erdos - Gallai theorem 으로 널리 알려져 있다. 정리 1 (Erdos - Gallai theorem). $d_1 \ge d_2 \ge … \ge d_n \ge 0$ 가 finite simple...