GATE CSE
First time here? Checkout the FAQ!
x
0 votes
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].
asked in Algorithms by Veteran (76.3k points)  
edited by | 79 views

1 Answer

+2 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.

answered by Veteran (24.6k points)  
edited by


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,088 questions
28,063 answers
63,298 comments
24,173 users