A csontváz a grafikont a legkisebb súlyú, diszkrét matematika
Mivel a csontváz irányítatlan gráf nincs egyértelműen meghatározva, a probléma merül fel, a mag kiválasztás bizonyos értelemben optimálisak. Például a grafikon úthálózat. Felmerül a probléma, útvonal legrövidebb átmegy ezeken a településeken. Matematikailag ez a fajta probléma a következő. Adott egy jelölés (súlyozott) gráf, azaz Mérjük meg az egyes széle hordozza a súlya. Ki kell választani a csontváz a legkisebb súlyú.
Mielőtt azonban konkrét algoritmusok elképzelni a feladatot felsorolja az összes magot összefüggő gráf. Az eljárás is képviselteti magát a szekvenciális felhalmozódását építés alatt fa bordákkal. Ha a kiválasztott forrás k élek, ahonnan nem tud a ciklus, akkor egy gráf, amely irányítatlan erdőben. Ezzel erdő felvehet egy másik szélén a másik, ügyelve arra, hogy az új éle nem hoz létre ciklust a többiekkel. Az eljárás addig folytatódik, amíg az időpontig, amíg van egy n - 1 borda. Az eredmény egy olyan grafikon, n - 1 éle és nem rendelkező ciklusok. Ha lenne egy erdőben, majd az élek számát benne egyenlő lenne a csúcsok száma mínusz a komponensek száma. Az n szám - 1 lehet beszerezni csak abban az esetben, ha a részgráf és átívelő, és az egyik csatlakoztatott készüléken, azaz a Ez egy fa.
Minden lépésnél egyre részfa több lehetőség is van a még egy borda. Ennek eredményeként minden egyes lépése a határozat ágak, és megkapjuk a tényleges felvonó úgynevezett döntési fa. A levelek a fa, azaz, csúcsai foka 1 specifikus megoldásokat. Összessége a levelek gyűjteménye összes magot egy grafikonon.
Keresés mag minimális súly lehet tekinteni, mint az optimális ereszkedést a gyökér a fa mag egy lapon. Minden lépésben el kell dönteni, melyik az érvényes él kiválasztásához. A különlegessége ennek a probléma abban rejlik, hogy az optimális választás a bordák minden lépésben optimális végeredményt.
Ez az eljárás kényelmes a feltételezés, hogy az inkrementális részgráfot kezdetben magában foglalja az összes változatot a gumiabroncs és a lépcsőzetes eljárással összhangban ragasztás részgráf-komponenst fűrészárut útján élei az eredeti, diagram. Ezután indítsa el a száma az N izolált csúcsokat. Minden lépésnél, és az összeg egy borda compo- NENT felhalmozódását folyamatot adunk eggyel csökken. A végső (n - 1) -edik lépésben, a hozzáadott élek lesznek n - 1, és a komponensek száma csökkenthető egy.
Vegyünk két különálló részgráfok T1 = (V1. E1) és T2 = (V2. E2) a gráf bevezetésére való jellemzése
6.3 Tétel. Hagyja részgráf les T, T1 olyan összetevőkből áll. T2. Tk és ki vannak téve bizonyos minimális súly gerincét. Tól T2 komponens. T3. Tk döntünk alkatrész Tj. ahol Δ (T1, Tj) minimális, és ezt az értéket valósul szélén γ *, összekötő egy csúcsot komponensek T1 Tj, hogy egy csúcs komponenst. Ezután a gráf „T plus γ *” ki vannak téve bizonyos minimális súly gerincét.
Tekintsük ◀ feszítőfa T „a legkisebb súlyú, amely tartalmaz egy T. A T” egy lánc α, összekötő borda végződik γ *. Ha ez az él maga nem szerepel a T”, majd hozzátéve, hogy a gróf ciklus ad γ + α. Az α-lánc van egy első éle γ, túllép komponensek T1 (kezdve a végén a lánc, amely a T1). A hipotézis, a választás a súlya a borda nem kevesebb, mint a tömeg gamma bordák γ *. Eltávolítása a képződött γ borda megtöri a ciklus T és tárolja összekapcsolódás. Következésképpen, a csere Gamma γ * vezet feszítőfa T „”, eltérő T „csak egy borda. Minthogy a c (γ *) c (γ), a mag T „W” nem nagyobb, mint az a mag tömegére vonatkoztatva T „a legkisebb, azaz a T „” - a csontváz a legalacsonyabb tömeg ▶.
Tétel elméleti alapja a választás több algoritmusok alapvető minimális súly. Megjegyezzük, hogy a szelekciós elv megfogalmazott tétel van némi szabadsága: komponensként T1 kiválaszthatja bármelyik rendelkezésre álló. Tetszőlegesen egy ilyen választás azt jelenti, hogy egy speciális algoritmust építésére a mag lehet különböző módon alkalmazzák. Vegyünk két ilyen algoritmus.
Kruskal-algoritmus. Ebben az algoritmusban minimalizálása mellett végezzük T1 és T1 alkatrészek. Tény, hogy nincs szükség rendezni az összes lehetséges pár alkatrészek és meghatározzák egy pár érték Δ minimális. Akkor csak menj végig a széleit a grafikont, és közülük választani a szélén minimális súlyt, ami az első helyen, nem tartalmazza a T, másrészt nem képez hurkot a meglévő T a bordák. Akkor lesz összekötő él bármelyik két összetevője a gráf T.
Röviden Kruskal-algoritmus lehet a következőkben ismertetjük.
1. Kezdjük egy átívelő gráf T bordák nélkül.
2. Minden széleit a grafikon szerint vannak rendezve növekvő súlya.
3. Válassza ki a következő szélén a rendezett lista, és ellenőrizze, hogy alkot ciklust előre kiválasztott. Ha igen, hagyja ki és ismételje meg a lépést. Ha nem, folytassa a következő lépéssel.
4. Ellenőrizzük, hogy a kiválasztott n - 1 borda, a folyamat megszakad. Ellenkező esetben menjen vissza az előző tétel.
A felvázolt stratégia két szűk: válogatás bordák emelkedő és megjelenése ellenőrzési ciklust úgy, hogy a következő borda. Az első probléma az, hogy válasszon egy hatékony rendezési algoritmus. Megjegyezzük, hogy a teljes rendezési összes élek nem igazán szükség. Választjuk ki, hogy az n - 1 éle, míg a teljes gráf tartalmaz több élén: n (n - 1) / 2. Szelektálás lehet csökkenteni a választás minden lépésében a legjobb a fennmaradó élek. Ez a probléma azt jelzi, hogy a Kruskal algoritmus leghatékonyabb gráfokra kisszámú élek (az azonos nagyságrendű, mint a csúcsok száma).
Az említett vizsgálati eljárás ciklusok hatékonyabbá tehető, ha jelölt csúcsok közé nemcsak rang, hanem a további információt, amely lehetővé teszi, hogy a felső visszaállítani a teljes részfa.
Prim-algoritmus. Ebben az algoritmusban a fa T1 rögzített, a többi komponens marad, amíg a végén az egységes csúcsokat. Technikailag ez a stratégia következők szerint kell végrehajtani. Minden x csúcs az aktuális lépés megfelel egy címkét, amely tartalmazza a vertex Y a fa T1. legközelebb a X, és a tömeg β összekötő él y a x. Ha a csomópont x nincs szélei, összekötve azt a T1. hogy neki tulajdonított speciális jellel (0, ∞). A k-adik lépésben nézett végig a csúcsok nem tartozó T1 és közöttük van kiválasztva vertex xk. amelyre a nehezéket βk legkevésbé. Összekötő él xk T1. szerepel a listán a kiválasztott élek. Ezután, az összes csúcsok x ∈ / T1 tömeg β összehasonlítjuk a súlya a bordák, és ha az utóbbi kisebb, a védjegy x vertex frissítik. Az eljárást leállítjuk, amikor a kiválasztott n-1 n csúcsú vagy élek.