Skip to content

Acm Problem: Graph Construction(10720) + Dream (11414)

July 31, 2011

Acm Problem: Graph Construction(10720) + Dream (11414)

This 2 problems are basically same. Here you are given degree sequence of graph and you have to find whether or not that sequence is graphic that is you can make a graph from that sequence.

There is a excellent algorithm for this problem named Havel-Hakimi algorithm.

The algorithm for the degree sequence S as follows-

1. If there exists an integer d in S such that d > n−1 then halt and report failure.
That is, we cannot have a vertex that is adjacent to more than n − 1 other vertices.

2. If there are an odd number of odd numbers in S halt and report failure.
That is, there must be an even number of vertices of odd degree.

3. If the sequence contains a negative number then halt and report failure.

4. If the sequence is all zeros then halt and report success.

5. Reorder S such that it is non-increasing.

6. Delete the first term d1 from S and subtract one from the next d1 terms to form a new sequence. Go to step 3

Consider the following input from sample input

6 2 4 5 5 2 1

and now follow the algorithm

a. The 1st condition (di > n−1 ) for i=0 to n-1 does not meet so continue.

b. The 2nd condition meet (there are an odd number of odd number),so the answer is not possible.

Another input-

6 1 3 4 2 5 2

a. The 1st condition (di > n−1 ) for i=0 to n-1 does not meet so continue.

b. The 2nd condition does not meet, so continue.

c. Now enter into a loop-

iteration: 1

c.1 3rd condition does not meet.

c.2 4th condition does not meet.

c.3 Sort the input.Looks like- 5 4 3 2 2 1

c.4 Now set x=value of first term,in this case it is 5. Now delete the first term.

so sequence is -> 4 3 2 2 1. Next subtract 1 from next x=5 item where x is the value of

deleted item.so the sequence is – 3 2 1 1 0.

iteration: 2

c.1 3rd condition does not meet.

c.2 4th condition does not meet.

c.3 Sort the input.Looks like- 3 2 1 1 0

c.4 Now set x=value of first term,in this case it is 3. Now delete the first term.

so sequence is -> 2 1 1 0. Next subtract 1 from next x=3 item where x is the value of

deleted item.so the sequence is 1 0 0 -1.

iteration: 3

c.1 3rd condition meet. So break and output not possible.

Advertisements
One Comment leave one →
  1. Farsan permalink
    May 10, 2013 4:29 am

    Thanks it was helpful. 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: