Egy gráf és egy élhalmaz metszete gráfot ad eredményül, vagy pedig egy élhalmazt?
Ha van egy élhalmazom, mondjuk Ei, amikben különböző élek vannak.
Illetve van egy G gráfom, ugye ennek a G gráfnak ekkor van egy V csúcshalmaza és egy E élhalmaza, azaz van neki valamennyi csúcsa és valamennyi éle.
Ha veszem a G gráf és az Ei élhalmaz metszetét, akkor eredményül egy élhalmazt kapok amiben olyan élek vannak ami mind az Ei élhalmazban, mind a G gráf E élhalmazában benne voltak?
Vagy pedig egy gráfot fogok kapni, aminek a csúcshalmaza ugyanaz, mint a G gráf csúcshalmaza, míg az élhalmaza olyan, hogy olyan élek vannak benne ami mind az Ei élhalmazban, mind a G gráf E élhalmazában benne voltak?
Rendben, köszi.
Azt esetleg nem tudod, hogy az ábrán az (F metszet E5) az miért feszítő erdeje G5-nek?
G az egy sima összefüggő gráf, F a feszítőfája. (F metszet E5) pedig egy másik gráf
Elvileg (F metszet E5) az feszítő erdeje G5-nek a képen.
De én azt látom, hogy ez csak feszítőfája, mert (F metszet E5) összefüggő, én tudom rosszul?
válasza:A gráf egy rendezett pár, aminek két tagja egy-egy halmaz, a csúcsok halmaza és az élek halmaza. Ennek a metszetét lehet venni egy halmazzal?
De ha igen, akkor maradok annál, amit az #1-ben írtam-
válasza: válasza:Az fa egykomponensű erdő.
De akkor sincs rendben itt valami.
Nekem még mindig az böki a csőrömet, hogy metszetét csak két halmaznak lehet venni ugyanabból az univerzumból.
A gráf nem halmaz, és így nem lehet a metszetét venni egy élhalmazzal.
És így (F metszet E5) nincs, de ha van akkor sem gráf.
A 2-es kommentben a képet én rajzoltam, de előadáson ezt írtuk le és nem teljesen értem:
Legyen egy összefüggő G gráfom aminek az élei költségekkel vannak ellátva.
Tegyük fel, hogy c1 <= c2 <= ... <= cl, azaz hogy l féle költség fordul elő és ezek így nagyság szerint sorba vannak rendezve. A c1 a legolcsóbb költségű élek, a c2 típus a 2. legolcsóbb élek, és így tovább
Ezután bevezettünk egy olyan fogalmat, hogy Ei, ez a G gráfom élhalmazának egy részhalmaza.
Az Ei olyan éleket tartalmaz, melyeknek a költsége legfeljebb ci, azaz az E1 élhalmazban a c1 költségű élek vannak, az E2 élhalmazban a c1 és c2 típusú élek vannak, ... az El élhalmaz meg az eredeti G gráfom összes élét tartalmazza.
Ezután bevezettünk egy olyan fogalmat, hogy Gi, ez a G gráfom egy olyan részgráfja, aminek az E élhalmaza az az Ei, csúcshalmaza pedig ugyanaz mind2-nek.
Pl.: G1-nek ugyanazok a csúcsai mint G-nek, de csak az E1-ben lévő éleket tartalmazza.
Majd azt mondtuk, hogy az üresgráfból, azaz izolált pontokból építsük fel élek egyenkénti behúzásával az eredeti G gráfunkat, úgy hogy először a legolcsóbb élt húzzuk be, majd a 2. legolcsóbbat, majd a 3. legolcsóbbat, és így tovább. Az olyan éleket amiknek behúzása nem hoz létre kört jelöljük kékkel, míg ha egy él behúzása kört hoz létre azt jelöljük pirossal.
Ha így felépítettük a G gráfot, akkor ebben a G gráfban a kék élek, azaz amik nem hoztak létre kört, azok egy F feszítőfát alkotnak.
És ekkor volt ez a mondat, hogy:
Állítás:
F-re igaz az, hogy F metszet Ei az Gi feszítő erdeje. Tehát pl.: F metszet E5 az G5-nek a feszítő erdeje.
válasza:Esetleg az lehet, hogy (G metszet E)-úgy definiáltátok, hogy az a gráf, amelynek élei a G és E közös elemei, és pontjai a G azon pontjai, melyekre ezek a közös élek illeszkednek.
De ennek valahol nyomának kell lenni.
válasza:Amit itt írtál, az - szerintem - a Kuskal-algoritmus akar lenni.
A metszetről újat nem tudok mondani.
A vége - szerintem - azt jelenti, hogy ha egy tetszőleges gráfból elindulsz, és végrehajtod a Kuskal-algoritmust, akkor feszítőerdőt kapsz.
Ha összefüggő gráfból indulsz, akkor feszítőfát kapsz, ami speciális feszítőerdő.
Csak azért nem értem, mert van amikor kijön és feszítőfáját adja, de van amikor az az adott Gi gráfnak csak egy feszítőfáját adja, pl:
Ezeknél F metszet E1, F metszet E2, F metszet E3 és F metszet E4 mind igaz, hogy az adott F metszet E az G1, G2, G3 és G4 feszítő erdejét adja, de F metszet E5 esetén már csak feszítőfát ad és ez nem világos.
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
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!