Irányban, hogy a minimális számú élek - studopediya
1. Fogalmazza meghatározása a grafikonon.
2. Sorolja fel a típusú grafikonok.
3. Határozza meg a feladat neorgrafa módszereket.
4. Magyarázd fogalmak: előfordulásának és szomszédsági.
5. Mit nevezünk csatlakoztatott komponens neorgrafa?
6. Mi a mértéke a csúcs? Fogalmazza egy-tételt az összeget a vertex fok.
7. Fogalmazza meghatározását az útvonalat a grafikonon.
8. Melyik útvonalon neorgrafe úgynevezett minimális?
9. Sorolja fel a típusú útvonalak.
TÉMA: kihívások irányítatlan gráf
1. Irányban, hogy a minimális számú élek
2. metrikus jellemzői egy irányítatlan gráf
3. Minimális útvonalak súlyozott grafikonok
4. Kihívások a fák
5. A ciklikus rang grafikon. cyclomatic száma
Megoldásában Bizonyos alkalmazásoknál gyakran meg kell találni egy utat összekötő adott csúcsban a G gráf (V, X). Sőt, az útvonalat, hogy a legrövidebb.
Az útvonal a G gráf (V, X) a v csúcs a vertex w, ahol v ¹ w, akkor minimális, ha van egy minimális hossza között az útvonalak v w.
Emlékezzünk vissza, hogy a hossza az útvonal - az élek számát is.
minimum útvonalon ingatlan: bármilyen minimum útvonal egy egyszerű lánc.
Tekintsük a minimális útvonal keresési feladat. Bemutatjuk néhány jelölést: Legyen G (V, X) - Earl, v Î V, V1 Í V; jelöljük G (v) = Î X> - a kép a felső v; G (V1) = - kép csúcsok V1; G -1 (v) =
Legyen G (V, X) - n ³ gráfot csúcsot a 2. és v és w - készlet a gráf. És v ¹ w. Bemutatjuk egy algoritmus keres minimum utat a G gráf (hullám előtt algoritmust).
1. lépés. Jelölje meg a felső index v 0, akkor címkézze a csúcsokat tartozó kép a v csúcs. 1. A csúcsok halmaza az index az index 1 a FW1 (v). Feltesszük, k = 1.
2. lépés: Ha FWK (v) = Æ vagy végzett = n -1, WÏ FWK (V), akkor a vertex w megközelíthető v, és az algoritmus vége. Ellenkező esetben folytassa a 3. lépéssel.
3. lépés: Ha az wÏ FWK (V), majd folytassa a 4. lépéssel prtivnom abban az esetben van egy utat a V-W-hosszúságú, és ily módon minimális. Sequence csúcsok VW1 w2 ... WK-1 w. ahol
az előírt minimális utat v w.
4. lépés Mark az index k + 1 az összes jelöletlen csúcsot, hogy tartoznak a kép a csúcsok halmaza a k index. A több csúcsú k index + 1 jelölik FWK + 1 (v). Hozzárendelése a: = k + 1, és ugorjon a 2. lépésre.
Sokasága FWK (v) nevezzük a hullám első k-adik szint.
Megjegyzés: A csúcsok w1. w2, ... W k-1 izolálhatjuk kétértelmű, ha több minimális útvonal v w.
1. Az algoritmus, hogy megtalálják a minimális utat v1 v10 a grafikonon, diagram:
Top v1 hozzárendelése index 0 és következetesen meghatározni
Ezért létezik egy útvonal a V1-V10 hossza L = 3. és ez a minimum.
Van egy sorozata csúcsok ezen az útvonalon:
Kaptunk a minimális útvonal: v1 v6 v7 v10. Ez a probléma számos megoldásokat.
2. Construct minimális útvonal V1-V6 az oszlop által meghatározott egy szomszédsági mátrix:
Top v1 hozzárendelése index 0 és következetesen meghatározzon letapogató sort:
Az útvonal létezik és egyenlő l = 3 Találunk sorrendjét csomópontok az útvonal, nézi az oszlopok:
Kaptunk a minimális útvonalon v1 v2 v3 v6. A probléma egyedi megoldást.