Алгоритам обрнуто брисање

Из Википедије, слободне енциклопедије

Алгоритам обрнуто брисање је алгоритам у теорија графова се користи за добијање минималног разапињућег стабла из датог повезаног тежинскоg графа . Он се први пут појавио kод Kрускал-a 1956. , али то не треба мешати са алгоритмом Крускал-а који се помиње у овој области. Уколико граф није повезан, овај алгоритам ће наћи минимално разапињуће стабло, одвојено за сваки део графа. Скуп ових минималних разапињућих стабала се зове минимална разапињућа шума, која садржи сваки чвор графа.

Овај алгоритам је похлепни алгоритам, бира најбољи избор у сваком тренутку у задатој ситуацији. То је супротно од Крускал-овог алгоритма, што је још један похлепни алгоритам који проналази минимално Разапињуће стабло. Крускал-ов алгоритам почиње са празним графом и додаје гране, док Обрнуто-Брисање почиње са оригиналном графом и брише из гране њега. Алгоритам ради на следећи начин:

  • Почиње са графом Г, који садржи листу грана Е.
  • Иде до Е по опадајућем редоследу тежине грана.
  • За сваку грану, проверите да ли ће брисање направити неповезан граф.
  • Извршите брисања која не доводе до додатних искључења.

Псеудокод[уреди]

 1  function ReverseDelete(edges[] E)
 2    sort E in decreasing order
 3    Define an index i ← 0
 4    while i < size(E)
 5       Define edge tempE[i]
 6         delete E[i]
 7         if temp.v1 is not connected to temp.v2
 8             E[i] ← temp
 9         ii + 1
 10   return edges[] E

Горњи граф је скуп грана Е где свака грана има тежину и повезује чворове v1 и v2.

Пример[уреди]

У следећем примеру зелене гране се процењују у алгоритму а црвене гране су избрисане.

Reverse Delete 0.svg Ово је наш оригинални граф. Бројеви на грани говоре тежину гране.
Reverse Delete 1.svg Алгоритам ће почети са граном максималне тежине, што је у ово случају DE тежине 15. Пошто брисање грана DE не узрокује распадање графа , грана се брише.
Reverse Delete 2.svg Следећа највећа грана је FG , алгоритам ће проверити да ли брисањем ове гране долази до распада графа. Пошто брисање гране неће довести дотле, грана је тада обрисана.
Reverse Delete 3.svg Следећа највећа грана је BD, па ће алгоритам проверити ову грану и избрисати је.
Reverse Delete 4.svg Следећа грана је да проверите грану EG, која неће бити избрисана јер би искључили чвор G из графа. Дакле, следећа грана за брисање је BC.
Reverse Delete 5.svg Следећа највећа грама је грана ЕF, тако ће алгоритам проверити ову грану и избрисати је.
Reverse Delete 6.svg Алгоритам ће онда тражити преостале гране и неће наћи другу грану да обрише, па ово је коначни граф који нам враћа алгоритам.

Време извршавања[уреди]

За алгоритам се може доказати да ради у О (E log V (log log V)3) времену, где јеЕ је број грама и V је број чворова. Ова граница се достиже на следећи начин:

  • Сортирање грана по тежини помоћу поређења у О ( Е лог Е) времену
  • Е итерације петље
  • Брисање уО (1) времену
  • Повезивање проверити у O(logV (log log V)3) времену Thorup 2000.

Исто тако, време рада може се сматрати О (E log E (log log E)3) јер највећи Е може се V 2. Запамтите да logV 2 = 2 * log V, па 2 је мултипликативна константа која ће бити игнорисана у нотацији великог O.

Литература[уреди]