## Graphical sequence - havel and hakimi

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### Graphical sequence - havel and hakimi

the theorem states -> (replace x with p)httx://img2.freeimagehosting.net/uploads/5c734dcd85.jpg
now consider a sequence d = 5 5 5 4 3 2 1 1 and now what is d'? i see in a book d' = 4 4 3 2 1 1 1 . I dont understand the "dd1+2 ......dn" part .what goes between the term dd1+2 and dn?

fairplay

Posts: 18
Joined: Mon Feb 25, 2008 1:52 pm

It's not that hard to read. The formula means that you remove the first number from the list, and since it was a 5, you subtract 1 from the next 5 elements.

In C++:
[syntax="cpp"]#include <iostream>
#include <vector>

std::vector<int> Havel_and_Hakimi(std::vector<int> const &d) {
std::vector<int> result;

for(int i=0;i<d[0];++i)
result.push_back(d[i+1]-1);
for(int i=d[0]+1;i<d.size();++i)
result.push_back(d[i]);
return result;
}

/* Alternative implementation:
std::vector<int> Havel_and_Hakimi(std::vector<int> const &d) {
std::vector<int>::const_iterator b=d.begin();
++b;
std::vector<int> result(b,d.end());

for(int i=0;i<d[0];++i)
--result[i];
return result;
}
*/

int main() {
int a[]={5,5,5,4,3,2,1,1};
std::vector<int> d(a,a+sizeof(a)/sizeof(*a));
std::vector<int> x=Havel_and_Hakimi(d);
for(int i=0;i<x.size();++i)
std::cout << x[i] << ' ';
std::cout << '\n';
}

[/syntax]

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

### thanks alvaro

thanks alvaro

fairplay

Posts: 18
Joined: Mon Feb 25, 2008 1:52 pm