Fordított törlési algoritmus

A visszatörlési algoritmus  egy olyan gráfelméleti algoritmus , amely egy adott összekapcsolt vonalsúlyozott gráfból egy minimális feszítőfát állít elő . Az algoritmus először Kruskal cikkében jelent meg [1] , de nem szabad összetéveszteni Kruskal algoritmusával , amely ugyanebben a cikkben jelent meg. Ha a gráf nincs összekapcsolva, ez az algoritmus a gráf minden egyes részéhez megkeresi a minimális feszítőfát. Ezeknek a minimális feszítőfáknak a halmazát nevezzük minimális feszítőerdőnek, amely a gráf összes csúcsát tartalmazza.

Az algoritmus egy mohó algoritmus , amely a legjobb megoldást adja. Ez ellentéte a Kruskal-algoritmusnak , amely egy másik mohó minimum feszítőfa algoritmus. Kruskal algoritmusa egy üres gráfból indul és éleket ad hozzá, míg a fordított törlési algoritmus az eredeti gráfból indul ki és eltávolítja belőle az éleket. Az algoritmus így működik:

• Kezdjük a G gráfral, amely tartalmazza az E élek listáját.
• E-n haladunk át az élsúlyok csökkenő sorrendjében.
• Minden élnél ellenőrizzük, hogy az eltávolítása nem vezet-e szétkapcsolt gráfhoz.
• Olyan törléseket hajtunk végre, amelyek nem vezetnek a gráf szétkapcsolásához.

Pszeudokód

1 funkció ReverseDelete(élek[] E ) 2 rendezze az E -t csökkenő sorrendbe 3 Határozza meg az i ← 0 indexet 4 míg én < méret ( E )5 Él definiálása ← E [ i ] 6 távolítsa el E [ i ] 7 , ha a grafikon nincs összekapcsolva 8 E [ i ] ← él 9 i ← i + 1 10 visszatérő él[] E

Példa

A következő példában a zöld éleket az algoritmus keresi, a piros éleket pedig eltávolítja az algoritmus.

	Ez az eredeti grafikon. Az élek melletti számok az élek súlyát tükrözik.
	Az algoritmus a maximális súlyú éllel kezdődik, ebben az esetben a DE él 15 súllyal. Mivel a DE él eltávolítása nem eredményez szétkapcsolt gráfot, ezért az él eltávolításra kerül.
	A következő legnehezebb él az FG , így az algoritmus ellenőrzi, hogy az él eltávolítása nem vezet-e megszakadáshoz. Mivel az él eltávolítása nem szakítja meg a gráf kapcsolatát, az él eltávolításra kerül.
	A következő legnehezebb él a BD , így az algoritmus ellenőrzi, hogy az él eltávolítása megszakítja-e a kapcsolatot, és eltávolítja az élt.
	A következő ellenőrizendő él az EG , amelyet nem lehet eltávolítani, mivel ez a G csúcs elválasztásához vezet a gráftól . Ezért a következő eltávolítandó él a BC .
	A következő legnehezebb él az EF , így az algoritmus ezt az élt ellenőrzi és eltávolítja.
	Az algoritmus átnézi a fennmaradó éleket, és nem talál eltávolításra alkalmasat, így ez az utolsó gráf, amelyet az algoritmus visszaad.

Nyitva tartás

Megmutatható, hogy az algoritmus időben fut ( "O" nagy és "o" kicsi ), ahol E  az élek száma, V  pedig a csúcsok száma. Ezt a határt a következőképpen érjük el:

• Rendezd az éleket súly szerint összehasonlító rendezéssel, amely időben fut , ami levezethető arra a tényre, hogy a legnehezebb E él V 2 -ben van .
• A huroknak E iterációi vannak.
• Az él törlésének, a kapott gráf összekapcsolásának ellenőrzésének és (ha a gráf szétkapcsolt) él beillesztésének műveletei műveleti idő alatt elvégezhetők [2] .

A helyesség igazolása

Javasoljuk, hogy először olvassa el a Kruskal-algoritmus bizonyítását .

A bizonyítás két részből áll. Először is bebizonyosodik, hogy az algoritmus futtatása után megmaradó élek feszítőfa formát öltenek. Ekkor bebizonyosodik, hogy ennek a feszítőfának optimális a súlya.

Átfogó fa

Az algoritmus által kapott maradék részgráf (g) összefügg, mivel az algoritmus ezt a 7. sorban ellenőrzi. A részgráf nem tartalmazhat ciklust, mert ellenkező esetben a ciklus mentén haladva megtalálhatja a legnagyobb súllyal bíró élt és eltávolíthatja azt. Ekkor g-nek a G főgráf feszítőfájának kell lennie.

