Optymalne rysowanie grafu

[nooga]

Hej.

Szukam metody optymalnego narysowania grafu tak, aby wierzcholki zostały rozłożone na kwadratowej siatce w sposób, przy którym suma długości krawędzi będzie minimalna.

Załóżmy, że posiadam graf o ok. 9 wierzchołków, każdy z nich posiada dokładnie 3 krawędzie prowadzące do innych wierzchołków. Wierzchołki są dwóch typów: A i B. Chodzi o to, żeby poustawiać te wierchołki np tak (gdyz zakładamy, że w tym przypadku da to minimalną długość krawędzi na rysunku):

A A B
B B B
A A A

A następnie narysować krawędzie. Krawędzie mogą się przecinać, mogą także przecinać obrazy wierzchołków.

Dodam, że algorytm powinien działać na stosunkowo dużych grafach - parę tys wierzchołków więc bruteforce nie wchodzi w grę raczej. Myślę, że da się to zrobić w jakiś deterministyczny sposów, jednak po popytaniu googla i poczytaniu paru prac nadal nie jestem w stanie tego sam wymyślić.

Pozdrawiam i liczę na jakieś podpowiedzi

[kwak2k]

znaczy masz juz odgornie ustalone polaczenia i tylko pustawiac zeby bylo jaknamniejsza dlugosc polaczen ?

[nooga]

Zgadza się. Graf jest gotowy. Należy go tylko "narysowac" w taki sposob jak mowilem aby dlugosci polaczen byly jak najmniejsze.

[ Dodano: 23 Listopada 2008, 11:31 ]
Zgadza się. Graf jest gotowy. Należy go tylko "narysowac" w taki sposob jak mowilem aby dlugosci polaczen byly jak najmniejsze.

[Xitami]

Niech... wierzchołki mają masę, czyli bezwładność ale niech nie działa grawitacja, wszystkie wierzchołki mają identyczny ładunek, krawędzie są idealnymi sprężynkami, a przestrzeń będzie skwantowana.

No i niech moc (obliczeniowa) będzie z Tobą.

[nooga]

A to nie spowoduje, że każdy węzeł ustawi się w równej odległości euklidesowej od innych?