Optymalne dopasowanie

piątek, Listopad 8, 2013 Brak komentarzy

Często w zastosowaniach (np. logistycznych) pojawia się potrzeba optymalnego (np. najtańszego) połączenia w pary elementów (np. przydział zadań serwisantom). Jest to realizowane przez znalezienie minimalnej transwersali w (kwadratowej) macierzy kosztów. Minimalną transwersalę można znaleźć efektywnie przez algorytm węgierski, podany przez Kuhna w 1955r. Pod tym linkiem znajduje się impelementacja algorytmu w formie makra w MS […]

Znajdowanie wszystkich drzew spinających

niedziela, Grudzień 16, 2012 Brak komentarzy

Ilość drzew spinających, jakie ma dany nieskierowany, etykietowany graf można wyznaczyć przez macierzowe twierdzenie o drzewach. Ilustracją twierdzenia może być aplikacja dostępna pod poniższym linkiem wyznaczająca wszystkie drzewa spinające zadanego grafu. Aplikację została napisana za pomocą HTML5 oraz jQuery. Jej autorami są studenci: Tomasz Adrianowski i Sliman Jakub El-Fara. Drzewa spinające