79 views
You are given $n$ positive integers, $d_1, d_2 \dots d_n$, each greater than 0. Design a greedy algorithm to test whether these integers correspond to the degrees of some $n$-vertex simple undirected graph $G = (V, E)$. [A simple graph has no self-loops and at most one edge between any pair of vertices].
edited | 79 views

1. Sort the degrees in non-increasing order.
2. Pick up the highest degree ( let us say it a), remove it from the list of degrees and subtract 1 from next a degrees in list.
3. Repeat Step $2$ until :
• If we get all $0$ entries in list $\color{red}{\Rightarrow}$ Simple Graph exits
• If we get a negative entry or not enough entries to subtract 1 in step 2 $\color{red}{\Rightarrow}$ Simple Graph does not exist

Let's take a example : $3, 2, 1, 2$

Step 1 : Sort the degree sequence : $3, 2, 2, 1$

Step 2: Pick 3, Remove 3 from list and from next 3 elements subtract 1,   $Result : (1,1,0)$

Again repeat step 2 : select 1, Remove 1 and from next 1 subtract 1,  $Result : (0,0,0)$

Thus, a simple graph exists for the following degree-sequence.