I am trying to solve this problem in which I am given a number n, representing the number of vertexes in a undirected graph. On the next line there are n natural numbers representing the degree of the respective vertex. I am asked to find the edges, such that the graph is connected.
n<=5000 and it is forbbiden that two or more edges connect the same two vertexes.
LE: Also, there will always exist a graph with the degrees given in the tests.
First condition : The sum of degrees of a graph must be even. So first you can sum all of your degrees must be even. ( however this is not a sufficient condition).
Second condition : Every node in your graph must have at least degree 1, and at most degree N-1. (Also not a sufficient, but rather necessary condition).
The sequence 3,3,3,1 meets the above two conditions, however no graph corresponds to it.
If both of these conditions are not met, then you should output there is no such graph, however if they do, it requires a complex theorm to compute that is somehow defined inductively ( google it). Do you have a link to this problem? Once you determine if it's graphical, it should be easy to implement it.
Erdős–Gallai theorem
Yeah, I have found that theorem, but it says the conditions for which exists a graph with given degrees, but not how to construct one.
You can use Havel Hakimi Algorithm wich is described clearly in the link!! :)
Does it guarantee that the graph will be connected?
Auto comment: topic has been updated by pas.andrei (previous revision, new revision, compare).
Hii can anyone share the conclusion or resources from where we can read about constructing a connected graph given the degree of sequences...
Smallest-First Havel–Hakimi Algorithm