CODEWITHSUNDEEP
graph
user3243499
user3243499

Reputation: 3161

How to construct a tree given each degrees maximum degree?

I have a "maximum" degree sequences of graph vertices. Now I want to construct a tree where every nodes have "AT most" coresponding maximum degree.

For example, if my maximum degree sequence is A = [3,4,2,1,4,3] then I want to make a tree of 6 vertices and each vertex having "maximum degree" corresponding to its value in A.

So far I tried with vertex coloring, but not able to get a tree, rather sometimes I get a graph having a cycle in it.

Upvotes: 1

Views: 1830

Answers (1)

Pac0
Pac0

Reputation: 23174

First let's recall an important fact on degrees of a tree with n vertices : total of degrees is always 2*(n-1) . The converse is also true, a graph is a tree if its degree sum is 2*(n-1). And actually, any sequence of natural numbers that gives 2*(n-1) could represent the degrees of a tree.

So the general algorithm for your problem should look like this :

  1. Reduce the "max degrees" list to an actual "degree list".

  2. From the list of degrees, use any graph construction algorithm. The resulting graph will be a tree because of the sum of degrees.

Note that : there might be several possibilities, but at the end, the total edge cost will be the same, (n-1) * cost of one edge , whatever is the resulting tree!

Example :

take sequence A = [3,4,2,1,4,3] . Total is 17. We should have 10 to have a tree.

Let's reduce by one every degree greater than one.

It gives : B = [2,3,1,1,3,2]. Total is 12.

Let's reduce by one the 2 first degreed greater by one we find :

It gives : C = [1,2,1,1,3,2]. Total is 10. This is the degree list of a tree.

Let's draw it.

Start by the degree one vertices (there must be at least 2 of them), then append by increasing order of degrees :

1--
1--
1--

1--2--
1--2--
1--

1--2--\
1--2---3
1-----/

Sorry my ASCII ART skills are not the best.

To be more specific : we whould try to link "greedily" n-1 vertices on the right of the diagram with any left vertex of degree n. Excepted for the last one which should link whatever is remaining.

example for [3, 3, 3, 1, 1, 1, 1, 1]

1--
1--
1--
1--
1--

1---3
1--/
1---3
1--/
1--

1---3-\
1--/   \
1---3---3
1--/   /
1-----/

Upvotes: 2

Related Questions