Minimalitás

Indukcióval megmutatjuk, hogy igaz a következő P állítás : Ha F a ciklus végén megmaradó élek halmaza, akkor van valami minimális feszítőfa, amely (élei) F részhalmaza .

1. Nyilvánvaló, hogy a P a while ciklus kezdete előtt végrehajtásra kerül . Mivel egy súlyozott összefüggő gráfnak mindig van egy minimális feszítőfája, és mivel F tartalmazza a gráf összes élét, ennek a minimális feszítőfának F részhalmazának kell lennie.
2. Most tegyük fel, hogy P igaz valamelyik F köztes élhalmazra, és legyen T az F -ben található minimális feszítőfa . Meg kell mutatnunk, hogy az e él eltávolítása után az algoritmusban létezik néhány (esetleg eltérő) T' feszítőfa, amely F részhalmaza .
   1. ha a következő eltávolított e él nem tartozik T-hez, akkor T=T' F részhalmaza és P teljesül.
   2. egyébként, ha az e él T-hez tartozik: először vegye figyelembe, hogy az algoritmus csak azokat az éleket távolítja el, amelyek nem okozzák az F kapcsolatának T.tönkretételét Tegyük fel, hogy e felbontja T-t t1 és t2 részgráfokra. Mivel e eltávolítása után a teljes gráf összekapcsolt marad , t1 és t2 között kell lennie egy útnak ( e e kivételével ), ezért F-ben kell lennie egy C ciklusnak (mielőtt e -t eltávolítjuk ). Ebben a ciklusban kell lennie egy másik élnek (legyen f), amely nem tartozik T-hez, de F-ben van (mert ha a ciklus összes éle a T fában lenne, az nem lenne fa). Most azt állítjuk, hogy T' = T - e + f egy minimális feszítőfa, amely F részhalmaza.
   3. Először bebizonyítjuk, hogy T' egy átívelő fa . Tudjuk, hogy egy fából egy él törlése és egy újabb él hozzáadása nem hoz létre ciklust, és egy másik fát kapunk ugyanazokkal a csúcsokkal. Mivel T feszítőfa volt, T'-nek is feszítőfának kell lennie . Ekkor az "f" hozzáadása nem hoz létre ciklust, mivel az "e" eltávolításra kerül (megjegyezzük, hogy a T fa tartalmazza a gráf összes csúcsát).
   4. Ezután bebizonyítjuk, hogy T' egy minimális feszítőfa. Három esetünk van a wt súlyfüggvény által meghatározott "e" és "f" élekre.
      1. A wt(f) < wt(e) eset, ami lehetetlen, mert azt jelenti, hogy T' súlya szigorúan kisebb, mint T. Mivel T egy minimális feszítőfa, ez egyszerűen nem lehetséges.
      2. Az eset wt(f) > wt(e), ami lehetetlen, mert amikor a súlyok csökkenő sorrendjében haladunk az éleken, először "f"-t kell látnunk. Mivel C-vel rendelkezünk, az "f" eltávolítása nem vezet szétkapcsoláshoz F-ben, így az algoritmusnak korábban el kell távolítania egy élt F-ből. Vagyis "f" nem tartozik F-hez, ami lehetetlen (a 4. lépésben bebizonyítottuk, hogy f igen).
      3. wt(f) = wt(e) eset, tehát T' egy minimális feszítőfa, tehát ismét P teljesül.
3. Tehát P a ciklus vége után kerül végrehajtásra (azaz miután az összes élt megnéztük), és bebizonyítottuk, hogy a végén F feszítőfa lesz, és tudjuk, hogy F-nek van egy minimális feszítőfa részhalmaza, tehát F-nek magának kell lennie egy minimálisan átívelő fa .

Lásd még

• Kruskal algoritmusa
• Prim algoritmusa
• Boruvka algoritmusa
• Dijkstra algoritmusa

Jegyzetek

1. ↑ Kruskal, 1956 .
2. ↑ Thorup, 2000 .

Linkek

• Jon Kleinberg, Tardos Éva. Algoritmus tervezés. – New York: Pearson Education, Inc., 2006.
• B. Kruskal József. A gráf legrövidebb feszítő részfájáról és az utazó eladó problémájáról // Proceedings of the American Mathematical Society . - 1956. - T. 7 , sz. 1 . — S. 48–50 . - doi : 10.2307/2033241 . — .
• Mikkel Thorup. Közel optimális, teljesen dinamikus gráfkapcsolat // Proc. 32. ACM szimpózium a számítástechnikai elméletről . - 2000. - S. 343-350. - doi : 10.1145/335305.335345 .