GATE CSE
First time here? Checkout the FAQ!
x
0 votes
81 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 (77.2k points)  
edited by | 81 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.7k points)  
edited by


Top Users May 2017
  1. akash.dinkar12

    3152 Points

  2. pawan kumarln

    1616 Points

  3. sh!va

    1580 Points

  4. Arjun

    1336 Points

  5. Devshree Dubey

    1230 Points

  6. Angkit

    1028 Points

  7. Debashish Deka

    1012 Points

  8. Bikram

    972 Points

  9. LeenSharma

    810 Points

  10. srestha

    662 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. pawan kumarln

    242 Points

  2. Ahwan

    138 Points

  3. joshi_nitish

    112 Points

  4. jjayantamahata

    104 Points

  5. Arjun

    64 Points


22,725 questions
29,056 answers
65,053 comments
27,566 users