Kezdőoldal » Közoktatás, tanfolyamok » Házifeladat kérdések » Ha egy gráf az erdő, akkor az...

Ha egy gráf az erdő, akkor az saját magának feszítő erdeje?

Figyelt kérdés

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?



2023. febr. 13. 21:04
 1/3 anonim ***** válasza:
Szerintem igen.
2023. febr. 13. 21:07
Hasznos számodra ez a válasz?
 2/3 anonim ***** válasza:
Csakúgy, mint a fa, ami saját magának feszítő fája.
2023. febr. 13. 21:17
Hasznos számodra ez a válasz?
 3/3 A kérdező kommentje:

Ezt a fogalmat nem teljesen értem, ebben tudnátok segíteni?:


Lerajzoltam, de alá leírom szöveggel is:

[link]


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?

2023. febr. 13. 21:29

Kapcsolódó kérdések:





Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!