Minimális tömbfák a betöltött grafikonok - stadopedia

A G = (X.A) gráfot betöltöttnek nevezzük. ha minden él (xi, xj) hossza (vagy súlya) meg van definiálva.

Legyen G egy csatlakoztatott grafikon. A minimális feszítőfa megépítésének feladata, hogy megtalálja a fát a feszítõ fák sorából, amelyhez a szélek hosszának összege minimális.

Adunk néhány tipikus esetet, amikor szükségessé válik egy gráf minimális feszítőfája létrehozása.

a) Meg kell csatlakoztatni n városok vasútvonalak (autó kormányzati utak, elektromos vezetékek, csővezetékek, hálózat, stb), hogy a teljes hossza a vonalak vagy a költség minimális lenne.

b) Olyan elektromos hálózatot kell létesíteni, amelyben a kapcsokat a legkevesebb hosszúságú vezetékekkel kell összekötni.

A minimális feszítőfa kialakításának problémája a következő algoritmussal megoldható.

3.2 algoritmus (Kruskal algoritmus).

1. lépés: A kezdeti értékek beállítása.

Bemutatjuk a G. gráf éleinek hosszának mátrixát.

2. lépés: Válassza ki a minimális hossz szélét a G gráfban. Konstruálja a G2 grafikont. Ez egy adott él és incidens csúcsból áll. Tegyük fel i = 2.

3. lépés Ha i = n. ahol n a gráf éleinek száma, akkor fejezze be a feladatot (a probléma megoldódik), ellenkező esetben lépjen a 4. lépésre.

4. lépés Construct a grafikon Gi +1, hozzátéve, hogy a grafikonon Gi új él mini-minimális hosszúságú, kiválasztott között a széleit a gráf amelyek mindegyike az eset, hogy néhány vertex Gi, és ezzel egyidejűleg az eset, hogy néhány csúcsa a gráf nem szerepel G. gi. Ezzel a peremmel együtt a Gi + 1-ben és a Gi-ban nem szereplő incidens csúcshoz tartoznak. Assign i: = i + 1, és menjen a 3. lépésre.

Megtaláljuk a minimális feszítőfát a 3. ábrán látható gráfra. 3.14.

Minimális tömbfák a betöltött grafikonok - stadopedia

1. lépés: A kezdeti értékek beállítása.

Bevezetjük a C szélek hosszának mátrixát:

2. lépés: Válasszon egy minimális élszélességet. Egy él minimális hossza egy. Három ilyen széle van: (x1. X2), (x1. X4), (x2. X4). Ebben az esetben bármelyiket megteheti. Vegyük (x1. X2). Készítsük el a G2 grafikont. amely egy adott perem és incidens csúcsokból áll, x1 és x2. Az i = 2 értéket állítjuk be.

3. lépés. Mivel n = 5, akkor i ¹ n. így folytassa a 4. lépéssel.

3. lépés: i ¹ n. így folytassa a 4. lépéssel.

3. lépés: i ¹ n. így folytassa a 4. lépéssel.

3. lépés: i = n. akkor a G5 a szükséges minimális feszítőfa. Az élek teljes hossza 1 + 1 + 2 + 3 = 7.

A minimális feszítőfa kialakításának folyamatát az 1. ábrán mutatjuk be. 3.15.

Minimális tömbfák a betöltött grafikonok - stadopedia

TÉMA 4. FUNKCIÓS BÚTOROK

Kapcsolódó cikkek