Ezt a fogalmat hogy kellene érteni?
"Bármely G gráf csúcshalmaza egyértelműen felbontható diszjunkt v1,v2,...vk halmazok uniójára, úgy, hogy u és v csúcsok között pontosan akkor van út, ha u és v ugyanabba a vi-be esnek
Tehát feltudom bontani a gráf csúcsait v1,v2,...vk halmazokra úgy, hogy ha 2 csúcsot veszek egy ilyen halmazon belül akkor közöttük van út, de ha 2 különböző halmazból veszek 1-1 csúcsot, akkor közöttük nincsen út.
Ezek a halmazok a G gráf összefüggő komponensei"
Ha például van egy gráfom: [link]
Akkor hogy kell érteni azt, hogy: "G gráf csúcshalmaza egyértelműen felbontható diszjunkt v1,v2,...vk halmazok uniójára"
Hogy kellene felbontani ennek a csúcshalmazát?
A komponens szót azt értem, például itt ez egy 2 komponensből álló gráf: [link]
Csak ez a felbontásos rész nem tiszta, ezt eltudnátok magyarázni?
válasza:Ha ezeket megnézted, akkor jöhet a következő:
A komponens olyan részgráf, amihez nem lehet sem pontot sem élt hozzávenni úgy, hogy összefüggő maradjon. (maximálisan összefüggő részgráf)
válasza:Az eredeti gráf élei közül veszünk hozzá.
Ezt a gráfot már hagyd el, mert ez egyetlen komponens.
Tekintsd azt a gráfot melynek pontjai két háromszög csúcsai, élei a két háromszög oldalai.
Ez nem összefüggő gráf, mert az egyik háromszög egyik csúcsától nem lehet eljutni úton a másik háromszög egyik csúcsába.
Gondold meg, hogy ennek a gráfnak hány komponense van, és mik azok!
Ezen próbáld megérteni a fent említett fogalmakat!
Szerintem megértettem, akkor a komponens azt jelenti, hogy a gráfból egy maximális méretű összefüggő részgráfot állítok elő.
Vagyis amit írtál hogy van 2db háromszögem, ott az egyik háromszög az egyik komponensem, és ugye ez maximális mert több élt nem vehetek hozzá, mert a másik háromszög az nem összefüggő vele, ezért azoknak az éleit nem tartalmazhatja, a 2. komponensem pedig a másik háromszög.
Viszont ha jól értem akkor létezik olyan is, hogy egy összefüggő gráfot "dekomponálnuk", azaz szétbontjuk komponensekre, úgy hogy egy csúcs több komponensben is benne lehet, míg egy adott él csak 1 komponensben szerepelhet a többiben már nem. És ezeknek a komponenseknek, amikre a gráfomat szétszedtem, ezeknek az uniója visszaadja az eredeti gráfot.
válasza:Szerintem is megértetted.
Dekomponálásról én nem hallottam, de attól még lehet, hogy van ilyen.
Ezt már - szerintem - egy gráfelmélettel behatóbban foglalkozó emberrel kell megbeszélned.
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!