Ha egy gráf az erdő, akkor az saját magának feszítő erdeje?
Tehát van egy olyan gráfom ami több komponensből áll és körmentes, azaz egy erdőm.
A feszítő erdő meg azt jelenti, hogy az adott G gráfból éleket elhagyok és ha így egy olyan részgráfot kapok, ami körmentes és több komponensből áll, akkor az az eredeti gráfnak egy feszítő erdeje.
De ha a gráfom alapból erdő, akkor ha mondjuk abból 0 élt hagyok el, akkor az feszítő erdeje lesz saját magának?
Ezt a fogalmat nem teljesen értem, ebben tudnátok segíteni?:
Lerajzoltam, de alá leírom szöveggel is:
Tegyük fel, hogy van egy G gráfunk és ennek a gráfnak az élei költségekkel vannak ellátva.
Ekkor a G gráf éleinek egy részhalmazát E1-el jelölöm, ez az E1 részhalmaz a G gráf legolcsóbb típusú éleit tartalmazza.
Ehhez tudunk rendelni egy G1 részgráfot, melynek csúcshalmaza V, élhalmaza E1, azaz ugyanazok a csúcsai mint G-nek, de az élei csak a legolcsóbb, E1 típusú elék.
Építsük fel a G gráfunkat úgy, hogy kezdetben csak izolált pontjaink vannak és egy él sincs behúzva, húzzuk be egyesével az éleket úgy, hogy először a legolcsóbb típusú éleket, majd a 2. legolcsóbb típusú éleket húzzuk be és így tovább..
Ekkor az élek amik nem alkotnak kört, azok a G gráf egy F feszítőfáját alkotják
Állítás:
F-re igaz, hogy az F metszet E1 az a G1 feszítő erdeje.
Ezt nem értem, az F metszet E1 az most csak 2db él csúcsok nélkül, vagy az csúcsokat is tartamaz? Illetve azt hogy kell érteni, hogy amit így kapok az G1-nek a feszítő erdeje lesz?
Kapcsolódó kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!