GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
110 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 (79k points)  
edited by | 110 views

1 Answer

+3 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.9k points)  
edited by
The link was very helpful. A must read.


Top Users Aug 2017
  1. ABKUNDAN

    4658 Points

  2. Bikram

    4134 Points

  3. akash.dinkar12

    3144 Points

  4. rahul sharma 5

    2928 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2390 Points

  7. just_bhavana

    2058 Points

  8. Tesla!

    1782 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,892 questions
31,967 answers
74,213 comments
30,083 users