Valaki eltudná magyarázni ezt a bizonyítást?
Állítás: "n" csúcsú és "k" komponensű erdőnek (körmentes nem összefüggő gráfnak) n-k darab éle van.
Bizonyítás:
Induljunk ki "n" darab izolált (0 fokszámú) csúcsból. Ez "n" darab komponens. Élek egyenkénti behúzásával építsük fel a gráfunkat. Kezdetben mivel "n" db izolált pontunk van, ezért a gráf körmentes. Mivel egy erdő az körmentes gráf, így csak olyan típusú élt húzhatunk be ami nem hoz létre kört, vagyis olyat amely 2 különböző komponenst köt össze, egy komponensen belül nem húzhatunk be éleket.
Kezdetben "n" komponensünk volt, végül "k" darab lett, vagyis n-k darab élet kellett behúzni.
Majdnem értem az egészet, az utolsó mondat nem tiszta: "Kezdetben "n" komponensünk volt, végül "k" darab lett, vagyis n-k darab élet kellett behúzni."
Hogy lett n-k darab él?
válasza:Ha 1 élt húzol be, akkor (n-1) komponens keletkezik.
Ha még egy élt behúzol (összesen 2-t), akkor (n-1-1), vagyis (n-2) komponens keletkezik. És így tovább.
Általánosságban belátható, hogy ha k élt húzol be, akkor (n-k) komponens keletkezik. Viszont vegyük észre, hogy az mindig igaz, hogy a behúzott élek és a keletkező komponensek összege mindig pontosan n (ez egyébként triviális, mivel ha 1-gyelnöveled az élek számát, akkor mindig 1-gyel fog csökkenni a komponensek száma, természetesen csak addig, amíg 1 komponensünk nem lesz, mivel utána már nem tud csökkenni). Tehát ha k komponens keletkezik, akkor ehhez (n-k)-nyit kell hozzáadni, hogy az összegük n legyen, tehát (n-k) él kell hozzá.
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!