edited by
1,565 views
16 votes
16 votes
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 by

2 Answers

Best answer
22 votes
22 votes
  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

Read More : http://goo.gl/4u3nfh

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.

edited by

Related questions

4 votes
4 votes
2 answers
2