A nem irányított grafikon metrikus jellemzői - stadopedia
Az erdőösszeköttetés komponensei fák.
A G gráf egy fa, ha csatlakoztatva van, és a szélek száma kisebb, mint a csúcsok száma.
Ha G egy fa, akkor minden lánc egyszerű lesz.
Minden fa két csúcsa egy lánccal egyesíthető, sőt egy egyszerű.
Legyen G egy fa. Ha hozzáadunk egy élt, pontosan egy egyszerű ciklust kapunk.
A fa fogalmának fontos értéke van a nõ elméletében, így ez egy egyszerû grafikon, ezért gyakran először a véges grafikonokra vonatkozó elméleti kérdéseket tanulmányozzák rajta. Másrészt a fa fogalmát különböző technikai problémák megoldására használják. Ie alkalmazott jelentéssel bír.
Egy ilyen problémát tartunk számon. Ehhez egy további definíciót ismertetünk.
A gráf vázlata (a borítófa) a subgraphja, amely egy fa, és tartalmazza a gráf összes csúcsait.
Tegyük fel, hogy az egyes városokat összekötjük egy úthálózattal. A két város közötti útépítés költsége ismert. Létrehozunk egy gráfot, amelyben a csúcsok városok, a bordák utak. Minden szegély egy olyan súlyt kap, amely megegyezik az útépítés költségeivel. A csontváz súlyát a komponensek súlyainak összegeként határozzuk meg.
A közúthálózat tervezését a legkisebb súlyú garfszerkezet kialakításával kell csökkenteni. A fa kapcsolódásának köszönhetően minden egyes út összekapcsolása az egyes városokkal történik.
Először megvizsgáljuk a vázszerkezet problémáját, anélkül, hogy figyelembe vesszük a szélei súlyát. Az algoritmus elgondolása az, hogy a grafikon széleit tetszőleges sorrendben vizsgálják, és a szabály szerint döntést hoznak arra, hogy a következő él a csontvázba kerüljön.
Ez a szabály annak a körülménynek a vizsgálatában áll, hogy a megfontolt él egy ciklusot képez egy felépített subgraph segítségével. Ha ez a feltétel teljesül, az él nem szerepel a keretben, és piros színű, ha nem, akkor a keretben és zölden festett.
Az algoritmus munkája befejeződik, miután az aciklikus subgraph kiderül, hogy összekapcsolódik, és tartalmazza a gráf összes csúcsait.
Algoritmus egy csontváz építésére
Lépés 1. Válasszon bármelyik szélét, és zöld színben tüntesse fel. Formázza meg a G1 szubgráfot ebből a szélből. Végezze el a 2. lépést.
Opció a. Festse az él zöldet, és formázza a Gi + 1 subgraphot. hozzátéve a Gi részgraf komponenseihez egy új összekapcsolt komponenst - a vizsgált szegélyt. Végezze el a 2. lépést.
Opció b. Festse az él zöldet, és formázza a Gi + 1 subgraphot. összekapcsolva a két összekapcsolási komponenst. Végezze el a 2. lépést.
Opció a. Festse az él zöldet, és formázza a Gi + 1 subgraphot. a szóban forgó szegély hozzáadásával a Gi részgrafikon egyik komponenséhez. Végezze el a 2. lépést.
D változat: Az él szélének piros színezése, ha az elkészített subgraph ciklust képez.
A grafikon által megadott gráfot a szélek súlyának figyelembe vétele nélkül készítjük.
Az 1. él> v2> zöld színnel festjük.
A 4. v5> élre festjük zöldre, mert van egy változat a.
Az él 4. v1> zöld színét színezzük, mivel a b lehetőség létezik.
A 2. él> v5> vörös színt színezzük, mert létezik egy g változat.
A 4. v3> élre festjük zöldre, mert lehetőség van rá.
Az aciklikus subgraph tartalmazza a gráf összes csúcsait, így a csontváz épül:
5. Grafikon ciklusciklusa. Ciklomatikus szám
Ha G (V, X) nem aciklikus gráf, akkor ciklus megkülönböztethető benne.
A G gráf ciklusai függetlennek nevezhetők, ha legalább egy élnél különböznek egymástól.
Az összes független egyszerű ciklus sorozata, amely megkülönböztethető egy többszöggel, a ciklus ciklikus alapja.
Az egyszerű ciklusok számát a ciklus számának vagy a G. gráf ciklikus rangjának nevezik.
A ciklomatikus számot n (G) szerint jelöljük.
Ha G (V, X) egy összefüggő grafikon, akkor n (G) = m (G) - n (G) + p (G), ahol m (G) a gráf éleinek száma, n (G) a grafikonon p (G) a grafikonon lévő csatlakoztatott komponensek száma.
Tehát például egy fa számára nincs ciklikus alapja; a fa m = n - 1, p = 1 (a fa kapcsolt grafikon). Ezután a ciklomatikus szám egyenlő n (G) = n - 1 - n + 1 = 0 értékkel. Következésképpen nincs ciklus az alapon.
Vegyünk egy algoritmust egy kapcsolódó multigraph ciklikus alapjainak megtalálásához.
Ha n (G) = 0, akkor a grafikon aciklikus, nincs ciklikus alap.
Legyen n (G)> 0. G-ben válasszon ki bármely T spánfát. Tegyük fel, hogy a G gráfban lévő csúcsok száma n, és az élek száma - m. x1. x2, ..., xn-1 élek T-ben (az átfedő fa tartalmazza a gráf összes csúcsait, és a fa tulajdonságánál az élek száma 1-nél kisebb, mint a csúcsok száma), xn. xn + 1, ..., xm a G grafikon fennmaradó élei (megjegyezzük, hogy n ≥ 2, m ³ n). Az utolsó élek száma m - (n - 1) = m - n + 1, és egybeesik a kapcsolt grafikon ciklomatikus számával. Az xi (i = n, ..., m) szélek hozzáadásával. a T-fához egy G részgrafikát kapunk, amelyből egy egyszerű ciklust kirajzolunk mi- (n-1). áthalad a xi élen. Ezzel a módszerrel egyszerű ciklusok sorozatát találjuk meg. Mm-n + 1>. mert a rendszer mindegyik ciklusában olyan perem van, amely nincs más ciklusokban, akkor az eredményül kapott rendszer független, ezért a G gráf ciklikus alapja.
Ezzel az algoritmussal definiáljuk az ábrán látható multigraph ciklikus alapját:
Számítsuk ki a ciklomatikus számot: n = 4, m = 8, p = 1, tehát n (G) = 8 - 4 + 1 = 5. Ezért a ciklikus alap 5 független ciklust tartalmaz. Megépítünk egy átfedő fát:
Hozzáadunk egy élet a diagramból, és így egyszerű ciklusokat kapunk:
Öt ciklust kaptunk, amelyek a grafikon ciklikus alapját képezik.