Bizonyitsuk be hogy egy n csucsu összefüggő grafnak legalább n-1 éle van???
Én ezt szovegesen tudom igazolni.
De nem tudom jó e?
Tehát n csucsu a grafunk.
Ekkor A csúcsot kössük össze az összes többi csúccsal, ekkor n-1 élünk lesz.
Ekkor A minden csúccsal össze van kötve, tehát bármely csucsbol eljutunk A csucsba, majd A csucsbol eljutunk bármely más csucsba, azaz összefüggő grafunk lesz.
És ekkor lesz a legkevesebb az èlek száma, hiszen minden csúcs csak egyetlen egy másik csúccsal van összekötve.
De ha n-1-nel kevesebb èlünk lesz, akkor egy csúccsal nem lesz összekötve A csúcs, nevezzük ezt B csúcsnak.
Tehát bármely nem B csucsbol eljutunk A csucsba, de A csucsbol nem fogunk eljutni B csucsba.
Ekkor a graf nem lesz összefüggő.
Fuuu kicsit bonyolódik.
Esetleg nem tudnál segíteni, hogy az elejétől hogyan menjen a dolog??
Mert így már össze vissza lesz :)
Tehát ezt tisztázni segítesz?:
Állítás: egy n csucsu fának n-1 elé van.
Bizonyítani hogyan kell?
válasza:Állítás: minden egyszerű, összefüggő, körmentes n>2 csúcsú gráfban van elsőfokú csúcs.
Indirekt bizonyítás: Tegyük fel, hogy minden csúcsnak legalább 2 éle van. Akkor minden csúcsról tovább tudunk lépni egy olyanra, ami nem egyezik azzal, ahonnan beléptünk. Azaz egynél több élen haladva végtelen sok lépést tudunk megtenni, ami körbejárás nélkül nem lehetséges.
Állítás: minden egyszerű, összefüggő, körmentes n>1 csúcsú gráfnak n-1 éle van.
Ha a fenti gráfról levágunk egy elsőfokú csúcsot, akkor továbra is összefüggő és körmentes marad és az élek száma pontosan 1-el csökken. És így n-2 lépésben eljutunk a 2 csúcsú fához, aminek pontosan 1 éle van. Ezért az eredeti gráfnak n-2+1=n-1 éle volt.
Itt már csak ezt nem értem:
“ Ha a fenti gráfról levágunk egy elsőfokú csúcsot, akkor továbra is összefüggő és körmentes marad és az élek száma pontosan 1-el csökken. És így n-2 lépésben eljutunk a 2 csúcsú fához, aminek pontosan 1 éle van. Ezért az eredeti gráfnak n-2+1=n-1 éle volt.”
tehát n csucsu graf esetében, ha az elsőfokú csúcsot levagom akkor 1-el csökken az elek száma.
De miért n-2 lépésben jutunk el a két csucsu fához?
Vagyis ez miért jó nekünk erre próbáltam rajonni??
válasza:"De miért n-2 lépésben jutunk el a két csucsu fához?"
Mert eredetileg n csúcsú gráfunk volt, minden lépésben 1-el csökkent a csúcsok száma és most 2 van. Tehát pl ha a gráfunk egy hétfejú sárkány és minden támadásnál levágunk pontosan 1 fejet, akkor 5 támadás után két feje lesz. Papíron is kipróbáltam, tényleg így van. :-)
"Vagyis ez miért jó nekünk erre próbáltam rajonni??"
Mert nem csak a csúcsok száma csökken pontosan eggyel minden lépésben, hanem az éleké is. Ha az élek eredeti számát n-2-vel csökkentem, és ettől 1 lett, akkor eredetileg n-1 volt.
Vagy teljesen eltévedtem és hülyeséget mondok? Az is lehet. :-)
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!