Clever Geek Handbook

Construct graph from given node degrees

I have to find which of the following values ​​can be degrees of an undirected graph with 6 vertices:

a) 3 2 2 2 3 3
b) 4 2 2 2 3 2
c) 5 2 2 2 0 3
d) 5 2 2 2 1 2

I just found a method to try and draw a graph on a piece of paper and then check if this is possible. I just need a hint to start this problem, if possible, other than drawing each graph.

+3


source to share


2 answers


The following algorithm decides if a simple graph with given node degrees can be built:

  • sort degrees descending

  • if the first degree is 0 (i.e. all degrees are 0), then obviously such a graph can be generated (no edges) and you're done.

  • if the first degree is d

    (> 0), then the next degrees d

    must be greater than 0. If you are not finished: such a graph cannot be generated.

  • remove the first degree (value d

    ) and decrease the next d

    degrees by one (i.e. draw the requested number of edges from the node with the highest degree to the nodes with the highest level among the rest - see the proof below for this assumption to be correct), then go to step 1 ( with now one node less)

example a) (can be rejected due to odd sum of weights, but the above algorithms also work)

3 2 2 2 3 3
3 3 3 2 2 2
  2 2 1 2 2
  2 2 2 2 1
    1 1 2 1
    2 1 1 1
      0 0 1
      1 0 0
        -1   not possible

example c)

5 2 2 2 0 3
5 3 2 2 2 0
  2 1 1 1 -1   not possible


example d)

5 2 2 2 1 2 
5 2 2 2 2 1
  1 1 1 1 0
    0 1 1 0
    1 1 0 0
      0 0 0  ok

There is no evidence that if a graph can be drawn with given node degrees, then one of the coinciding graphs has this property for step 4, i.e. that the node with the highest degree is associated with the nodes with the next highest degree.

Suppose there A

is a node with the highest degree and that it is associated with a node B

whose degree is less than the degree of a node C

not associated with A. Since degree(B) > 0

, we know degree(C) > 1

. Hence, there is another node d

associated with C

. So, we have edges AB

and CD

, which we can replace with eges AC

and BD

without changing the degrees of the nodes.

By repeating this procedure enough, we can make all nodes with the next highest degrees associated with the node with the highest degree.

+10


source


a link to a confirmation link or a degree sum formula is a necessary and sufficient condition in this case, since all we have to do is for it to form an undirected graph (the orientation of the edge does not matter, but nothing is said about the loop or parallel edges). Therefore option c and option d are valid 6-vertex undirected graphs.



If the question is asking a simple undirected graph (loopback and parallel edges are not allowed), we need to introduce the Havel / Hakimi algorithm , which is described by @coproc.

+2


source






More articles:


All Articles