Минимално допълнение към силно свързана графа
Минимално допълнение към силно свързана графа
Дадена е насочена графа. Броят на върховете е около десет в четвъртия, броят на ръбовете е около десет в петия. Трябва да намерим минималния брой ребра, така че графът да стане силно свързан. Как да го направим? Разбирам, че трябва да разделите графиката на силно свързани компоненти, след което да преброите колко компонента нямат изходящи ръбове и колко нямат входящи. Отговорът е максималното от тези числа. Проблемът е, че не мога да разбера как да изградя тези ръбове по-късно.
Алгоритъмът за решаване на този проблем се основава на избиране на граф от източници, поглътители и изолирани върхове в кондензация и свързването им в определен ред. Асимптотична O(n+m). Алгоритъмът е описан подробно в статията „Бележка за алгоритъма на Eswaran и Tarjan за проблема за увеличаване на силната свързаност“ (S. Raghavan). В българоезичния сегмент на мрежата явно няма нищо адекватно.
Струва ми се, че може да се изгради по този начин.
Новата графа, представена като силно свързани компоненти, ще бъде насочена и ациклична. Нека извършим топологично сортиране на върховете в нов граф. Нека намерим всички върхове, от които е невъзможно да се премине към друг връх, нека условно ги наречем "листа". Нека намерим всички върхове, които не могат да бъдат достигнати от други върхове, нека условно ги наречем "корени". Ако номерираме свързаните компоненти на новата графика от 1 до N, тогава желаните ребра ще изглеждат така:
"Лист 1" - "Лист 2" - . - "лист N" - "корен N" - "корен N - 1" - . — „корен 1“. Това ще направи възможно да стигнете от всеки връх до който и да е: слезте до листата, отидете до „листа N“, отидете нагоре до „корена N“, отидете до желания „корен“, слезте до върха, който ви интересува.
Вашият отговор е твърде голям. Например в графика като тази:
Верният отговор е 2 (свържете 15 и 24). Ще имате четири ребра.
Ако въпросът е в асимптотиката, тогава той се решава чрез изхвърляне на ненужното, от всички ръбове, включени в долния компонент, е достатъчно да оставите един, от всички ръбове, излизащи от горния компонент, също е достатъчно да оставите един, но отговорът не се променя. (Всъщност можете да отпаднете до състояние на набор от храсти, растящи нагоре, набор от храсти, растящи надолу, и отделни върхове, всичко това може да бъде свързано конструктивно в цикъл и след това да добавите листа; но не е необходимо да пускате достатъчно ръбове до 2 * брой върхове.) Освен това, свържете се в цикъл, тъй като има малко ръбове, тогава компонентът за сливане ще бъде бърз.
Честно казано, не разбрах за какво говориш.
Нека имаме максимални и минимални силно свързани компоненти, от някои максимални можем да отидем до някои минимални, т.е. всъщност имаме двуделна графа, върху която трябва да решим проблема.
Стъпка 2: (което НЕ Е НЕОБХОДИМО да се прави) ще изградим сдвояване върху оставащия граф (много бързо, защото има максимум върхове), върховете, които са били свързани с нещо, но не са били свързани с нищо, ще бъдат свързани с нещо. Тогава получаваме граф, състоящ се от обекти от три типа: един връх, храст нагоре, храст надолу (храстът е връх на един компонент, свързан с няколко върха на друг компонент).
Стъпка 3: (същинска конструкция) започваме от някакъв връх на по-малкия от двата компонента на двуделния граф (компонент 1), съхраняваме списък (S) от върхове от (компонент 2), до които можем да достигнем от този начален връх. Добавяме към списъка (S) всички върхове, до които можем да стигнем от текущия, вземаме всеки връх от новодобавените (не от целия списък S, а от новодобавените към списъка) и рисуваме до ръба внякои от върховете, които са свързани с някакъв връх извън списъка S. Повтаряме операцията, докато списъкът S покрие всички върхове, в този случай затваряме пътя: от някой новодобавен връх към S рисуваме ребро към върха, от който сме започнали пътуването. След това можете да разпръснете ребрата така или иначе.