Witam.
Mam pewien problem, do którego nie mogę znaleźć wskazówki i rozwiązania.
Graf w którym między każdą parą węzłów jest tylko jedna droga i "niszcząc" dwie z nich mam podzielić graf na trzy jak najrówniejsze części. A dokładniej w taki sposób, aby pozostało jak najmniej par węzłów między którymi da się przejść.
Myślałem o podziale przez centroid, ale jednak nie wiem jak go wykorzystać do podziału na inne części niż połowy, ćwiartki, 1/8 itd.
Liczę na pomoc.
0
1
Twój graf jest drzewem(jak w tytule),czyli to taki 'patyczak' bez żadnych pętli, wiec sprawa jest dość prosta. Znajdujesz wszystkie liście, a następnie zaczynając od tych liści iterujesz i obliczasz ile każda krawędź zostawiła by za sobą po odcięciu z jednej i drugiej strony. Najlepiej zrobić to 2 razy na papierze, przed implementacją. Tak jak na obrazkach(tylko bez błędu na 5/5 ;)). Ilość par z jakich można dojść do siebie nawzajem (to co optymalizujesz) możesz policzyć ze wzoru na sumę szeregu arytmetycznego n - to liczba elementów w drzewie/jego wycinku.
Jak już to wszystko z robisz to wynik możesz znaleźć bruteforcem w czasie n^2 wystarczy trzymać liczbę już odciętych węzłów w pamięci i iterować wzdłoż struktury drzewa . Pewnie można zbić wszystko do n ale n^2 też jest ładne.