Witam.
Szukałem jakichś algorytmów do znajdowania skojarzeń doskonałych o minimalnej sumie wag krawędzi w grafach ważonych. Przekopałem się przez mnóstwo różnorakiej literatury i znalazłem dwie możliwości. Algorytm Edmondsa albo algorytm zaprezentowany przez Wattenhoferów tutaj:
Doszedłem do wniosku, że chciałbym skorzystać z algorytmu Wattenhoferów. Jednakże mam kilka problemów ze zrozumieniem go. Czy ktoś byłby tak dobry i wytłumaczyłby mi rzeczy, których nie rozumiem? Rzeczy tych jest kilka:
Po pierwsze, skoro w pierwszym obrocie pętli za komponenty przyjmujemy wierzchołki, to wiadomym jest, że ilość krawędzi w wierzchołkach jest równa 0. Zatem oznaczałoby to, że każdy komponent jest nieaktywny i tak naprawdę nic się nie wydarzy.
Po drugie, co jeśli pozostanie nam tylko jeden komponent, który jest aktywny? Pętla wtedy trwa w nieskończoność?
Po trzecie - czym w teorii grafów jest "shortcutting", które jest używane w algorytmach 2 i 3? Szukałem informacji na ten temat w internecie, ale niczego jednoznacznego niestety nie znalazłem.
Będę wdzięczny za odpowiedź na którekolwiek z tych pytań. Pozdrawiam.